調和的靈感

解題背景 這題是傳說中的Endian問題。我們都知道int占用4 bytes，但是很神奇的這 4 byte 在記憶體中的排列方式並不固定，分為兩派，一派是以 Intel 為首的 little-endian，另一派是網路傳輸使用的 big-endian。 我用例子來說明，有個變數: int x = 11112345; 如果我們從記憶體的角度來看這個變數x，也就是轉換為二進位bit來觀察，那麼會看見以下兩種狀況: 變數 x 的四個 byte 在 big-endian 的機器上做如此排列 00000000 10101001 10001111 10011001 但是在 little-endian 的機器上，卻以這樣的方式儲存 10011001 10001111 10101001 00000000 兩者byte擺放的順序恰好相反，若一個不小心，就會解讀為完全錯誤的數值，因此 Endian 一直是計算機系統必須處理的問題，這兒有個連結談到Endians的 歷史由來 。本題就是要做 endian 轉換。 解題策略 C語言可以把 int 當作 char array 來操作，髒，但有效。 int big, little; char * plittle = (char*) &little; char * pbig = (char*) &big; pbig[0] = plittle[3]; pbig[1] = plittle[2]; pbig[2] = plittle[1]; pbig[3] = plittle[0]; 閒聊 感謝蔡神的大一計概。

解題策略: 勾股定理 A 2 +B 2 =C 2 ，或者叫做畢氏定理，符合公式的數對(A,B,C)就叫一組勾股數 (畢氏三元數)。 題目給一個正整數N，要我們找出兩個答案，第一: 0~N之間總共有幾組互質勾股數? 第二: 0~N之間有幾個數完全不屬於任何一組勾股數? 我舉個例子N=10，那麼0~10之間可以找到兩組勾股數(3,4,5)與(6,8,10)，其中只有(3,4,5)一組互質，所以第一個答案是1。再來，3,4,5,6,8,10 都屬於某一組勾股數，完全沒用到的數字是1,2,7,9，共四個數，所以第二個答案是4。 解題關鍵在於如何快速找出一堆勾股數。我想就別折騰了，要解這題就要知道勾股數的通解，單純用暴力搜尋鐵定超時。 從 維基百科的勾股數條目 參考來的通解： 給一個任意數對(X,Y)，用以下公式代 A = X 2 - Y 2 B = 2XY C = X 2 + Y 2 得出的A,B,C就是一組勾股數。 若 (X,Y) 恰好互質而且一奇一偶，那麼會得到一組(A,B,C)互質的勾股數。 知道通解後，雙層迴圈跑 (X,Y) 就能找出所有互質勾股數。 找出不屬於勾股數的數字，直接開一個 size=1000000 的陣列來記錄所有出現過的數字 (用array或是bitset都成)。別忘了一點，我們上面只列出互質的勾股數，但是勾股數的任意整數倍也都是勾股數，如(3,4,5) (6,8,10) (9,12,15)，這些數字也都必須列入紀錄。 閒聊 我知道Fermat是費瑪，不過標題看很久才發現P先生是畢達哥拉斯orz，對於世界第一的先生(Runtime 0.008秒 by Java)，感到由衷的敬佩。

解題策略 題目要求依照第一個陣列的值來排列第二個陣列，照著直覺來寫並不困難。 不過我這兒要提另一個比較狡猾的做法。首先我把第一個陣列叫作pos，pos是一個位置的對應表，告訴你元素排列的新位置。比方說 pos[5] = 3 意思是原本陣列第五個元素應該要移到位置三去。 假如我們翻轉陣列 pos 的 key 與 value，例如把 pos[5] = 3 變成了 pos'[3] = 5，意義上沒有變化: 位置三應該擺放未排列前的舊陣列的第五個元素，但是對程式來說就很方便了，因為我們可以直接依據pos'輸出新陣列，而不需要先經過排序: for(int i=0;i<len;++i){ cout << data[ pos[i] ] <<'\n'; } 好了，那現在問題就是題目給的測資是pos，我們該怎麼產生這個key/value翻轉的 pos' 對應表呢 ? int index=0; int x; while( cin>>x ) { pos[x-1] = index; //index shift index++; if( cin.get()=='\n') break; } 其中一個好辦法是把key/value翻轉過來讀取，原本的pos[index] = x 變成 pos[x] = index;。那個x-1是因為題目給的測資是1起算，而C語言陣列是0起算。一旦 pos' 建好，資料讀取完畢後就能直接輸出結果了，中間省去一道排序的工作。 注意 雖然題目說第二個陣列是浮點數陣列，但是最好當成字串來處理，省得應付格式麻煩。範例測資 : ------Input------ 2 3 1 2 32.0 54.7 -2 1 3 2 4 .004 +5.0e0 0.000007 3 ------Output------ 54.7 -2 32.0 .004 0.000007 +5.0e0 3 本題讀取時有許多空行，輸出時也要求每個case「之間」要有空行，要小心處理這些空行。 碎碎念 原本我第一次也是乖乖排序，後來在網上看見這招手法，想說非學起來不可。

解題策略 計算兩數相加總共需要多少次進位，用一般大數加法的技巧，數一下進位次數就行了。 //big number a + b int carry_count = 0; for(int i=0;i<MAX_LEN;++i) { a[i] = a[i] + b[i]; if( a[i] > 9 ){ a[i] = a[i] - 10; a[i+1]++; carry_count++; //數數進位幾次... } } 注意 輸出時要注意名詞的單複數，總共有三個狀況0、1、其他，別忘了判斷喔。 if(carry_count == 0) printf("No carry operation.\n"); else if (carry_count == 1) printf("1 carry operation.\n"); else printf("%d carry operations.\n", carry_count); 碎碎念 輸出句子最後忘了打句號所以吃了兩次WA....

解題策略 組合公式: C(n,r) = n! / (n-r)!r! 直接使用組合公式來計算結果就可以了。 必須注意的就是階乘的成長速度極快，14! 的值就已經超出long的範圍，更別說第一個範例測資 C(100,6)，100!保證爆掉。所以不能分開計算分子分母最後再相除，要在迴圈中邊乘邊除，壓低計算過程中的數字。 注意 要用浮點數，因為除法會產生小數點。ZeroJudge的測資更嚴苛些，想通過最好把變數精確度提高到long double。而long double與printf溝通的代號是%Lf 碎碎念 偷懶寫的遞迴解法，果然製造 Time Limit Exceeded。自己測了一下，C(34,20)要跑個十來秒，數量級成長很恐怖呀。(汗)

解題策略 因為瓶子的顏色總共只有三種：B、G、C，所以直接手動將六種排列方式列出，並一一計算每種方法的移動次數即可。 注意 本題的I/O量非常大，所以使用cin/cout與scanf/printf之間的速度差距很明顯。我解這題用cin/cout的執行時間是0.420秒，換為scanf/printf後的執行時間則是0.230秒，幾乎要快上一倍，cin之效能殺手令我印象深刻。 碎碎念 這題花了不少時間debug，找到bug之後只有囧一個字可以形容，就是totalGlasses進迴圈前忘了歸零，栽在這種智障 bug上...。提醒我以後一定要謹守編程的好習慣: 「永遠在變數需要被用到的最內層區塊才宣告並初始化該變數。」

解題策略 這題是這樣的，要把輸入的數字反轉，例如1357變成7531，然後與原數相加。直到這個數字變成迴文(palindrome)為止，像是1357+7531=8888，8888就是一個迴文。本題只需要按照著要求計算即可，唯一比較技巧是反轉一個整數 int：reverse() 注意 需要注意變數範圍：至少要 unsigned long 才能容納題目的數字範圍。而printf()、scanf() 與 unsigned long 打交道的代號是%lu。 爭議點 這題有個爭議點是第一個數字到底需不需要判斷回文，舉個例子： 輸入2，那麼該輸出0 2或者1 4？舊版的UVa測資要求必須要輸出1 4，這有些不合常理，新版則是把爭議性測資都拿掉了，所以兩種寫法都能AC。但是在zerojudge.tw上就必須輸出1 4才行。 PS.這題我不小心把某個unsigned long打成int，抓了好久的bug。

解題策略 典型的Binary Tree的題目，牽涉到兩個跟Binary Tree相關的動作 我們知道只要有 inorder + postorder 就可得唯一的一棵 binary tree。那該怎麼把樹建起來呢 ? 我寫在 build_tree()裡。 樹建起來之後，該怎麼走這顆樹，才能找出最小路徑呢? 這我寫在 do_summing( ) 函數，遞迴往下累加總和，再回傳最小的樹葉回來。 Tree 天生就是遞迴結構，用遞迴來寫再自然不過了。 注意 Tree原本應該是NULL的地方，我都掛了外部點(External Node)，這樣會讓程式碼清爽一些。

解題策略 相當有趣的題目，要旋轉字串90度再印出。注意字串不足的部份要自行補白。 提供一個測資： aaa aaa bbb bbb cccccc dddd ee f f g g h h

解題策略 這題要找出字串中的最小週期，我的作法比較好玩一些。 首先用兩個指針i,j分別指向字串的頭兩個字母，像這樣： abcdabcd ↑↑ 我的基本想法很簡單，讓i,j之間保持一個固定間距，如果這個間距就是週期，那麼且同步往後移動指針，比對字母，i,j指的兩字母應該要一直都相同。 # 例子:不管何時，兩指針的字母皆同。 abcabcabc ↑ ↑ abcabcabc ↑ ↑ abcabcabc ↑ ↑ 那麼我們的任務就是找出i, j 的間距啦。初始從週期值1開始比對兩字，不同表示尚未找到週期，拉開指針的間距一格 (++j) 。直到兩字相同 buf[i]==buf[j]，這時候可能就是字串中的週期出現了，同步移動指針 (++i,++j) 持續往後比對。 這個作法有兩個Special case要考慮 字串只有一個字母的時候(長度為1)，兩根指針還能指去哪，直接return 1。 有時候字串尾巴會出現一些破壞週期的字母，例如：abcabcabc d ，或者hoha ho 。所以最後必須檢查找到的週期，跟字串長度是否恰好是倍數關係。若不能整除就表示有這種討人厭的破壞字母出現了，週期值直接等於字串長度。

解題策略 慶祝新書入手，解了書中第一題噴題。盯著鍵盤建好Ascii對應表：如 map['W'] = 'Q'，注意空格跟換行不需要換字。

Dynamic Programming的基本題 LCS DJWS的LCS筆記 洪朝貴老師的動態規劃講義 這題我寫了兩種解法 LCS() 是一般的作法，最清楚直接。 LCS_save_memory() 是針對記憶體優化過的算法。 這題唯一要小心的點就是UVa的字串中包含空格。

解題策略 給一張藏寶圖，記載著如何找到寶藏的指令，要算出最終寶藏的確切位置跟及離出發點的距離。這題是典型的模擬題，照著題目要求在平面座標上四處移動就行了。 我在兩個地方稍微傷了點腦筋 這題的input parsing不好做，或者說用c++ std IO有點麻煩。 operator>>切字串時不能選擇delimeter，用getline 來切也不能設定超過一個delimeter，可是這題偏偏就有兩個-逗點跟句點。我不想自己切，最後就把字串內的逗點跟句點都換成空白，這樣就能用上stringstream了。 浮點數誤差：這題送去ZJ後，我拿到一個WA結果如下 您的答案為: The treasure is located at (0.000,-0.000). 正確答案為: The treasure is located at (0.000,0.000). 怎麼會有負零呢!?  應該不是負零，是個非常非常小的負數，因為浮點數不夠精確才產生的誤差，加上一個EPS修正就行了。(不過事實上我對EPS的觀念還不是很懂..orz) 解決這兩項大概就沒問題了，AC get。

解題策略 爛題目，首先光題目就誤導人了，這題不是Ackermann function ，是 3n+1 ，我還特別跑去確認 Ackermann function 的樣子。 然後兩個很爛的陷阱 (題目敘述沒明說) 1. 有可能 L>H。而最後輸出時必須交換成L<=H ，這跟 UVa 100 3n+1 不一樣。 2. 題目說範圍不會超過long的真正的意思是unsigned long，所以一般 int 會吃WA。 被細節弄得很火。 提供測資 ==input== 2000 3000 3000 2000 0 0 ==Output== Between 2000 and 3000, 2919 generates the longest sequence of 216 values. Between 2000 and 3000, 2919 generates the longest sequence of 216 values.

解題策略 這題的解法很直接，要找d=a+b+c 用四層迴圈下去跑a,b,c,d就好了 XDDDD 我犯了幾個錯誤 要找最大符合d (意思是數列中可能出現好幾個符合要求的解)，所以迴圈應該由最大元素往下找，第一個找到的解就是答案，我一開始由最小元素往上遞增尋找，拿了WA。 沒找到解就回傳0，殊不知0也有可能是解: 0 = -5 + 3 + 2，這裡也吃了一個WA，所以我後來改回傳 INT_MAX 作為無解。 這題有負值，所以 -5 = -10 + -2 + 7 ，這樣算一組合法的解。 是比較需要小心的地方。 官網論壇上的(a+b)=(d-c)法，方法複雜很多，卻沒有比較快。

跟 147 、 674 同樣的題目，順便就吃下來啦 我發現IE會讓我的程式碼排版亂掉，真讓人困擾@_@

典型的DP題，沒有玩什麼花招.. Sagit's C++ 動態規劃 我想我就不需要多解釋了

....

解題策略 有關圓形體積的小題目，稍微推導一下即可。 注意 n == 1 是特例要處理。變數記得開long long。

之前解的，忘了貼上來。 這是個典型的Dynamic Programming問題。 可是我忘記遞迴式是什麼了..囧 改天補上