【游记】NOI2021 网上同步赛
UPD（2021.9.1）：
偶然想起翻看官方发布的同步赛成绩（当然之前已经看过了），猛然发现自己的实际得分比洛谷测出来的得分低 4 分。于是去查了一下自己在洛谷上的提交记录，发现自己 D2T1 有一个 AC 的点跑了 1.94s，预计就是这个点 T 了。
不愧是 CCF 的机子，连洛谷的机子都跑不过……（事实上在这之前我就发现过这事）
题记
又是一年同步赛，发现自己真的菜。
Day 1 只会打暴力，可惜没能出奇迹。
Day 2 暴力也不会，分数低到打铁退。
Day 1 (2021.7.26)
赛前
早上 8:15 起床，看了一眼 NOI 官网和邮箱，还是啥动静都没有。
说好的 7 月 25 日发考试服务器地址呢？
教练说应该还是今天，让等通知。
这 CCF 真就区别对待？要延期好歹发个通知吧……
吃完早饭，给 [email protected] 发了封邮件去问网上同步赛时间，然后开始做作业。
做了一阵，突然想打开电脑看一眼有消息没有。
电脑打开后看了一眼时间，已经 10:00 了。
要是再没通知就撒手不管！
打开 NOI 官网：咦，有通知了！点开一看，时间是……10:00！
不愧是长期 ddl 的我，这么准时！
赛时
登录以后，开始下载压缩包。速度感觉特别慢，点开详情一看，要 1h？！
这还让不让人好好参加啦？！
从 Chrome 换成 IE 也是一样，便上 QQ 找其他人要了压缩包。
话说我为啥不早点这么干
阅读了一遍题目，理清了题意，还没深入思考，就已经 10:50 了……
可见阅读能力有多差
先想 T1。
话说为什么三道题都以图为背景
首先
然后考虑特殊性质，直觉告诉我 B 性质更可做，就先想 B 性质。
发现树剖线段树可以拿到这 30 分。
再回头想了下 A 性质，原来更简单，直接线段树区间赋值即可，又有 10 分。
由于 A 性质的做法完全不能拓展，于是想从 B 性质做法出发想正解。
思考了一阵没有解法，并且我定的 20 分钟计时器响了，就开始敲 T1 部分分。
一开始莫名的有自信，想在 10 分钟内把主函数和 30 分暴力写完。
开始写以后才发现没有想象的那么好写，就加到了 15 分钟。
结果写了半小时……（码力不行是真的难受）
然后写 A 性质，发现过不了样例？！（已经过了 12:00）
调了一下，发现是线段树 lazy 下放后没清空，改了就过了样例。
这是我第 N 次线段树写挂，几乎是写一次挂一次，每次挂得还不一样。
把 A 性质部分的线段树拿来一改，继续写 B 性质，过样例已经 12:30 左右。
我有充分理由怀疑，当时是不是忘记了在参加比赛
急忙去做 T3。
首先
怎么感觉这次部分分挺足呀
然后
描述成缩点它不香吗
等等，拓扑排序，那么题目的条件相当于拓扑排序后形成了一颗外向树！
总算知道题目这个神秘的条件有神马用了
于是把外向树建出来，用倍增判断祖先关系以判断是否无解，有解就输出两个点之间链上的 size 之和。
话说当时为什么不用 dfs 序判断祖先关系？
这样就又有 16 分。
好少啊
再想了想，如果加一条边，要么是一段竖着的链缩成一个点，要么是一段竖着的链可达范围加上一个子树。好恶心啊……
话说我为什么想起了今年省选的某道题
赛后看了题解，想不通自己为什么不分类讨论经不经过某条边
由于时间本来就不多，果断放弃
写了一会儿，
又写了一会儿，
调试发现拓扑排序时竟然只有几个点入过队……
对着代码检查了一下，没看出哪里挂了。
不管了不管了，赶紧做 T2 去了！
首先
对于 A+B 性质，两层之间至多有一个完美匹配，于是用匈牙利算法求最大匹配，又有 20 分。
继续想……
突然想到 A 性质可以使每两层之间的结果可直接合并，于是对于
考虑到此处 dfs 枚举排列可以中途判断 & 计算贡献，因此跑不满，应该能过，故又有 10 分。
由于
dfs 写出来跑得有点慢，我不确定究竟能不能过。
（我这台电脑运行比正常编译器慢——所以我不知道究竟是多慢）
于是又加了个剪枝，跑出来 1s 多一点，我觉得能过。
写完匈牙利，一测样例发现 RE……
调试发现是死递归了——竟然没有用 bool 数组记录是否访问过……
各种迷惑行为大赏
由于三份代码都已提交了一遍，便继续调 T3 的
又瞪了好一会，终于发现 tarjan 的 low 的更新写反了……
改了重新交的时候网站卡了很久……
等了会儿又突然不卡了。
在等的同时测了大样例，发现拓扑排序不入队的问题已解决，但还是 WA 得很惨。
最后两三分钟时，定睛一看：我竟然没有把原编号转化成缩点后的编号！
过了编译后，赶紧又交了一发（怕交不上去）。
不过，测样例还是挂飞……
我这 16 分是写出了多少个 bug！
恰巧在检查回答询问那一部分，突然发现：有 解 条 件 写 错 了！！！
我当时写成了这个样子：
if(dep[s[i]]>dep[t[i]]||jump(t[i],dep[t[i]]-dep[s[i]])==s[i])
IO::write_int(sum[t[i]]-sum[f[s[i]][0]]);
else
IO::write_char('0');
IO::write_char('\n');说明：有解的条件为 dep[s[i]]<=dep[t[i]]&&jump(t[i],dep[t[i]]-dep[s[i]])==s[i]。我大概是在想无解的条件，于是写了 dep[s[i]]>dep[t[i]]||，但是写到后半部分又想判有解……
我急忙一改，但交的时候考试已经结束了……
然后测大样例，就过了……
我的 16 分，你死得好惨……
赛后
估分 70+(40~50)+28=138~148。
隐隐约约感觉要凉
后来发现大众分 200 左右……
有人说 T1 很像 [SDOI2011]染色。
看来我是白做了
有人说 T2 跟 CF167E 很像，可惜没做过。
最终在洛谷得分为 80+50+28=158。
CCF 的机子应该不会比 Luogu 评测机慢吧
（2021.7.27）
去看了 T1 的题解。
这个染色咋就没想到呢……
就连粗暴地用树剖线段树维护都没想到……
Day 2 (2021.7.28)
赛前
早上 8:30，同步赛的网站死活上不去，我索性就继续吃早餐。
显然不是因为我要吃早餐所以网站上不去
一直等到 8:55 左右，同步赛的网站才上得去。
下载好题目压缩包以后，刷新了一下，发现提示“比赛未开始，禁止进入”，原来是考试时间被改成了 9:00-14:00。
感谢 CCF 送的几分钟！
赛时
先把题目阅读了一遍，我最大的感受是，这题面（和昨天相比）也太冗长了吧！
理清题意后决定先做 T1。
一口气想了几个暴力做法，时空复杂度都很爆炸，根本拿不了多少分……
想了 20 分钟左右，还是没啥思路，就开始打暴力。
先写了个
然后写了个 01-trie+dfs枚举哪些位不同，用于处理测试点 3,4,8。
部分分也太少了吧
写完已经 11:00，原本想写的询问串随机生成的部分也只好暂时放下，去做 T2。
从时间可见笔者代码能力有多差
我一开始先发现：连续的相同操作可以快速执行。
然而并没有任何用
由于生成
我一开始觉得出题人很毒瘤——分子分母都要输出，而值的和是
想了好一阵，才猛然醒悟：由于每次是求倒数，再加上一个整数，分子分母始终互质，所以可以在计算过程中取模。
于是
然后思考 A 性质，手玩一下发现生成序列的形式为若干个
在这一过程中，我突然意识到
又思考 B+C 性质，发现模拟+矩阵乘法即可，又有 15 分。
但接下来就有点无从下手。
看了眼时间，差不多该写了，就放弃了 T2 后面的部分。
写 A 性质的判断时，一开始以为无需记录当前序列长度，然后就过不了样例，调了一会儿才发现。
写着写着 B+C 性质，才发现当前序列的最后两个位置可能会修改，不能直接乘进答案里。（虽然很好改，但这说明自己没有完全想清楚）
12:40 左右，50 分总算到手。
时间挺紧张，匆忙地去做 T3。
先考虑完全按照题意模拟，发现时间复杂度是
成功升天
于是干脆先写 R 答案就为
然后写性质 A，写的过程中发现：这也没想清楚，那也没想清楚，自我感觉会挂，但还是坚持写完了。
直觉真准
竟然不下发对应测试点性质的大样例——必须给出题人打五星，分五次给的那种。
写完性质 A 时间不多了，就再写了个
剩余十几分钟，倒回去写 T1 的随机生成部分。
这时才发现：自己之前想的算法时间复杂度是错的。
但又突然发现：即使允许
但愿出题人有良心
最后几分钟检查了一下文件名和提交情况，没出什么差错。
赛后
会做 T1 的人似乎很多，而我 T1 拿的部分分还没 T2 多……
T3 倒是公认很难……
等了许久，终于等来了数据，最终得分 36+50+12=98。（T1 全