历程

2018年暑假集训（应付学校社会实践）

一、时间内容

2018 年暑假，山东理工大学信息楼，2018 年 7 月 29 日至 2018 年 8 月 30 日，共记 33 天，评价每天 8 小时，约 33 × 8 = 264 小时。

主要以学习算法提高自己的能力为目的，另外要负责17级新生的训练计划安排和辅导工作。

二、体验和经历

不出意外的话应该是最后一次参加的 ACM 集训了，集训后接下来就要参加下半年的 ICPC 区域赛和 CCPC 了，经过前两年的学习，这次集训的内容基本上是查缺补漏和学习一些比较难的算法了。

首先经过 14 级的学长指导，需要学一下后缀自动机、虚树、Link-Cut-Tree 等算法。

后缀自动机

后缀自动机首先是一类自动机，他可以识别一个串的所有子串。自动机上的每一个节点表示着一个状态，但是又不像 AC 自动机那样，每个节点记录着一个前缀。后缀自动机的每个节点维护的是一个整数的集合，可以叫做子串的结束位置集合。

例如字符串 S = "aabbabd" ，那么对于子串 "ab" 的结束位置集合就是 {3, 6}。

后缀自动机将结束位置集合相同的子串归于一个等价类中，并只在自动机上表示为一个状态，有证明给出，这样自动机上的状态数是和字符串的长度同阶的。

接下来就是需要考虑后缀自动机如何识别一个字符串，给出一个字符串，需要从后缀自动机的初始状态开始转移，依次添加一个新的字符，如果转移中添加了一个新的字符串但是没有对应的状态，那么这个字符串是后缀自动机识别不了的，也就是说这个字符串不是字符串 S 的子串。

后缀自动机还有诸多的性质，例如如果沿着 Parents 边走的话，Right 集合会不断的合并变大，Parents 上方节点能表示的字符串均是下面字符串的一个后缀等…

虚树

据说虚树的英文是叫 Auxiliary tree，简单的来说是维护树上仅于题目有关的信息，除去掉冗余信息以保证时间复杂度的一种算法。为什么说是虚树呢，是因为他是在原来树的基础上建出的一颗全新的树，需要重新建边或分配点权等信息。

虚树的题目通常是这样的，给出一颗大小为 n 有边权或点权的树，然后有 q 次询问，每次给出 $k_i$ 个关键点，要求计算关于这 k 个点的问题（通常和 LCA 有关），但是 $\sum k_i$ 又比较小（通常和树的大小同阶）。

假设你可以 $O(n)$ 的在树上解决单次的询问，那么总时间复杂度是 $O(nq)$ 的，问题的 n 和 q 一般为 $10^5$ 显然这样是不可以过这道题的。这时候就需要用到虚树了，使用虚树我们对于每个询问都可以 $O(k_i)$ 的建出一颗有 $O(k_i)$ 个节点的树，并且可以通过这棵树 $O(k_i)$ 的计算出答案。

LCT（Link-Cut-Tree） 又叫动态树，支持让一颗树删除一条边分裂成两颗树，或者两棵树合并成一颗树，并且维护一条链或子树的信息。

LCT 和树链剖分差不多，树链剖分大概是将一棵树划分成若干条链，然后对每条链映射成连续的区间，就可以用线段树去维护每条链的区间信息。LCT 也是把一棵树拆成若干条链来维护，不过 LCT 是直接把一条链用一颗 Splay 当做一个序列来维护，序列按照节点的深度当做关键字排序。

LCT 主要支持三种操作，Access 操作，将一个节点 u 到根节点的路打通（类比树链剖分里的重链），并且将 u 节点设置为其所在的 Splay 的根。Link 操作，将 u 设置成 v 的儿子，先 Access u，给 u 加一条虚边到 v，然后 Access u。Cut 操作，将一个节点 u 和其父亲断开，先 Access u，然后断开 u 与其左儿子的连接，再 Access u。

有证明给出，LCT 的每一个操作都是 $O(\log n)$ 的。

接下来说一下前半年参加的比赛的总结。

CCCC 天梯赛

感觉一直是一项以考察基本数据结构为主的比赛，今年比赛缩水了一下，没有选拔赛直接只有一场决赛了。老师说按照 SDUT 的经验每次都是初赛打的不太好，然后决赛打的不错。不过这次没有初赛，于是决赛相比前几年打的不怎么好。

比赛是在青岛的中国石油大学进行，不得不说中石油的校区环境是真的不错，不过这次不像区域赛那样有个热身赛之类的，所以当天去当天就回学校了，少了几分乐趣。中石油提供伙食的自助餐厅是真的棒，饭菜样式多，肉菜多，又挺好吃的，中午吃饭的时候老师在催要去比赛了我们还在吃…

比赛不知道为什么，前一个半小时整个机房的电脑都不能正常上比赛的网址，本来时间就不太充裕，先锋奖励肯定是放弃了，只能用剩下时间去尽可能的做了会做的题目…

和往届一样，前面几道题都是基础题，大概程序设计基础的难度，后面几道也就涉及到并查集这种基本的数据结构，比赛的核心是考察代码能力，做起来根本不用动脑子，这一点和 ICPC、CCPC、Codeforces 之类的比赛非常不同。然后后面几道题有特别难，一道是写一个格式化代码的程序，一道是一个非常难的字符串题，另外一个是计算几何。基本上也都能写一个暴力程序骗不少分。

最后好像是 226 分滚粗（去年都能打到 236），感觉难题是比去年难，简单题也都没什么感觉，也算是尽力了。

山东省省赛

首先先看的 C，标准的签到题，让队友敲的，结果 WA 了两次才 A，可以说是开局非常爆炸了，于是导致我后面交题也不怎么看罚时了（不知道算不算什么破釜沉舟背水一战），想着只能靠题数取胜了。

然后看的 B，理解错了题意，正确的题意是符合贪心性质的，可以写贪心，我大概是做了个 Hard Version，写了个最小费用流，非常熟练的抄完自己总结的板子，保存边的数量的变量没初始化 RE 了一发，然后由于不考虑罚时，于是改完就立刻交了一发就 A 了。

在我写 B 的时候队友就已经在看 F 题了（数据出错的那个题），等我写完他告诉了我一下容斥的做法，我觉得没什么问题就开始敲了，不过写的过程中感觉非常难写…看到榜单上 6 分钟就 AC 的，怀疑自己的做法是不是不对…然后让队友写了个对拍自己去重新想了一下思路，发现还是得写容斥，于是回来继续写，写完后又对拍了几组数据改了改就交了，然后肯定是 A 的，最后也不知道这个题有没有写对 ORZ

这时候另一个队友一直在读题，我敲完一道题基本上就可以接着看下一道题了，这时候一个队友在想 E 题，我去写 G 题，然后一眼看过去就是 NIM 博弈加 DP 记录方案数，不过这里数据越界改了好几次才过，不过改完一次就交一次不在乎罚时，所幸改的还算快。

在我改 G 题的时候让队友敲了下 E 题，NlogN 的复杂度 TLE 了，感觉必须得线性的算法才能过，这时候封榜还有半个小时，榜上已经有六题的了，于是决定让队友去其他的题了（B 和 D），然后我考虑这个题的答案限制条件比较少，应该用不到队友敲得逆序数之类的，于是正好我们都想到单调队列，于是先写了个单调队列，然后测了下样例对了，要交的时候还是不放心，因为如果这个 WA 的话我不能确定是算法错了还是代码细节错了，于是让队友出了下样例果然错了，后来多考虑了一个条件就 OK 了，然后提交 AC。

这时候队友说 B 题有思路了，不过是图论题还是让我敲，我一直感觉 1e8 的时间复杂度过不去，于是先让队友把板子抄上，然后自己想了下细节怎么处理，感觉没问题之后就开始上手做了，写完 debug 了 20 多分钟，队友板子抄错了两个地方，改完过了另一个队友出的特别强的样例（反转他说是比较强），提交就 AC 了。

这时候比赛结束还有四十分钟，榜上已经有七题的队伍了，加上我们罚时比较高，夺冠要在这 40 分钟 A 两题感觉希望不太大了，有点失望…队友在我写 B 题的时候已经想了下大概的 D 题做法，我问了他一下，感觉加上树链剖分就可以写了，于是拿过来之前直接整理的树链剖分板子就超了起来，心情比较差加上又特别累了，中间电脑还重启耽误了十多分钟，最后还有十分钟结束才写完，总共 200 多行代码，我当时就和队友说，这么长的代码要是不出点 Bug 什么的我都不信，结果运行没编译错误，然后输入样例结果却都是 0 … 非常紧急的改完之后还剩五分钟了，最终居然过了样例，当时 PC ^ 2 显示结束还有三分钟立刻就交了，之后就赶紧看代码还有没有错误。然后看着看着队友说有评测结果了，看了一下返回了一个 Yes，可以说是非常开心了。

西安邀请赛

首先看的 E 题，很显然的一个几何的结论三分钟 A 了。

然后看的 A 题，猜了个显然不对的做法，WA 一次，然后和 szq 讨论后又写了一个优化版的做法，还是 WA，最后又讨论了下，算是推出来了出题人认为的正解，不过这个题目出错了，在我们推出来正解后讨论区裁判公布了正解。算是可惜了两发罚时，不过裁判组处理也是比较得当，如果不这样的话会有好多有水平的队伍卡在 A 题。

在我敲 A 题的时候 szq 就已经在看 D 题，看上去就是 nim 博弈的变种，推出来 SG 函数就基本上做出来的了，不过他没有打好表，还是我上去记忆化搜索一波后打出来表，规律非常显然，出了个小失误 WA 一发后就 AC 了。

然后 lxw 告诉我了下 B 题（最后也没写出来）的题意后我就去看 K 了，这里我大概敲了一个小时，思路越敲越乱，大概浪费了一个多小时，最后 szq 说他有一个比较简单的做法，我就让开机位去让他敲了，自己去洗了把脸清醒一下…最后 szq 写完调试了半个小时多才 A 掉这个题，算是这次比赛里面最大的失误了。

之前看榜上有好多人过了 G 题，并且 szq 和 lxw 已经讨论出来了这是一个简单的板子题，于是 A 完 K 题后直接去做 G 题了，敲完板子后一直 WA，最后我打印代码让他们两个看，去敲了 C 题，C 题在 szq 敲 K 题的时候我已经和 lxw 讨论的差不多了。

最后实在没找到其他的错误，于是只好试试改精度，然后改完之后 G 题居然 AC 了，随后我敲完 C 题过了样例也顺利 1A 了。

这时候刚好封榜，只有一个小时剩余的时间了，看榜上其他有人做出来的题只有 B 和 H 题，F 题只有 GDUT 穷游中国做出来了，感觉可能比较难，于是就去做 B 题了（后来发现这个是错误选择）。

最后让 lxw 读出来了 H 题的题目，B 和 H 最后也没有思路。

比赛后听他们讨论说封榜前没人过的 I 和 J 题都是数据结构的模板题，感觉自己没看有点可惜。