本期有新题，但是因为测试数据放水，并不难。而老题也是很容易可以找到答案。总的来说，难度不大，没有需要特别讲解的地方。

第一题：幼稚班作业

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

分析

19期考过，好像并不遥远。以前写的题解在此。

老样子，主要的坑在于理解题意。4根木棒并不是要全部用掉，而只是从里面选出3根。于是，排序 + 三角形合法性判断。

第二题：异或和

小张找到了一个整数 N，他想问问你从 1 到 N 的所有不同整数的异或和是多少， 请你回答他的问题。（）

分析

友好的数据范围使得此题成为大水题，循环 1e5 次毫无压力。于是只要循环累计 1 到 N 的异或运算即可通过此题，复杂度 。

但实际上，本题存在  的解法，如果 的范围取到 1e9，甚至更大，或许才有竞赛的意义。

• 当  是偶数时
  • 如果  能被 4 整除，答案是 
  • 如果  不能被 4 整除，答案是 
• 当  是奇数时
  • 如果  能被 4 整除，答案是 1
  • 如果  不能被 4 整除，答案是 0

感兴趣的同学可以自己推导看看。 

第三题：大整数替换数位

以字符串的形式给你一个长度为 M 的整数 N，请你计算出对这个数进行一次操作后模 9 的值为 1 的所有可能的不同操作方式。

在一次操作中， 我们可以选择 N 的一个数位 N[i]，并把它替换成另一个不同的 0 到 9 范围之内的数 B，当且仅当它们选择的 i 或 B 不同时两种操作方式不同。

输入描述：第一行包含一个整数 M (1 <= M <= 100000)。第二行包含一个大整数 N。

输出描述：输出一个整数， 代表对 N 执行一次操作后使 N 模 9 的值为 1 的所有可能的不同操作方式数量。

示例：

	示例
输入	4 2345
输出	5

分析

有趣的一道脑筋急转弯，仿佛让我回到了学生时代。

从小时候得到的经验可得，一个数如果能被 3、6、9 这样的 3 的倍数整数，那么它的各个数位的数字加起来就应该能被 3、6、9 整除。同理，如果一个数模 9 余 1，那么这个数的各个数位的数字之和也必然模 9 余 1。想到这一点，这道题的答案就显而易见了。

第一步，计算出整数  的各个数位之和（共  个数字）。

第二步，将上一步求得的和对 9 取余，根据余数的不同来进行（稍微）不同的操作：

 ** 这里由原数模 9 的余数得到操作的数字（比如加1、减8）可以得到数学公式，即使没有数学公式，列出 9 条判断语句也未尝不可。:D

第三步，对原整数从头到尾遍历每一位数字，如果该位数字进行操作后得到的数字合法（加和减单独检查），就记为合法的操作，结果加 1。

所谓操作后得到的数字合法，就是检查上下界。比如，我们得到的操作数如果是加1、减8，而某位数字是 9，很显然，9+1=10，需要进位，就必须改变其他数位，显然不合法；而 9-8=1，也就是可以把 9 改成 1，合法。总结来说，合法的条件是某位数字：

• 加上操作数小于10
• 减去操作数大于等于0

最后的结果就是遍历完所有数位，把检查结果累加，复杂度 。

第四题：莫名其妙的键盘

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

输入描述：一行一个字符串，长度不超过200，全部是由小写字母组成。

输出描述：一个整数，代表方案数量

示例：

	示例
输入	ac
输出	2

分析

由结果字符串逆推输入过程即可。逆推的时候只要考虑以下情况：

• 如果字符串的最后一位是元音字母
  • ① 如果第一位也是元音字母：说明最后输入的是首位字符，发生了翻转。
  • 如果第一位不是元音字母：不可能出现这种情况，因为末尾元音字母会发生翻转。
• 如果字符串的第一位是元音字母
  • ② 最后输入的是首位字符，发生了翻转。
  • ③ 最后输入的是末尾字符，未发生翻转。
• ④ 其他情况，最后输入的就是末尾的字符

只要依次把最后输入的字符“剥掉”，然后递归调用上述检查，最后把合法的方案加在一起即可。

举个例子。如果我们要得到的字符串是 abcdefg，推导的过程如下图（从下往上，圆圈数字代表了上述的 4 种情况）：