CSP2023游记

文中杜赢指do_while_true.

Day -n

开始停课, 打了4场模拟赛, 第一场爆了一个标, 剩下的都挺寄.

Day 0

上午复习数位dp, 看以前的blog, 中午出发, 晚上到达日照一个民宿, 晚霞很好!

试机, 抽到win10. 发现虚拟机不能用, 说晚上解决. 机子上放了3个不同的mingw, 最后只有dev自带的那个能用. 但是机子配了vscode, 即使没有c++插件也是vscode, 即使没有虚拟机也是vscode. 最可惜的是没有python. 考试过程中习惯性拿python当计算器/暴力弹出的是微软商店. 面到杜赢, 他们机房虚拟机能用. 面到whc, 面到一个也来打比赛的初中同学.

晚上复习圆方树, 虚树, kmp. 没有python于是背了一个bat对拍板子.

Day 1 比赛

上午又看了看字符串打开知乎, 听说普及组某机房没断网(问号脸). 特意带了杯咖啡和零食, 切一个题吃一个.

提前30min左右进场, 配vscode, 打了空模板, 考场大概提前几分钟给了压缩包密码, 压缩包里看到名字”tree”打一个存树的模板, 看”struct”大样例猜是结构体对齐之类的模拟猜是T1(大模拟放T3? ? ), lock不知道是什么, game像个数数题, 但有字符串, 果断打一个kmp一个sam. 都没用上. 提醒自己去年寄大了今年要稳打要写对拍.

开题先看30min, 看T1, 想了1min发现诶好像不用计数可以枚举. 看T2, 这莫不是原, 发现在杜赢OJ上做过, 现在都这么搬题了吗? 看T3, 大模拟! 看T4, 暂时没思路, 先写前面的.

大概15min过了T1, 正解就是暴力就只测两组手造样例没拍.

然后写T2, 记得正解是dp, 但直接模拟括号序列匹配对过程中的栈哈希的做法也能过(甚至先学到的就是这种). 当时做杜赢OJ单hash会寄就写了个任意重hash的, 写unordered_map自定义hash函数, CE10min, 先用map, 发现大样例单hash果然过不了换双, 结果极限数据要跑2s. 于是还是得环unordered_map. 给自定义hash函数所有地方加上const终于不CE进了1s, 但是也塞不下3hash的时间了. 发现自己平时没背模数, 选择了1e9+7和998244853(出题人就算卡, 也想不到我用的居然不是998244353? ). 搞完T2记得大概还剩下2. 5h. 要是平常背背pbds的hashmap是不是能更稳一点.

再不开咖啡就来不及了, 喝咖啡.

开T3, 大模拟, 发现它还是能用类型套出 $10^{18}$ 的内存占用的, 一个一个操作的写很快就写完了, 然后调了一会发现自己印象里的结构体对齐和它的不一样(题目中结构体中的第 $i$ 个变量对 $a_i$ 对齐, 而不是对 $\max_j a_j$ 对齐), 改过来过大样例, 现在还剩1. 5h.

想T4, 能种树的形状很难dp且同一个父亲的不同兄弟之间不能独立出来, 感觉不是dp. 想二分答案, 然后发现可以忽略 $a, b, c$ 找到每个点 $u$ 最晚必须被种的时间 $t_u$, 因为排除了dp只能是贪心, 发现对于点 $u, v$, 若当前状态分别需要 $d_u, d_v$ 步能在它们的位置种下树, 那么一定要 $d_u\le t_u, d_v\le t_v$, 先种 $u$ 再种 $v$ 要求 $d_u+d_v\le t_v$, 先 $v$ 要求 $d_u+d_v\le t_u$, 于是直接按 $t$ 排序模拟应该就是对的. 那模拟只要暴力跳父亲就是均摊线性, 总复杂度是二分log和内层排序/算 $t$ 二分log一共2log, 开冲, 调完测大样例答案是对的但最后一个T了.

二分算 $t$ 可以不二分直接解方程, 于是开始改解方程, 发现根本解不对, 一直解到还有40min, 先复制出一个原版的测一下过了大样例, 又把其它3个题拖进noi linux里测, 发现T2在 longlong 数组初始化写1e9+7在 noi linux 里会报错紧急修了. 然后接着解方程解到最后没解出来交了2log大概是寄了.

Day 1 比赛结束

面到杜赢一问他不挂分就AK了, 但T2写的dp, 我说这是你们学校OJ上原题, T4写的是2log且过了1s而且做法不一样, 开始怀疑我的贪心, 还没等讨论T4杜赢说他正在约npy(? ? ? )就扔下我走了. 出来的时候没面到人.

带进去一包零食都忘拿了, 捐CCF肉铺能加分吗?

发现WJQ会T4并且也不一样(二分+树剖之类的没有懂), 于是开摆

深夜教练发来代码, 但我已经关电脑了. 发来说云斗390, 到前面有两个400, 但这仍然是挂分挂的最少的一次.

Day2

因为前一天的民测令人震撼, 就又开洛谷测了一遍也是390, zyb测的榜也是390, T42logTLE了两个点, 都在1. 2s以内. 然后大概20min就从2log上重写了一遍解方程版本调出来过了云斗, 测luogu1WA1RE, 发现WA是边界错误云斗没测出来, RE是数据里有 $b=0, c=0$ 的点. 好像考试从最后1h就开始心跳加速了脑子比较急, 方程的式子错了也没检查出来. (赛时十年功, 赛后一分钟)

杜赢大模拟寄了/kk/kk/kk T4 $\log^2$ T了 /kk/kk/kk AK失败

在山上看日出.