SPOJ题目及题解.docVIP

1 TEST Life, the Universe, and Everything 题意：不断地从输入中读取数字，直到遇到42就停止。 算法：题意就是算法。 时间复杂度：和输入同阶 个人觉得这题比A+B问题出得有意思多了，呵呵，既让大家熟悉了多数据处理，又显得名字很牛(知道42的来历的人看到题目都会会心一笑吧:D 2 PRIME1 Prime Generator 题意：给定L和R，生成所有L和R之间的质数。 时间复杂度：O((R-L)*R^0.5) 算法：先算一个40000以内的质数表，然后枚举范围内每个数并测试。 3 SBSTR1 Substring Check (Bug Funny) 题意：24组数据，每组都是给定一个长度为10和一个长度为5的01串，对于每组数据输出一行1（可以匹配）或者0（不能匹配）。 限制：只能使用whitespace, brainf**k和intercal语言。 时间复杂度：可能是O(n3) 算法：虽然题目很弱智，但是看这个语言限制……我选择的是brainf**k，下面介绍一下我的算法： 把数组以10个元素为一个单元来考虑，第一个是循环变量i，第二个是循环变量j，第3列是串A，第6列是串B，第9列和第10列分别表示当前偏移量的匹配情况和全局的匹配情况。 简介循环的方法： 比如要循环10次，可以这样： ++++++++++（循环变量置为10） [-[+-] …… ]（每次循环变量减一，然后把循环变量移到下一个单元，处理当前单元，然后把指针移到下一个单元） 然后还有一个小问题，就是怎么方便地写”if *p!=0 then …”。我的解决办法是：把当前位置（p指向的位置）的后两个元素设为缓冲区，即*(p+1)=0, *(p+2)=1，然后，可以用 [……] 即，如果if被执行了，指针最终会移到p+1。 然后再执行 [] 可以保证自己落在p。 有了这两个工具，就相当于有了for和if，再实现起来就不困难了( 4 ONP Transform the Expression 题目：给定一个四则运算外加乘方组成的算式，输出对应的逆波兰表达式（后缀表达式）。 时间复杂度：O(L) 算法：栈模拟 5 PALIN The Next Palinfrome 题目：给定一个整数，求出比它大的最小回文整数 时间复杂度：O(L)，L是位数 算法：用这个数的前一半生成后一半，看看够不够大，如果不够大就加一再生成一遍。 6 ARITH Simple Arithmetics 7 BULK The Bulk! 8 CMPLS Complete the Sequence! 9 DIRVS Direct Visibility 10 CMEXPR Complicated Expressions 11 FCTRL Factorial 12 MMIND The Game of Master-Mind 13 HOTLINE Hotline 14 IKEYB I-Keyboard 15 SHPATH 16 TETRA 17 CRYPTO1 18 CRYPTO2 19 CRYPTO3 20 CRYPTO4 The Bytelandian Cryptographer (Act IV) 22 TRICENTR 23 PIR 24 FCTRL2 25 POUR1 26 BSHEEP 27 SBANK 28 HMRO 29 HASHIT 30 BLINNET 31 MUL 32 NHAY 33 TRIP Trip 34 RUNAWAY Run Away 35 EQBOX Equipment Box 36 CODE1 Secret Code 37 PROPKEY The Proper Key 38 LABYR1 Labyrinth 39 PIGBANK Piggy-Bank 40 STONE Lifting the Stone 41 WORDS1 Play on Words 42 ADDREV Adding Reversed Numbers 43 BOOKS1 Copying Books 44 SCYPHER Substitution Cipher 45 COMMEDIA Commedia dell Arte 47 SCRAPER Skyscraper Floors 48 BEADS Glass Beads 49 HAREFOX Hares and Foxes 50 INCARDS Invitation Cards 51 TOUR Fake tourna