SPOJ Problems Solved
张文泰
posted @ 2010年3月20日 07:34
in Art of Science
with tags
SPOJ
, 5565 阅读
- 1 - Life, the Universe, and Everything[TEST]
模拟题,只需要按照要求做就可以了。 - 2 - Prime Generator[PRIME1]
先用筛法求出范围内的质数,然后对指定的区间再使用筛法就可以了。不需要特别的优化。 - 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]。
本作品遵循“署名-非商业性使用-相同方式共享 3.0 Unported”协议,转载请注明来自richard-desktop。