HDU 1251 統計難題

要看論文準備畢業設計了，好幾周都沒有搞ACM了，今天實在手癢了，就去hdu上溜達了一圈，挑幾個題做，于是乎就看到了這個題，典型的字典樹。

題目要求輸出以某個字符串為前綴的word的數目，建立字典樹之后就是個簡單的查詢了，為了性能采用了靜態字典樹，由于不知道會有多少個單詞就猜了下感覺10w應該夠了吧，提交上去access violation，明顯的越界訪問，修改為20W一樣出錯，后來火了，直接開到50w過了，測試數據相當狠呀。

不多說了，參考代碼如下。

ZOJ 1808 Immediate Decodability

       這道題給出n個有1和0組成的字符串集合，然后要求判斷是否有某一個字符串是另一個字符串的前綴。是字典樹的典型應用。

       字典樹有靜態和動態之分，動態字典樹就是在插入時根據需要動態malloc節點，而靜態字典樹則是事先開辟一個較大的數組，然后設置一個變量index指向當前數組中未被占用的節點下標的最小值，即下一個可用節點的下標。跟C語言中實現靜態鏈表類似。這兩種方法各有優劣，動態字典樹理論上可以插入任意多個節點，但是每次的malloc及最后的free會消耗很多時間。而靜態字典樹省去了內存的動態申請和釋放，節省了時間，但是可以插入節點數目受到事先開辟的數組大小限制，可擴展性較差。具體采用哪種實現方式根據需求而定。就本題而言時間要求1s，可以初步需要插入的判斷節點數目不會太多，因此為了提高運行速度采用了靜態字典樹。

       參考代碼如下：

ZOJ1058 Currency Exchange

       水題一道，唯一需要注意的是題目中說只能取到貨幣的百分之一，因此在每次進行貨幣匯率轉換之后都要進行處理，WA了一次就是因為到最后輸出的時候才四舍五入，這個操作應該在每次轉換匯率后都進行。

       參考代碼如下：

ZOJ 1334 Basically Speaking

       這是一道簡單的進制轉換題，也是一道讓我無語的題。

       題目大意較為簡單，但是提交了n次，一直PE，檢查了好多地方，實在感覺沒頭緒了，就活馬當死馬醫，把printf(“%*c”, len, ‘ ’)換成了循環，因為要右對齊，所以輸出些空格，竟然AC了，竟然是對printf的這種輸出格式理解有誤，無語呀。

       參考代碼如下：

ZOJ 1051 A New Growth Industry

       這道題嚴格來說屬于一道簡單的模擬題，但是題目描述的太繁瑣了，影響了理解。而一旦看懂題意后就好辦了。

       這道題的大意就是說在一個20X20的方格中養一種細菌，這種細菌的DNA被改造了，周圍密度大時，繁殖減慢，密度減少，反之密度增加，且數量變動大小由DNA序列決定，然后根據輸入進行模擬，輸入n天后的情況。

       題就這么簡單，但是需要注意的是不能計算完一個方格的變化量之后立刻改變該方格的值，因為周圍的方格k值還需要引用當前的密度值。唯一可以使用的技巧就是把數組開大點，題目是20X20，可以開到22X22，只使用下標1-20來表示題目中的方格，這樣在計算時就不用判斷是否越界了，可以節省一些時間。

       參考代碼如下：

DNA Sorting(ZOJ 1188)

本題應該來說是一道比較容易的題，但是我覺得確實一道比較好的題：為了解決這道題可以寫很短的代碼，也可以寫很長的代碼；可以寫出比較高效的代碼，也可以寫出比較低效的代碼。

原題大家可以到ZOJ上查看，本處就不累述了。題目大意就是根據一個由ATCG字符組成的字符串的逆序數進行排序，然后輸出結果，如果有兩個字符串的逆序數相同則按照其輸入順序輸出，即要求排序函數是穩定的。至此，本題的思路已經很清晰了：接收數據à計算逆序à排序à輸出結果。

這里關鍵步驟是排序，要求穩定排序，因此C語言中的qsort和STL中的sort不再適用，而要自己編寫排序函數或者適用STL中的stable_sort。字符串逆序數的計算可以在輸入以后計算，也可以在輸入的同時就計算，根據接收字符串的方式而定，如果是整行接收的，只能以后再算了；如果是逐字符接收的，則可以邊接收邊計算。此處為了方便處理采用了整行接收的方法。具體代碼如下：

該題在ZOJ上的題號是1225。

題目描述如下：

Background
In this problem you will be given a series of lists containing both words and numbers. The goal is to sort these lists in such a way that all words are in alphabetical order and all numbers are in numerical order. Furthermore, if the nth element in the list is a number it must remain a number, and if it is a word it must remain a word.
Input
The input will contain multiple lists, one per line. Each element of the list will be separated by a comma followed a space, and the list will be terminated by a period. The input will be terminated by a line containing only a single
period.

Output

For each list in the input, output the scramble sorted list, separating each element of the list with a comma followed by a space, and ending the list with a period.

Sample Input

0.
banana, strawberry, OrAnGe.
Banana, StRaWbErRy, orange.
10, 8, 6, 4, 2, 0.
x, 30, -20, z, 1000, 1, Y.
50, 7, kitten, puppy, 2, orangutan, 52, -100, bird, worm, 7, beetle.
.
Sample Output

0.
banana, OrAnGe, strawberry.
Banana, orange, StRaWbErRy.
0, 2, 4, 6, 8, 10.
x, -20, 1, Y, 30, 1000, z.
-100, 2, beetle, bird, 7, kitten, 7, 50, orangutan, puppy, 52, wor

         本題不是難題，根據題意，只需把輸入中的數字和字符串分開，然后分別按照相應的規則進行排序，并記錄下第i個是數字或者是字符，最后按照記錄情況一次輸出相應的元素即可。因為需要對字符串數組進行排序，因此第一印象是使用C++的string和STL中的sort函數，但是結果卻因為懶得寫一個排序函數多寫了很多代碼。

具體代碼如下：

Fibonacci Again

【題目描述】

There are another kind of Fibonacci numbers: F(0) = 7, F(1) = 11, F(n) = F(n-1) + F(n-2) (n>=2)
Input
Input consists of a sequence of lines, each containing an integer n. (n < 1,000,000)
Output
Print the word "yes" if 3 divide evenly into F(n).
Print the word "no" if not.
Sample Input
0
1
2
3
4
5
Sample Output
no
no
yes
no
no
no

這道題應該說是很簡單的題，如果說考察了什么知識點的話時能說是（a+b）%n = (a%n + b%n)%n，但是這個題卻有多種思路，可以從很多方面優化，比較有意思。

【解題思路1】：

最簡單的思路,開一個大小為n的數組，初始化為0，遍歷一遍，如果某一項滿足條件則設置為1，就不多說了，代碼如下：

這個提交上去，由于執行時只查表，時間不算多10ms，但是內存消耗不小。下面看幾種優化的方法。

【思路2】

這種題一般情況下會有規律。把前幾個能被3整除的數的下標列出來一看，規律就出現了：2 6 10 14…，這就是一個等差數列嘛，這就好辦了，an = a1 + (n-1)*4,那么an-a1肯定能被4整除。代碼如下：

該解法如果說還可以優化的話，那只能把取余運算變為位運算了。

if ((n-2)&3)

                     printf("no\n");

              else

                     printf("yes\n");

【思路3】

如果把數列前幾項的值列出來，會發現數組中每8項構成一個循環。這也很好辦。

代碼如下：

其實這個還可以優化，我們仔細觀察可以看到這些滿足條件的下標有一個特點：

N%8 == 2或者n%8==6

代碼如下：

Counterfeit Dollar

該題ZOJ題號為1184， POJ題號為1013.

題目描述如下：

Sally Jones has a dozen Voyageur silver dollars. However, only eleven of the coins are true silver dollars; one coin is counterfeit even though its color and size make it indistinguishable from the real silver dollars. The counterfeit coin has a different weight from the other coins but Sally does not know if it is heavier or lighter than the real coins.

Happily, Sally has a friend who loans her a very accurate balance scale. The friend will permit Sally three weighings to find the counterfeit coin. For instance, if Sally weighs two coins against each other and the scales balance then she knows these two coins are true. Now if Sally weighs one of the true coins against a third coin and the scales do not balance then Sally knows the third coin is counterfeit and she can tell whether it is light or heavy depending on whether the balance on which it is placed goes up or down, respectively.

By choosing her weighings carefully, Sally is able to ensure that she will find the counterfeit coin with exactly three weighings.

Input
The first line of input is an integer n (n > 0) specifying the number of cases to follow. Each case consists of three lines of input, one for each weighing. Sally has identified each of the coins with the letters A-L. Information on a weighing will be given by two strings of letters and then one of the words ``up'', ``down'', or ``even''. The first string of letters will represent the coins on the left balance; the second string, the coins on the right balance. (Sally will always place the same number of coins on the right balance as on the left balance.) The word in the third position will tell whether the right side of the balance goes up, down, or remains even.

Output
For each case, the output will identify the counterfeit coin by its letter and tell whether it is heavy or light. The solution will always be uniquely determined.

Sample Input

1
ABCD EFGH even
ABCI EFJK up
ABIJ EFGH even

Sample Output
K is the counterfeit coin and it is light.

【分析】該題屬于枚舉范疇。沒有比較巧妙的可以一步到位求出結果的方法，可以一次枚舉這12枚錢幣，假設其為假，然后代入到3次稱量判斷中，如果使三次判斷都成立且判斷結果相同，那么毫無疑問這枚錢幣是假的。首先可以進行預處理，比較結果為EVEN的可以判定兩邊的錢幣都是真的，不必參與到枚舉中來。對于上面的輸入用例，假設K是假的，代入判斷1，k不出現，那么兩邊重量應相等，成立。繼續稱量2，k出現在右邊，結果是UP，亦成立，且據此知道k是較輕的，因此k在右邊，而天平右邊翹起。下面進行判斷3

，k沒有出現在天平兩邊，而且結果為even成立。通過三次稱量判斷，且結果一致，可以肯定k就是假幣，且較輕。為了說明為題，對于上例假設L是假幣。代入稱量1，L不出現，結果even成立，稱量2，L不出現，結果為up不成立，因為只有一枚假幣，現假設L為假幣，而在L不出現的情況下天平不平衡，故L不是假幣。按照上述算法進行枚舉，遇到可以肯定是假幣的貨幣時算法終止。

       需要注意的是當假設一枚硬幣為假且通過三次稱量時，需要判斷三次稱量k的輕重情況是否一致，如果一次推得該硬幣較輕，而另一次卻判斷該硬幣較重，那么該硬幣肯定不是假幣。在判斷是需要注意當左右兩邊都不出現假設為假的硬幣時，需要特殊處理，不能簡單的比較3次硬幣輕重是否相同，在左右兩邊都不出現該硬幣的情況下，不應該把這次測量納入比較的范疇。除此之外需要的就是細心了，本人因為打印的時候多打印了個the，WA了6次，檢查了半個多小時，有種欲哭無淚的感覺。

具體代碼如下：