时间过得好快！今年大概有 5 个月的时间都在搞算法，然后其他时间基本上每周都会打比赛，虽然对面试来说不应该花费这么多时间，但是我喜欢算法给我带来的反馈，以及比赛时能够高度集中注意力的状态。特别是绞尽脑汁然后 AC 的感觉，真的很棒。即使不会做，赛后也可以通过题解来学习。

力扣基本上可以稳定三题，上 2300 分之后就有点没状态，排名波动有点大。在打 CF 之前就听说，力扣分减 700 大概就是 CF 分，结果还真是这样。CF 思维题较多，前四题基本上不会使用很复杂的数据结构，如果能稳定四题就能到 1900 分吧。AtCoder 题目有点水，对我来说，基本上从 D 题开始才算正式进入比赛，但是经常简单题也没做出来。令人印象深刻的是，获得两次群主发的进步奖。

5 月份阅读完《OSTEP》，9、11 月份学习完课程 CMU 15-445，并且做完四个相关的项目，感觉还不错。12 月份阅读《DDIA》25%，然后摸鱼。6-8 月份，高数、线代、Linux、Java 虚拟机、Spring、设计模式雨露均沾，基本上没有特别深入的，当时有点急躁。总的来说，确实有做不少事，但是效率不高，目的不明确，缺乏实践，要做的事还有很多。

找出出现至少三次的最长特殊子字符串 II

题目

输入长度为 \(n\) 的由小写字母组成的字符串 \(s\)。如果一个字符串仅由单一字符组成，则它被称为特殊字符串。输出在 \(s\) 中出现至少三次的最长特殊非空子字符串的长度，如果不存在则输出 \(-1\)。

数据范围：\(3\leq n\leq 5\times 10^{5}\)。

思路

可以直接想到二分答案，时间复杂度为 \(O(n\log{n})\)。不过该题有 \(O(n)\) 的做法，其实就是分类讨论。首先遍历一边数组，将数组按照字母分段，把对应的长度存到桶中。假设字符串 \(s\) 的最长特殊子字符串的长度为 \(m\)，则答案必定在 \([m-2,m]\) 范围内，枚举答案然后判断是否满足条件即可。当然还可以像灵神一样讨论得更细，但是不好理解。

回文串重新排列查询

题目

输入长度为偶数 \(n\) 的字符串 \(s\)，以及长度为 \(m\) 的二维数组 \(q\)，其中 \(q_{i}=[a_{i},b_{i},c_{i},d_{i}]\)。对于每个查询 \(i\)，可以将区间 \([a_{i},b_{i}]\) 和 \([c_{i},d_{i}]\) 中的字符重新排列，输出是否能让字符串 \(s\) 变为回文串。每个查询是独立的。

数据范围：\(2\leq n\leq 10^{5}\)，\(1\leq m\leq 10^{5}\)，\(0\leq a_{i}\leq b_{i}<\frac{n}{2}\)，\(\frac{n}{2}\leq c_{i}\leq d_{i}<n\)。

思路

比赛时基本的思路是有的，就是没有实现出来。首先可以将后半段字符串反转，将原串当成两个字符串，这就将问题转化为判断操作之后两个字符串能否相等，从而简化实现。然后就是预处理前缀的字符计数（类似前缀和），最后对每个查询分类讨论，两个区间是相离、相交还是包含关系。个人觉得稍微复杂点的就是相交关系该如何判断，具体可以看题解区。

Two Divisors

题目

输入两个整数 \(a\) 和 \(b\)，它们是 \(x\) 的最大除数，满足 \(1\leq a\leq b<x\)。输出 \(x\) 的值。

数据范围：\(1\leq a\leq b<x\leq 10^{9}\)。

思路

首先 \(b\) 肯定等于 \(x\) 除以最小的质因数，然后 \(a\) 可能等于 \(x\) 除以两次最小的质因数，或者等于 \(x\) 除以次小的质因数。这可以根据 \(b\bmod a\) 是否等于 \(0\) 来确定，如果是则 \(x=b\times\frac{b}{a}\)，否则 \(x=b\times\frac{a}{\gcd(a,b)}\)。

Mathematical Problem

题目

输入奇数 \(n\)，输出 \(n\) 个不同的数，它们都是整数的平方，并且 \(n\) 个数的数位构成的多重集合都相同。

数据范围：\(1\leq n\leq 99\)。

思路

只需要在 \(169,196,961\) 的基础上添加 \(0\) 就可以构造出满足条件的 \(n\) 个数，方法直接看题解或者代码吧，反正 \(169\) 和 \(961\) 这两个数比较特殊，真不知道大家怎么做出来的。