前段时间看到群友聊天，使用特殊的昵称能够让文字的顺序发生变化。我把昵称复制到 IDEA 里面，发现包含一个显示为 RLI 的字符。在网上查询之后，发现是 Unicode 为显示双向文本提供的一个特殊字符，功能是将之后的文本视为独立的从右到左的顺序。还有其他特殊的格式化字符，以及用于解析这些字符并正确显示文本顺序的 Unicode 双向算法。
1 | print(";(" |
上面的文本在浏览器中会显示为 print("");，因为在第一个引号之后有一个 RLI 字符。如果在之后添加文字：
1 | print(";("Hello World! |
则会显示为 print("!Hello World");，具体的显示方式和双向算法的实现有关。介绍 Unicode 双向算法的两个网站：UNICODE BIDIRECTIONAL ALGORITHM，Unicode Bidirectional Algorithm basics。
时间过得好快！今年大概有 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、设计模式雨露均沾，基本上没有特别深入的，当时有点急躁。总的来说，确实有做不少事，但是效率不高，目的不明确，缺乏实践，要做的事还有很多。
题目
输入长度为 \(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\)。
思路
比赛时基本的思路是有的，就是没有实现出来。首先可以将后半段字符串反转，将原串当成两个字符串，这就将问题转化为判断操作之后两个字符串能否相等，从而简化实现。然后就是预处理前缀的字符计数（类似前缀和），最后对每个查询分类讨论，两个区间是相离、相交还是包含关系。个人觉得稍微复杂点的就是相交关系该如何判断，具体可以看题解区。