竞赛总览
CSDN 编程竞赛五十六期：比赛详情 (csdn.net)
竞赛题解
题目1、因数-数字游戏
小Q的柠檬汁做完了，掏出了自己的数字卡牌，想和别人做数字游戏，可是她又不想要输掉游戏。她制定好规则，每次每个人只能把这个牌换成它的因子的某个牌。但是这个因子不能是1或者整数本身。现在给出整数n，两个人开始做游戏，先手在最优策略状态下能否必胜。
第十四期竞赛原题。
题目2、津津的储蓄计划
津津的零花钱一直都是自己管理。每个月的月初妈妈给津津三百元钱，津津会预算这个月的花销，并且总能做到实际花销 和预算的相同。为了让津津学习如何储蓄，妈妈提出，津津可以随时把整百的钱存在她那里，到了年末她会加上百分之二十还给津津。因此津津制定了一个储蓄计划：每个月的月初，在得到妈妈给的零花钱后，如果她预计到这个月的月末手中还会有多于一百元或恰好一百元，她就会把整百的钱存在妈妈那里，剩余的钱留在自己手中。例如，月初津津手中还有95元，妈妈给了津津300元。津津预计11月的花销是170元，那么她就会在妈妈那里存200元，自己留下195元。 到了月末，津津手中会剩下25元钱。津津发现这个储蓄计划的主要风险是，存在妈妈那里的钱在年末之前不能取出。有可能在某个月的月初，津津手中的钱加上这个月妈妈给的钱，不够这个月的原定预算。如果出现这种情况，津津将不得不在这个月省吃俭用，压缩预算。现在请你根据2004年1月到12月每个月津津的预算，判断会不会出现这种情况。如果不会，计算到2004年年末，妈妈将津津平常存的钱加上20％还给津津之后，津津手中会有多少钱。
这道题是NOIP的上古原题，只需直接按照题意去模拟操作十二个月，即可算出利息（成功算出答案，返回正数，表示最终本金和利息的和）。
如果中途遇到余额为负的情况，直接返回当前月份即可（失败，返回负数，表示失败时所处的月份）。
题目3、一维数组的最大子数组和
下面是一个一维数组的 “最大子数组的和” 的动态规划的解法：
[代码段]
如果需要返回值返回这个最大子数组的开始和结束的下标，应该怎么修改这个程序？
这道题目也出现过多次了，可以使用前缀和算法快速地算出起点位置到当前位置的子数组和。
如果子数组的和为负，那么更新起点位置为当前位置，继续向后计算，直到扫描完整个列表。
题目4、莫名其妙的键盘
有一个神奇的键盘，你可以用它输入a到z的字符。然而，每当你输入一个元音字母的时候，已输入的字符串会发生一次反转！元音字母有a、e、i、o、u五种。例如，当前输入了tw，此时再输入一个o，此时屏幕上的字符串two会反转成owt。若用该键盘输入，有多少种方法可以得到指定的字符串？
可以使用递归方法求解。
当字符串长度小于等于1时，有字符串长度种方案数。
当字符串长度大于1时，有两种状态转移的形式：
第一种情况：延长。例如，字符串userid，可以由长度比它短的“useri”加上一个“d”得到。这种情况要求最后一个字符不是元音字母。同样地，“useri”又可以由“user”加上一个“i”得到，但是由于这样会被反转，所以最后一个字母是元音字母时应直接跳过。
第二种情况：反转。例如，字符串userid，可以由“dires”加上“u”再反转得到。这种情况求解时，需要使用反转的逆过程来处理。即判断目标字符串的首字母是否为元音字母，如果首字母是元音字母，当前字符串可以由第二个字符开始的子序列反转得到。例如，传入的目标参数为“userid”，首字母u是元音字母，因此这种情况的方案数目等于“serid”反转（即“dires”）的方案数目。
两种情况加起来就是最终答案了。