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次，检查了半个多小时，有种欲哭无泪的感觉。

具体代码如下：