10月做题记录
0x00. 前言
从开始刷算法题到现在大概有8个月了。自从上个月得到了去青岛现场赛的名额之后，我这个月狂补算法竞赛的知识。但是大一荒废了太多，很多时间可以学很多东西，时光白白浪费了，还是很后悔。
现在大二了，拼两年，决战大三大四，希望能拿一个好成绩。
朋友都说我最近气色不好了，哈哈。既然自己选择了这条路，就不会后悔。
这个栏目主要记录一些做过的有趣的和典型的题目，不会给详细代码。
我的答案仓库是 Click Me!。根据题号你能找到我的答案，但是我的答案有很大改进余地，欢迎与我探讨。
0x01. 模板题
模板题不过多介绍了，这些题都验板子和套路用的。
- Ouplio，KMP板子题，秒了。
- Power String，next数组的性质，循环节
- 统计难题，Trie树板子题，被HDU这个破编译器坑了20发WA和不计其数的修改代码。。。
- 统计同成绩学生人数，STL中map板子题。
- 01背包，完全背包，Hihocoder特色，教学题，很好的题目，建议和背包九讲一起看。
0x02. 趣题
这个月打了很多CF，有很多练思维的题目，相当有意思，找几道印象比较深的。
注意：下面的所有分析都会剧透这题怎么做，想练习的点击标题直接跳转练习即可。
完全没想到会这么考构造，我想到了$1\oplus 2……\oplus (1\oplus 2…\oplus x)$这种构造方法，但是显而易见的是，这题会有冲突。解决的方法完全给我上了一课，对于上限$x$寻找第一个符合要求的$x\le 2^k$，然而还有可能重复，为了避免这个问题，使用$2^{k+1}$来辅助构造。这样就能保证不再重复，十分具有启发性。
构造+模拟，这个题是真正使用逆向思维的题目。我们对一个无序序列需要调用$k$次归并排序才能把它排成有序的，那么我们可以直接这么构造：调用$k$次“打乱”方法，正好是归并排序的逆过程，就可以保证符合题目要求。一次打乱和一次排序是一一对应的关系，只要能理解这一点，这一题就很好做。
这个题十分有趣，要求这个序列先递增，后持平，再递减。想象一个梯形的轮廓就行。而且这三块区域可以任何一个为空集或者皆为空集。第一个想法就是先比较，一直递增就记录，那就是记录几个打破的点。但这里存在的问题很多很多，后面有很多东西需要考虑。看了题解才知道其实十分简单，两边一边递增一边递减，实际上都是沿着中心递增，那就从两头出发使用两个指针，到第一个不平衡位置打破然后判断区间内是否都相等即可。
哎，比不过高中生。上海中学的大佬出的组合数学题。其实我很少在国外人出的题上做过组合数学题，可能是中国人数学很好的原因？哈哈。这个题主要是描述让我觉得十分有意思：“两个岛若直接相连距离为1，而两个不同颜色的岛若要相连至少距离为3”。这一句话其实隐藏了这么一个信息：两个相同颜色岛不能距离为1或者2。距离为1的情况是直接相连，2呢？2其实就是说两个相同颜色的岛不能连接到同一个其他颜色的岛上。那这个题就是两个岛集构造单射或者双射的过程，然后就变成一个很简单的组合数学问题。我对这种用情景描述重要信息的题目十分喜欢，这个题虽然我比赛的时候没做出来，但是真的很让我印象深刻。
还是上面的大佬出的题。这题让我意识到数学推导的重要性。这个题最优美的一点就是情景是确定的，虽然看起来不确定，但是$a\oplus b$和$b\oplus a$都是满足题意的解，这是数学的对称性，这样保证答案一定是一个偶数，那答案就是确定的。这样的题目分析正是我所缺失的，很多时候我为了追求效率会变得急躁不冷静，这个题很好的教育了我，这个做法也让我觉得十分有趣。
这次就挑这些题吧。CF出的很多题目还是很有意思，最近一直在CF打比赛，之后也会去TopCoders和其他网站打打，坚持下去总有收获。