調和的靈感

解題背景 這題是傳說中的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上...。提醒我以後一定要謹守編程的好習慣: 「永遠在變數需要被用到的最內層區塊才宣告並初始化該變數。」

這次『四大天王』阿嘉莎。克莉絲嘗試了新的故事風格，但看完後我實在沒辦法說精彩。 本次白羅老爹的對手是一個呼風喚雨的跨國地下犯罪集團，而白羅則從一個只會動灰色腦細胞的老頭，搖身一變成了詹姆斯龐德，上山下海，拯救世界。看得出來克莉絲蒂想突破以往的格局，寫一個超大背景的故事。 整個劇情也就像一部動作電影一樣，突發事件一個接一個往主角白羅撲來。每個事件單獨來看都很玄奇，但是整體來看關聯卻很薄弱，好像互不相干的獨立事件。書中說這些行動都是由幕後主使「四大天王」策動，但這樣零散缺乏組織的攻擊行動，我真的很懷疑這四大天王的腦袋能力阿。最讓我吐血的一點，最終隱藏大頭目：四大天王中的一號，李長彥，從頭到尾沒有露過臉，結局突然就自殺了。除了四號來去無形，殺人技巧不錯，他兩位沒有什麼特別作為。整個故事就在誇張不合理的事情與差勁的敵人之中莫名其妙的結束了。 其實看到開場白羅與海斯汀重逢的那一小段，我發現這位克莉絲蒂還是我們熟悉的克莉絲蒂，她寫的人際互動非常有魅力，非常有趣，可惜這次故事不巧挑中了一個不擅長的路線。