省流：寄了。
初赛部分
Day -2
已经停课了，这次果然没有报普及组。（不能AK了呜呜呜……）
下午老师给我们送了蛋糕和奶茶过来，好像是老师的生日。不过过两天也是我的生日呢，不知道为什么每次我的生日都会和初赛撞……
Day -1
以往这个时候我们都开始复习初赛了，但今年不同（可能考习惯了）。
但是为什么今天还有模拟赛啊喂，我还打寄了……
晚上还是有很多学弟复习初赛了，我就看了一下洛谷的 CSP-J 初赛模拟，被打爆了，然后就没敢看 CSP-S 的。
不知道明天 S 组会怎么样。
Day 1
上午没事做，看了看初赛知识点总结就开始颓。
有人拿到了 CSP-J 初赛试题，就一起做了一下。一看题，完了，面向对象特性，哈夫曼编码，我全都不会。
“啊啊啊啊啊啊都不会怎么办啊，我是不是寄了？”
“你TMD在这大叫不如去多复习复习。”ztc 一脸嫌弃地怼我。
（在此说明一下，我中午和下午就是被上面这句话心态搞崩的，所以不要再问我为什么不说话。）
然后直到考试前，我都没心情复习。
中午回去睡了个觉，精神好了很多，就直接去了考场。
附近没什么认识的人，教室另一侧有两个**一直在说话，监考员提醒了都还在说。
很快发卷了，快速预览前几题，都比较简单，没有普及组毒瘤。
做到第13题：
for(int j=0;j<n;j*=2)
虽然一眼过去就是 \(O(n\log n)\)，但是还是觉得很好笑。
很快就做完了，觉得简单了很多，但有些地方不确定（我忘了取模负数是什么）。
后两个小时都在想一道模拟赛题，大概想出来了。
出来对答案，除了第 26 题和那道时间复杂度可能为负数的题，其他应该都对了。
又去洛谷上对了对答案，感觉有些题洛谷上的答案是错的，我又逐个问了机房里的人，就不管了。
预估 95.5。不过初赛考多少分都是一样的，并不重要。
Day ???
教练先拿到了我们学校的成绩，我 95.5，意料之中。我竟然还是全校最高的，属实是……
不过这次提高比普及简单是我没有想到的。
复赛部分
Day -2
又是模拟赛，但这次是我搬的题哈哈哈哈哈哈哈……
但因为是信心赛，所以大家都很高分。其实考前应该多挂挂分涨涨人品的？
晚上改了改题，又跟 wlx 玩了玩奥日2，打到了光之池末尾。
每日一问：夸洛克到底是怎么被控制的？
Day -1
今天全天没有安排，早上把过去的一些题改了，然后开始 CSP 前动员。
wlx，wzy，lh，wcj，ztc 等人分享了 CSP 的防挂分注意事项，我还学了学如何用 NOI Linux 编译文件以防 UB。
-fsanitize=address,undefined
下午去试了试机，敲了敲 mystd，把去年 T3 切了，然后和 wlx 想 T4 没想出来。（我现在知道为什么去年人均 360 了）
晚上大家都开始颓废了，我也和 wlx 继续打奥日2，成功在 8 点前把沙虫打通了。
8 点是雷打不动时间，但是还是没有飞盘，差评。回机房的时候发现老师都在，就不敢再颓了。
回宿舍后又拿舍友板子打了打 phi，但没打多久就被其他人强制关停睡觉了。
理应来说，考试前一天确实要睡个好觉。
Day 1
早上起床晚了一点，差点进不去机房了。
打了打 fhq treap 和 splay 的板子，毕竟平衡树去年救了我两道题，万一今年又用的上了呢。
又打了打点双的板子，就又开始颓，但是每次小颓一会过后老师都会进来，所以就不敢颓了。
（可恶啊，没在 CSP 前打完奥日2/fn/fn/fn）
中午老师给了我们普及组试题，自造了数据放在 OJ 上，感觉会有一群学弟 AK。希望今年 S 组能再简单一点吧。
吃完饭后就早早回宿舍了，毕竟考前睡个好午觉也是很有必要的。（但是中午没能打到 phigros 呜呜呜）
下午又起晚了一点，赶紧跑去机房，把东西准备好，奔去考场。虽然说 CSP 并不怎么重要，但我还是感觉好紧张。
不要挂分！！！不要挂分！！！不要挂分！！！
进了考场，监考员不给带水和零食，之前买的士力架都白买了。
我是 2 号，左边的左边就是 wcj（其实就是左边，中间没有人），右边是个女孩子，看起来很紧张。除此之外就看不见其他人了。
仔细阅览考前须知，不断提醒自己建子文件夹，写文操，但还是担心自己会因此爆零。（谁不担心呢？）
监考员提前 3 分钟开考了，密码是 belief2022，上午普及组的好像也是类似的密码。感觉寓意是跟疫情有关的？
先打开 C++，把编译指令配置好，又打了打 mystd，检查无误后开始看题。
T1 是图论题，好像要先求一个点走 k 步内能到哪些点，再求一个无重复点的五元环。
想了一会没思路。完了，我不会今年 CSP 要被 T1 创死了吧？
突然想到去年也是这个状态，便冷静下来重新思考。把题目分成两部分，先求解第一个问题。可以类似 floyd 的做法，松弛 \(k\) 次，复杂度 \(O(n^2k)\)，不行。再想了想发现只需要求两个点是否可达，可以用 bitset 优化，复杂度 \(O(\frac{n^2k}{\omega})\)，算了一下很能过。
接着第二个问题，想了一下 dfs 树发现不可行，但又发现这个环一定包含 \(1\)，可以把环拆成从 \(1\) 开始的两条长度为 \(2\) 的链，最后判断底部两个点有没有边即可。
于是对每个点记录一下有哪些点可以作为它和 \(1\) 的中转点，再枚举两个点一条边，取那个权值最大且不与另外两个点相等的点即可。这只需维护最大值，次大值，次次大值即可。复杂度 \(O(nm)\)。
很快过了所有大样例，再花一点时间写了个暴力，拍了拍没问题，准备看 T2。
突然想到要测极限数据，于是测了一下，发现寄了！以为是 bitset 太慢了，便注释掉下面，发现跑得飞快。原来是数环寄了……
再仔细思考一下，我建的新图的 \(m\) 好像不是原图的 \(m\) 了，是 \(n^2\) 级别的了，也就是说我的复杂度是 \(O(n^3)\) 的，不寄才怪。于是换个思路，枚举两个点，再对这两个点的最大值，次大值，次次大值分类讨论，就是 \(O(n^2)\) 的了。极限数据跑的飞快。
现在已经过去 1h 了，我才做完 T1，有点慌，便赶紧去看 T2。一看 T2：是我看错题了吗，我怎么感觉好简单？
把正负分类讨论一下，然后写几个 ST 表就好了。发现最后一个大样例没过，对着调一会就过了。真的是 T2<T1 啊。
接着看 T3，想了一下发现两个条件其实相当于所有点出度为 \(1\)，是内向基环森林。不过直接做的话不好做，2，4 的操作特别麻烦。
这时突然想到了一个非常 nb 的做法：给每个点附一个随即权值 \(a_i\)，保证 \(\sum{a_i}=0\)，现在只需要判断是否 \(\sum{out_ia_i}=0\) 且 \(m=n\)。
其实一开始想的是异或，但感觉这样很容易错（\(out_i=2\) 就抵消成 \(0\) 了），就改成了和。
大样例全都过了，这时我想要不要再来个双哈希保险一点（比如求积取模之类的），不过想了想貌似很难卡，就懒得写了。
现在已经过去两个小时了，开始看 T4。\(k=1\) 是送分的，\(k=2\) 好像倍增也非常好做，\(k=3\) 还不太会。于是先开始码 \(k \leq 2\) 的部分分，很快把大样例过了。
然后开始想 \(k=3\)，发现只会出现一种特殊情况，即儿子的儿子跳到另一个儿子。那只需要多记录一些倍增数组就可以了。
为了方便打 \(k=3\)，我把 \(k=1,2\) 分别放进一个结构体里分开讨论，并把 \(k=1\) 重打了一遍。然后开始码。码了一阵发现转移异常冗杂，有很多很多特殊情况，再加上离考试结束只剩半个小时了，我就弃了正解，转而去打 \(n,q \leq 200\) 的部分分。事实证明，这样做是正确的。
最后 15 分钟，我把所有文件放在 NOI Linux 下测大样例，没有任何问题，测了所有代码的空间，并拍了 T1T2 的极限数据，都没有任何问题。于是便摆烂了。
说句闲话：机房空调好冷，我又忘记把外套带上，所以最后一个小时我全身都在发抖 /fad
期望得分：100+100+100+68=368
考试结束了，wlx 和 wcj 都做出 T4 没做出 T3；我，wzy，lh 都做出 T3 没做出 T4（所以没有人 AK？），ztc 和 lgj 好像没上 300。
其实如果我不挂分的话，我的分数还是挺好看的。
晚上回家了，老师把 S 组代码发群里了，我就立刻去 infoj 上测。
T1————没挂。
T2————没挂。
T3————没挂。
T4————————挂了？？？？？？
我 \(k=1\) 的点全挂了？？？仔细翻开代码一看：
f[u][i]=f[f[u][u-1]][i-1]
我这才发现，我在重写 \(k=1\) 前自测了 \(k=1\) 的数据，但是重写后没有测！
喜提挂分 -16，又没有大众分。晚上睡不着觉了。
\[\Huge\texttt{f[u][i]=f[f[u][u-1]][i-1]} \]\[\Huge\texttt{f[u][i]=f[f[u][u-1]][i-1]} \]\[\Huge\texttt{f[u][i]=f[f[u][u-1]][i-1]} \]Day ???
咕。
标签：大样,wlx,复杂度,初赛,Day,2022,游记,CSP From： https://www.cnblogs.com/AFewSuns/p/16840525.html