竞赛总览

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”)的方案数目。

两种情况加起来就是最终答案了。

06-01 15:12