竞赛总览

CSDN 编程竞赛三十七期：比赛详情 (csdn.net)

近几期竞赛出现了一些新的题目，而且整场下来也没再遇到新的bug。

另外，对于抄袭题解等情况的投诉，处理速度也非常及时，让博主看到了C站的进步。

虽然有个别用户开小号的问题还是经常出现，但总体上体验越来越好了。

竞赛题解

题目1、幼稚班作业

幼稚班终于又有新的作业了。老师安排同学用发给同学的4根木棒拼接成一个三角形。当然按照正常的逻辑，如果不能拼接成三角形，必然要折断某个木棍来拼接三角形。可是懒惰的小艺当然不会费力了！如果拼接不成三角形，小艺就会把它拼接成类似边长1 1 2的伪三角形（两边之和等于第三边）。如果伪三角形都拼接不成那就不交作业！

最终答案就一个数，且答案种类很少。懒得思考，直接骗分做的。

题目2、异或和

小张找到了一个整数N，他想问问你从1到N的所有不同整数的异或和是多少？请你回答他的问题。此题由CSDN用户a23333a提供。

#include int main () {int resu1t = 0;int n;scanf ("%d", &n);while (n > 0) resu1t = resu1t ^ n --;return 0;
}

测试数据比较友好，直接暴力模拟即可。

题目3、大整数替换数位

以字符串的形式给你一个长度为M的整数N，请你计算出对这个数进行一次操作后模9的值为1的所有可能的不同操作方式。在一次操作中，我们可以选择N的一个数位A，并把它替换成另一个不同的0到9范围之内的数B。当且仅当选择的位置或替换的数不同时，两种操作方式不同。此题由CSDN用户a23333a提供。

相信大家都学过判断3的倍数的方法。对数字的每一位进行求和，再除以3看看余数是否为零，即可知道这个数是不是3的倍数。如果要求余数为1，那么满足SUM % 3 == 1即可。

九的倍数也同理，只需对每一位求和，判断对9的余数是否为零。例如27、108等，都是9的倍数。

这道题只需要判断替换之后的数，如果SUM % 9 == 1就可以替换。另外，如果被替换的数和原数位上的数一致，则不可替换，应该直接跳过。

从上面的推理可知，替换时，数位和不是变小，就是变大。因此，这道题还有优化点，可以不用逐个尝试，就知道这一位能否被替换。感兴趣的小伙伴可以自行思考一下哦。

题目4、莫名其妙的键盘

有一个神奇的键盘，你可以用它输入a到z的字符，然而每当你输入一个元音字母（a、e、i、o、u）其中之一的时候，已输入的字符串会发生一次反转！比方说，当前输入了tw，此时再输入一个o，此时屏幕上的字符串two会反转成owt。现给出一个字符串，若用该键盘输入，有多少种方法可以得到？

#include 
#include 
#include 
#include const std::string spec = "aeiou";int search (std::string str) {if (str.length () == 1) return 1;int result = 0;if (match (str [0]) == true) {std::string inv = str.substr (1);std::reverse (inv.begin (), inv.end ());result = result + search (inv);}if (match (str [str.length () - 1]) == false) {result = result + search (str.substr (0, str.length () - 1));}return result;
}

 这道题可以用类似动态规划的思路进行推理。

字符串长度为1时，直接输入即可得到，有1种方式。

当其长度超过1时，可以由更短的字符串状态转移过来。

例如，目标字符串为ac时：

1、可以由c加上1个a（即ca），强制翻转得到。

2、可以由a加上1个c，直接输入得到。c不是aeiou其中的一个，所以结果不会被翻转。

通过这两种方式进行状态转移，可以将短字符串扩展为长字符串，得到方案数。