CSP-S 2024 游记
lichenghan · · 生活·游记
J 组没去，上午 睡大觉 + 水群。
13:15 午休起床，赶往考点。似乎是卡着点到的。
14:28 解压。由于试图使用 PDF 密码解压压缩包，错了好几次（
备份样例……建文件夹……调 Dev-C++ 配色……调 cmd 窗口……最后确实是在 14:30 整开始做题的。
开 A。发现可以从小到大维护这个过程，
总之十分钟写完了。
开 B。超速的位置显然是一段区间，然后是经典贪心题。但是由于一开始定义不清，上下取整调了半天。
开 C。首先一眼的平方 DP，然后再把一维扔上值域，似乎做完了。
“写线段树……（10min）……复杂度好像高了……哦可以树状数组……（5min）……哦可以数组……”
能把三个做法写一遍也是无敌了。浪费时间。写完大概总时长 2h？记不清了。
开 D。大概可以用线段树，但没细想。数据范围提示线性，我不相信我的卡常技巧。
（注：以下讨论中，称一个节点“确定”当且仅当其胜者已经确定）
进行了大约 30min 的形如“如果擂主@#%&，非擂主*&$%，结果是什么？”的观察，发现：
-
如果淘汰树上的一个节点已经确定，且它是擂主，且此节点赢家可以继续赢，那么可以确定它的父亲。（废话，这不就是题面吗！）
-
如果淘汰树上的某节点的两个儿子都已经确定，则该节点也确定。（废话+1）
-
一个人的实力大于其到根路径上“最高”的擂主高度是这个人赢下整场比赛的必要条件。也就是说，他要赢下每一场作为擂主的比赛。（废话+2）
-
在按照 1. 2. 规则确定节点后，如果一个节点已经确定，但是其父亲未确定，则对于这个节点的胜者，条件 3 是充分的。 这是因为，这个胜者此后遇到的对手，要么是“替补选手”（此时很容易构造），要么不是擂主，要么是注定赢不了的擂主。所以这个人只需要满足条件 3，即赢下到根的路径上所有非擂主即可。
所以开个栈维护当前确定，且父亲不存在或不确定的节点就行。需要亿点预处理和亿点细节，但是时间复杂度
此时剩余时间 100min。
大概琢磨了下细节，上厕所，洗脸，把所有变量名的含义写在草稿纸上，开写！
……70min later……
哈！小样例过了！
哈？大样例错了？（心脏骤停）
诶？为什么我只回答了一点点询问？
哦哦哦，一个时刻可以被询问多次……
……（2min）……
大样例过了。（心肺复苏）
开 NOI Linux，检查 checker.exe，FileIO，调试信息……
……（15min）……
D 好像没有极限样例？造一组。
哈？RE？（心脏骤停）
哦哦哦数据造错了……（心肺复苏）
最后，通读所有代码全文。
18:28 The End.
估分
花絮
before
候考室里，HF 图寻组和 HF 斗地主组正欢乐地“准备”着接下来的比赛。
前往机房的路上，有同校的同学正在进行暴戾语言含量较高的讨论，素质不是很高。
after
监考员宣布可以离场时，前排的 qsc 同学发出了尖锐的爆鸣声。他 T4 的单
继续水群。好像 T4 写线性的人不多？咋都会卡常 qwq。
晚上去珠江边走走。突然发现，我刚才一直处于兴奋状态，完全没感觉，其实已经非常累了。
打算早点睡觉，但是由于考试时灌的咖啡，直到 00:00 后才睡着。
RP++，继续努力。
upd 10.28
今日与同学交谈得知，D 其实有 5 组样例，但是我在 cmd 中进行了以下操作：
E:/GD-xxxxx/color> dir
...
1.in
1.out
2.in
2.out
...
E:/GD-xxxxx/color> cd ..
E:/GD-xxxxx> cd arena
E:/GD-xxxxx/arena>然后我开始做 D。这导致我以为只有两组样例。
我就说样例咋这么小。
啊啊啊不会挂分吧……