SPOJ Problems Solved

张文泰 posted @ 2010年3月20日 07:34 in Art of Science with tags SPOJ , 4005 阅读
  • 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]

本作品遵循“署名-非商业性使用-相同方式共享 3.0 Unported”协议,转载请注明来自richard-desktop
Creative Commons License

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter