SPOJ Problems Solved

张文泰 posted @ 2010年3月20日 07:34 in Art of Science with tags SPOJ , 5462 阅读

1 - Life, the Universe, and Everything[TEST]
模拟题，只需要按照要求做就可以了。
2 - Prime Generator[PRIME1]
先用筛法求出 $\sqrt{n}$ 范围内的质数，然后对指定的区间再使用筛法就可以了。不需要特别的优化。
4 - Transform the Expression[ONP]
中缀转后缀，经典问题，用栈操作就可以了。
5 - The Next Palindrome[PALIN]
只需要提取出前半部分，然后累加再判断是否符合要求就可以了。
6 - Simple Arithmetics[ARITH]
注意到水平线的长度只和直接相邻的上下两行有关。
8 - Complete the Sequence![CMPLS]
见SPOJ 8 - Complete the Sequence![CMPLS]。
10 - Complicated Expressions[CMEXPR]
利用中缀转后缀的结果进行去括号是比较稳妥的做法。分析表达式树也是可行的。
11 - Factorial[FCTRL]
简单题。
14 - I-Keyboard[IKEYB]
见SPOJ 14 - I-Keyboard[IKEYB]。
15 - The Shortest Path[SHPATH]
见SPOJ 15 - The Shortest Path[SHPATH]。
16 - Sphere in a tetrahedron[TETRA]
见SPOJ 16 - Sphere in a tetrahedron[TETRA]。
22 - Triangle From Centroid[TRICENTR]
平面几何题。我们先求出基本的三边长、三条高的长度。然后，建立坐标系，算出外心的坐标。由欧拉线的性质可知，重心到外心的距离是重心到垂心距离的一半，所以可以得到答案。
23 - Pyramids[PIR]
与TETRA一题方法一样。
24 - Small factorials[FCTRL2]
简单题。
25 - Pouring water[POUR1]
见SPOJ 25 - Pouring water[POUR1]。
27 - Sorting Bank Accounts[SBANK]
就是简单的排序，用gets()应该可以保证不会超时。
29 - Hash it![HASHIT]
Hash表的简单应用。
31 - Fast Multiplication[MUL]
高精度乘法，可以使用FFT等算法。其实直接压位也可以过。
32 - A Needle in the Haystack[NHAY]
KMP算法就可以过了。不过如果按照题目中给的提示，采用动态内存分配程序似乎有点慢。
33 - Trip[TRIP]
动态规划，没什么难度。
39 - Piggy-Bank[PIGBANK]
背包问题，动态规划解决之。
40 - Lifting the Stone[STONE]
求多边形的重心，一般采用三角剖分做，剖分的中心点往往是原点。
42 - Adding Reversed Numbers[ADDREV]
简单题。
54 - Julka[JULKA]
简单题。
375 - Query on a tree[QTREE]
见SPOJ 375 - Query on a tree[QTREE]。
861 - Counting inversions[SWAPS]
见SPOJ 861 - Counting inversions[SWAPS]。
1644 - Trees[TREEOI14]
见SPOJ 1644 - Trees[TREEOI14]。