解题报告_王波.txt

集合了SOJ（四川大学ACM在线评测系统）众多经典题目的详细解题报告

1002:大数加法。开两个数组，用来存两个加数a,b。如果a>=b,那么加的结果可以放在a里头。反之，则放在b里头。这样可以节约空间。
1003:大数乘法。做法与1002类似。
1005(Move cards):此题带有贪心的算法。从第一堆开始，向后推移。设平均每堆数量为average，如果前n堆的数目小于average*n，则继续向后推移；否则，如果等于average*n，那么则在前n堆里头调整。否则，将多出的移到后面去。
1006(The Hardest Problem Ever):简单的字母代换。
1009(Dollars):此题我郁闷了很久。开始用的是递归。严重超时。然后又用递推，15s可以出结果，但还是超时。最后是用的JB讲的母函数的方法做出来的。假期回去想了想，其实是一道很简单的动规题。结果一做就过了。
1010(Mutant Flatworld Explorers):一道模拟题。只要认真读题就应该做的出来。
1013(The Cat in the Hat):数学题。先按题意，推出公式，再枚举就可以了。
1014(Maximum Sum):此题想了3天。最后终于想出来了。是一道比较经典的动归。最后一次比赛也做到了这道题。从上到下，从左到右。依次累加。求最大。
1019(Unidirectional TSP):经典的动态规划问题。这是我学动归的开门题。后面很多题有这道题影子。
1020(Mutant Flatworld Explorers):和1010一样的题。
1022(Uniform Generator):公式计算题。简单。
1023(Prime Cuts):求素数的问题。开一个数组，把其中的合数划掉。
1025(Integer Inquiry):大数加法
1026(Eeny Meeny Moo):约色夫问题。
1027(Lotto):枚举。
1035(Power Crisis):约色夫问题。
1036(The Dole Queue):约色夫问题。
1039(Greedy Gift Givers):简单模拟加计算。
1043(Joseph):约色夫问题。
1051(palindromes):简单模拟题。
1052(MASH):约色夫问题。
1059(Pi):数学计算题。
1067(Word-Search Wonder):枚举，比较。
1071(The Tower of Babylon):先将各种石块的面积按大小排序，然后使用动规。
1072(The Circumference of the Circle):简单数学题。
1082(不甘心的皇后):我先是用的搜索，然后听袁原讲了，实际是一道动规。
1084(滑雪比赛):动态规划。
1090(Dick and Jane):比赛的时候没把他做出来。我觉得是有公式的。但是总是通不过。下来以后是用的枚举过的。
1092(欧几里得算法):比赛的时候，已经把其中一种情况做出来了。但是另一种情况始终不行。最后听何巍讲了以后，立刻就明白了，只要减一下就行了。
1103(IP判断):主要是sscanf()的用法。
1113(排队):动态规划。
1114(数字三角):动态规划。
1115(阶乘):数学计算。注意超界，处理好尾数。
1116(回文数):简单模拟题。
1117(最大整数):贪心算法。我用的是近似排序的方法。先将两个字符串a,b按ab和ba这样组合，然后比较ab,ba的大小。然后就近似选择排序。
1118(上车人数):简单计算题。
1120(01串压缩编码):简单模拟。
1133(Billiard):此题用的是物理上的镜象原理。将一个矩形扩展成几个矩形，然后在计算。
1135(Choose and Divide):此题是数学计算题。问题的关键是解决好超界的问题。
1177(T9):简单模拟。