ACM POJ 总结

ACM POJ 总结：

注意点：
1. 一定要测试临界情况 (一定要参考每题后的讨论，1598 的血泪教训) 后再提交。
2. 要仔细！输出格式别弄错了 (参考 1918) ！
3. 注意循环的边界条件。有一些错误，并不是每次都会造成错误的结果，而是时而对，时而错。比如，数组越界，而循环又要依赖数组元素来判断是否结束时。参考本题的前两次提交代码 (1591) 。
4. 编译器对数组元素个数是有限制的。Windows 下的 gcc 限制数组元素个数小于 1000000 (1706, 2215) 。
5. Linux 和 Windows 下 gcc 对数组元素个数的限制不一样 (2215) 。

经验：
1. 如果多次优化后仍超时，有可能是程序在临界情况下有死循环。
2. 预防运行时期错误：
1) / 运算和 % 运算时注意除数为 0 的情况。
2) 注意数组下标是否越界。
3. 如果需要多次重复计算特定序列的特定幂 (比如本题中 2 到 100 的立方)，可以算一次然后储存之，用时直接枚举。这样可以大大节省时间！
4. 如果求幂运算中的指数固定 (比如，只是求平方或立方)，且比较小 (比如，不大于 5)，则尽量不要用 pow 函数。
5. 运行时期错误的可能原因：
指针地址非法，数组地址越界，scanf 参数没加取地址符。
6. 用 %.0f 输出浮点数为整数会对该浮点数进行舍入；而强制转换为整型则是直接取整。

---------------------------------------------------------------------------

POJ 1001

测试数据：

95.123 12
0.4321 20
5.1234 15
6.7592 9
98.999 10
1.0100 12
0001.1 2
1.1000 2
10.000 2
000.10 2
000095 2

---------------------------------------------------------------------------

POJ 1002

1. 尽量用 C 风格字符串，不用 string。
2. 尽量不用复杂的数据结构，比如类。参考 1。

---------------------------------------------------------------------------

POJ 1006

1. 数学很重要。
2. 相关数学知识：
1) 中国剩余定理。
例：
一数除以 3 余 2，除以 5 余 3，除以 7 余 2，求符合该条件的最小正整数。
首先找出能被 5 与 7 整除而被 3 除余 1 的数 70，被 3 与 7 整除而被 5 除余 1 的数 21，被 3 与 5 整除而被 7 除余 1 的数 15。
所求数被 3 除余 2，则取数 70×2 = 140，140 是被 5 与 7 整除而被 3 除余 2 的数。所求数被 5 除余 3，则取数 21×3 = 63，63 是被 3 与 7 整除而被 5 除余 3 的数。所求数被 7 除余 2，则取数 15×2 = 30，30 是被 3 与 5 整除而被 7 除余 2 的数。
140 + 63 + 30 = 233，再对 3、5、7 的最小公倍数 105 取模得 23，故结果为 23。
2) 求最大公约数的辗转相除法。
辗转相除法在求出两数 a 和 b 的最大公约数 n 的同时，还能求出满足 ax + by = n 的 x 和 y。
例：
a = 23, b = 28
28 = 23 × 1 + 5
23 = 5 × 4 + 3
5 = 3 × 1 + 2
3 = 2 × 1 + 1
2 = 1 × 2 + 0
故最小公约数为 1。再求 x 和 y (由上述结果由下而上逆推)：
1 = 3 - 2 × 1
= 3 - (5 - 3 × 1) × 1
= 3 × 2 - 5
= (23 - 5 × 4) × 2 - 5
= 23 × 2 - 5 × 9
= 23 × 2 - (28 - 23 × 1) × 9
= 23 × 11 - 28 × 9
故 x 为 11，y 为 -9。

测试数据：

24 29 34 0
24 29 34 1
24 29 34 2
0 0 0 0
0 0 0 100
5 20 34 325
4 5 6 7
283 102 23 320
203 301 203 40
-1 -1 -1 -1

---------------------------------------------------------------------------

POJ 1012

此题不超时的关键在于找 m 时的技巧。
一：m 的取值。
考虑只剩 k+1 个人时的情况，这时候 m 如果不是 k+1 的倍数或 k+1 的倍数加一，则显然不满足题意。因此 m 只能是 k+1 的倍数或 k+1 的倍数加一。
二：找下一个被杀的人时不能直接加 m，否则肯定超时。应该加 m%alive (如果 m%alive 为 0 的话就加 alive)，这里 alive 是剩下的人数。

---------------------------------------------------------------------------

POJ 1013

测试数据：(请注意第三组数据)

3
ALCD EFGH even
ALCI EFJK up
ALIJ EFGH even
A B even
A C down
E F even
A B down
B C up
G E even

---------------------------------------------------------------------------

POJ 1026

1. 不要舍不得空间。时间重要，该记录时记录，以空间换时间。
2. 只有在保证值在 [-128, 127] 范围内时才可以用 char 变量保存 int 变量。保险的做法是不要用 char 变量保存 int 变量。(因为这个问题在这道题上耗了八个小时 -_-)
3. 一定要测试临界情况 (对于这道题而言是 n=200) 后再提交。要是一开始就测试临界情况，2 中的问题就能早发现了。现在多提交了五次 TLE 的情况 (都是在临界情况下死循环 -_-)，郁闷。吸取教训！

测试数据：(注意第二个 Hello Bob 前面的空格)

200
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 1
1 Hello Bob
1 Hello Bob
1995 CERC
0
0

---------------------------------------------------------------------------

POJ 1046

1. 小心输入输出格式。char 可以保存整型值，但是无法用 %d 格式输入整型值。

---------------------------------------------------------------------------

POJ 1107

1. 重申一次：测试临界情况后再提交！因为这个原因 RE 一次。-_-!
2. 预防运行时期错误：
1) / 运算和 % 运算时注意除数为 0 的情况。
2) 注意数组下标是否越界。

---------------------------------------------------------------------------

POJ 1147

题意：
给定一个 N 位的二进制串 b1 b2 ... bN-1 bN，将该串做旋转，即将 b1 移到 bN 后面，得到一个新的二进制串：b2 b3 ... bN-1 bN b1。对新的二进制串再做旋转，得二进制串 b3 b4 ... bN-1 bN b1 b2。重复旋转操作操作，可得 N 个二进制串，对这 N 个串按二进制数大小排序，可得一个 N*N 的矩阵。
问：给定这种矩阵的最后一列，求出矩阵的第一行。

说明：
很有意思的一道题。这道题可以穷举，可以迭代，但效率都比较低。如果解题者善于发现题目的特点，可以得到线性解法，大大提高速度。

注意点：
要求的是第一行，不是第一列。
我一开始看成是第一列，提交出错后才发现是第一行。-_-! 而且这时候还以为第一行跟第一列的结果应该是一样的 (居然没想到 1 不连续的情况，-_-!!)，直到看到别人的解题报告中的例子才真正明白题意。-_-!!!

---------------------------------------------------------------------------

POJ 1218

本题利用完全平方数的性质可以迅速得解。
本题的实质就是求所有满足如下性质的数的个数：小于等于 n 并且相异因数个数为奇数。
而只有完全平方数有奇数个相异因数：因为一个数 n 的因子 m 和 n/m 可以两两配对，所以奇数个因子的数必有某个 m 使 m=n/m => n=m^2。

注意点：
1. 用 %.0f 输出浮点数为整数会对该浮点数进行舍入；而强制转换为整型则是直接取整。

---------------------------------------------------------------------------

POJ 1519

快捷方法：各位之和除以九取余数，若余数为 0 则取 9。
相关的数学原理：十进制数除以九的余数等于各位之和除以九的余数。
令 X=abcdefg 为十进制数。其中 a, b, c, d, e, f, g 各代表 0-9 的一个数。
则
a + b + c + d + e + f + g =
(a * 10^6) % 9 + (b * 10^5) % 9 + (c * 10^4) % 9 + (d * 10^3) % 9 + (e * 10^2) % 9 + (f * 10^1) % 9 + (g * 10^0) % 9 =
( (a * 10^6) + (b * 10^5) + (c * 10^4) + (d * 10^3) + (e * 10^2) + (f * 10^1) + (g * 10^0) ) % 9 + 9 * k = (这里的 k 是非负整数)
abcdefg % 9 + 9 * k =
X % 9 + 9 * k
于是，取十进制数各位之和相当于将该数除以九的余数加上九的某个倍数。
重复该过程将使得后面加上的九的倍数越来越小，最终的结果肯定是：
X % 9 (X % 9 != 0) 或 9 (X % 9 = 0)

---------------------------------------------------------------------------

POJ 1543

1. 如果需要多次重复计算特定序列的特定幂 (比如本题中 2 到 100 的立方)，可以算一次然后储存之，用时直接枚举。这样可以大大节省时间！
2. 如果求幂运算中的指数固定 (比如，只是求平方或立方)，且比较小 (比如，不大于 5)，则尽量不要用 pow 函数。

---------------------------------------------------------------------------

POJ 1591

注意循环的边界条件。有一些错误，并不是每次都会造成错误的结果，而是时而对，时而错。比如，数组越界，而循环又要依赖数组元素来判断是否结束时。参考本题的前两次提交代码。

---------------------------------------------------------------------------

POJ 1598

1. 进一步熟悉标准输入函数 scanf；学习使用字符串分割函数 strtok。
2. Linux 中有 strncasecmp，没有 stricmp；Windows 中都有 (貌似)。

注意点：

1. 本题目中最大的陷阱 (由 hubo430 发现。感谢 hubo430。)：
题目中有这样一句话：All excuses can contain any upper or lower case alphanumeric character, a space, or any of the following punctuation marks [".,!?] not including the square brackets and will not exceed 70 characters in length.
对这句话的理解要注意：can contain 是说可以包含这些，而不是只包含这些！所以嘛，excuses 中还可能包含 ~@#!@$#^&*(()* 这些乱七八糟的符号！他们也是下文说的分割符！

因为这个原因 WA 了三次！还白耗了大半天的时间查错！
对出题人真是无语啊！

2. 要不怕麻烦，肯试。
也怪自己不肯试，之前就看到了这个贴，但就是嫌麻烦没试。导致更大的麻烦！

3. 疑惑点：Linux (Fedora Core 6, Fedora 7) 下单步跟踪正确，但输出就是不对！疯了！

---------------------------------------------------------------------------

POJ 1706

1. 编译器对数组元素个数是有限制的。从本题的经验看，gcc 限制数组元素个数小于 8100000。
2. 疑惑点：Linux (Fedora 7) 下单步跟踪正确，但输出就是不对！
3. 鄙视不说明题意导致浪费大家时间的行为！

---------------------------------------------------------------------------

POJ 1918

第一遍提交时把输出中的英文句点看成了冒号，导致 WA 一次。-_-!

要仔细！

---------------------------------------------------------------------------

POJ 2215

1. 编译器对数组元素个数是有限制的。从本题的经验看，Windows 下的 gcc 限制数组元素个数小于 1000000。
2. Linux 和 Windows 下 gcc 对数组大小的限制不一样。同样是 4000000 B，Linux 下运行正常，而 Windows 下运行时刻出错。

---------------------------------------------------------------------------

POJ 2309

察看 BST 的开始部分：
_______________8______________
_______4_______ ______12______
___2___ ___6___ __10__ __14__
1 3 5 7 9 11 13 15

我们将其转化为二进制表示：
____________1000____________
____0100____ ____1100____
0010 0110 1010 1110
0001 0011 0101 0111 1001 1011 1101 1111

观察二进制 BST，不难得出结论：
以二进制数 X 为根的子树的最小值是将 X 最右之 1 换成 0，再加 1 所得的数；
以二进制数 X 为根的子树的最大值是将 X 最右之 1 右边的 0 全换成 1 所得的数。

---------------------------------------------------------------------------

POJ 2413

测试数据：

4 4
4 5
4 6
5 5
5 6
5 8
0 5
1 5
2 5
0 0

---------------------------------------------------------------------------