0x00. 前言

从开始刷算法题到现在大概有8个月了。自从上个月得到了去青岛现场赛的名额之后,我这个月狂补算法竞赛的知识。但是大一荒废了太多,很多时间可以学很多东西,时光白白浪费了,还是很后悔。

现在大二了,拼两年,决战大三大四,希望能拿一个好成绩。

朋友都说我最近气色不好了,哈哈。既然自己选择了这条路,就不会后悔。

这个栏目主要记录一些做过的有趣的和典型的题目,不会给详细代码。

我的答案仓库是 Click Me!。根据题号你能找到我的答案,但是我的答案有很大改进余地,欢迎与我探讨。

0x01. 模板题

模板题不过多介绍了,这些题都验板子和套路用的。

  1. Ouplio,KMP板子题,秒了。
  2. Power String,next数组的性质,循环节
  3. 统计难题,Trie树板子题,被HDU这个破编译器坑了20发WA和不计其数的修改代码。。。
  4. 统计同成绩学生人数,STL中map板子题。
  5. 01背包完全背包,Hihocoder特色,教学题,很好的题目,建议和背包九讲一起看。

0x02. 趣题

这个月打了很多CF,有很多练思维的题目,相当有意思,找几道印象比较深的。

注意:下面的所有分析都会剧透这题怎么做,想练习的点击标题直接跳转练习即可。

  1. Mahmoud and Ehab and the xor

    完全没想到会这么考构造,我想到了$1\oplus 2……\oplus (1\oplus 2…\oplus x)$这种构造方法,但是显而易见的是,这题会有冲突。解决的方法完全给我上了一课,对于上限$x$寻找第一个符合要求的$x\le 2^k$,然而还有可能重复,为了避免这个问题,使用$2^{k+1}$来辅助构造。这样就能保证不再重复,十分具有启发性。

  2. Merge Sort

    构造+模拟,这个题是真正使用逆向思维的题目。我们对一个无序序列需要调用$k$次归并排序才能把它排成有序的,那么我们可以直接这么构造:调用$k$次“打乱”方法,正好是归并排序的逆过程,就可以保证符合题目要求。一次打乱和一次排序是一一对应的关系,只要能理解这一点,这一题就很好做。

  3. Unimodal Array

    这个题十分有趣,要求这个序列先递增,后持平,再递减。想象一个梯形的轮廓就行。而且这三块区域可以任何一个为空集或者皆为空集。第一个想法就是先比较,一直递增就记录,那就是记录几个打破的点。但这里存在的问题很多很多,后面有很多东西需要考虑。看了题解才知道其实十分简单,两边一边递增一边递减,实际上都是沿着中心递增,那就从两头出发使用两个指针,到第一个不平衡位置打破然后判断区间内是否都相等即可。

  4. The Intriguing Obsession

    哎,比不过高中生。上海中学的大佬出的组合数学题。其实我很少在国外人出的题上做过组合数学题,可能是中国人数学很好的原因?哈哈。这个题主要是描述让我觉得十分有意思:“两个岛若直接相连距离为1,而两个不同颜色的岛若要相连至少距离为3”。这一句话其实隐藏了这么一个信息:两个相同颜色岛不能距离为1或者2。距离为1的情况是直接相连,2呢?2其实就是说两个相同颜色的岛不能连接到同一个其他颜色的岛上。那这个题就是两个岛集构造单射或者双射的过程,然后就变成一个很简单的组合数学问题。我对这种用情景描述重要信息的题目十分喜欢,这个题虽然我比赛的时候没做出来,但是真的很让我印象深刻。

  5. The Artful Expedient

    还是上面的大佬出的题。这题让我意识到数学推导的重要性。这个题最优美的一点就是情景是确定的,虽然看起来不确定,但是$a\oplus b$和$b\oplus a$都是满足题意的解,这是数学的对称性,这样保证答案一定是一个偶数,那答案就是确定的。这样的题目分析正是我所缺失的,很多时候我为了追求效率会变得急躁不冷静,这个题很好的教育了我,这个做法也让我觉得十分有趣。

这次就挑这些题吧。CF出的很多题目还是很有意思,最近一直在CF打比赛,之后也会去TopCoders和其他网站打打,坚持下去总有收获。