CSP-S 2022 游寄

Day -2

模拟赛被薄纱，矩阵快速幂啥的全部忘完了。

恶补矩阵快速幂。

写了贪吃蛇和一道前缀和优化 DP。

Day -1

考试前一天真的不想做题了，不过还是被 zjj 拉着写了两道组合数学的往年真题。

突然感觉组合数学不算太难了？至少往年的 tg 真题是这样。

晚上。颓洛谷灌水区，在机房巨佬旁边晃悠以得 RP++。

没咋做题，本来说把割点和桥复习一下也摆了，觉得 CSP-S 不会考到，因为要考只可能是模板题，稍微伪装下就直接变成 T4 了，所以觉得不学也无所谓。

Day 0

上午睡到将近 10 点钟才起床。

打了一会音游，性了几首歌，吃完饭就去考点了。

考点排队的人真的多，所以就先去找初中教练和现在的教练去了。被初中教练拉着和初三的同学合了张照然后再在门外转了会就进去了。

因为是明年 WC 的场地，所以机房也都是新机房，并且电脑配置高的吓死人。哪个学校会给机房配 i7 12代啊。

在考场上手冰冷，一直在搓手，不过好像没怎么感觉紧张，可能是一直在下意识深呼吸吧。

赛时

2 点 10 分左右下发了题目，23 左右给了密码。看了一眼题，第一感觉就是怎么全是图论题。

开了 Dev 的自动保存，不过感觉用处不大。

按照开考前看题的感觉，决定做题顺序是 \(1\rightarrow 2 \rightarrow 4 \rightarrow 3\)。

先看 T1，觉得可以先预处理一下每个点 \(k\) 步之内到达的点有哪些，然后可能跑下 DP？觉得预处理的思想应该没错，就先写了预处理的部分。写完了一遍调过然后开始想 DP。突然发现不好 DP，因为要去重，所以换了下思路。发现可以拆成两节然后类似 meet in mid 的思路，想的差不多了就开始写求答案部分。第一遍写出来大样例没过，结果发现是判重点的位置写错了，改完就过了大样例，用时 40 分钟左右。

开 T2，直接一眼看出与 RMQ 有关，所以就先把 ST 表给写出来。先写了 4 个 ST 表来维护两个序列的区间最大最小，然后觉得要分类讨论，就在草稿纸上画了一下，推了 5 分钟差不多推出来了，就开始写代码。第一遍第二个样例没过，发现是有个情况（二者值域都是 \([-,+]\) 的时候）讨论错了，再想了一下发现还需要维护一下 A 的正数最小和负数最大，就再加了两个 ST 表。然后直接过了大样例。至此，才用了 1 小时 30 分钟。

开 T4，先手玩了一下样例，结果发现题读错了，重新看了下，觉得可能 T3 更可做，就转回 T3。

盯了 T3 题面 20 分钟没想到做法，就又跑去看 T4 了。结果 T4 也看了 20 分钟没做出来。对比了下 T3 和 T4，决定先写 T4 的暴力分，因为 T4 暴力分有 44 分可以拿。随便写了个 \(\mathcal O(n^2k)\) 建图然后用 SPFA 代替 Floyd 跑了下全源最短路，直接 \(\mathcal O(1)\) 查询。没花多久过了第三组样例（200 级别），又去看 T3 了。

T3 越看越觉得不可做，所以想暴力怎么写。花了 30 分钟写了个 \(\mathcal O(qn(n+m) \log m)\) 的暴力，希望能拿 20 分左右。然后再去看了一眼 T4 发现还有 \(k=1\) 的情况可做，就写了个 LCA 和树上前缀和，过了自己手造的样例。此时还剩 30 分钟。

回去造了个 T1 的极限数据，结果直接 RE。找了半天的错结果发现是去重的问题，此时还剩下 5 分钟，赶紧加了个 map 去重，测了下大样例和手造极限数据，一发就过了，剩下 2 分钟，祈祷ing……

赛后

出来讨论，都感觉 T2 水，但是有个线段树没调出来。我们几个人均切了 T1 T2，感觉分数线不会太低。

Day +1

洛谷民间数据估分 95 + 100 + ? + 44 = 239 + ?（第三题没数据）。

IOJ 估分 100 + 100 + 40 + 44 = 284。

感觉还行，不过觉得一等线应该不低，毕竟暴力分给太多了。

等小图灵ing……