CSP-S 2022 游记

· · 个人记录

风烛残年选手的游记。

Day -1

又是被 zr 模拟赛吊打的一天。

开始写板子。

Day 0

板子写不动了。

开颓。

又给自己开了 ABC153 当作信心赛，喜提 4 发罚时。

Day 1

坐大巴，坐大巴，坐大巴，坐大巴，坐大巴。坐的人都傻了。

大家看起来心态很好，都在打隔膜。希望在回来的车上也能笑着。

进校排队的时候看到了 dX，靠着同学家长的社牛能力成功嫖到了徽章。？.jpg。

第三次走在杭师大的那条路上，去年的那份激动与自信早已不见，虽然一路上都在给自己暗示，但还是经常想到 csp 爆炸的结果。

到楼下的时候刚好开门，面基失败。

进考场的时候差不多 14:10，立马下了个蓝 Dev，调了下编译选项之后去上了个厕所，回来监考正好贴密码 Belief2022，但到了 14:25 才可以动。

14:25 ：tnnd 为什么密码老是输不对啊，回头转了几圈发现大家好像都不行，觉得不是自己的问题。14:26 是 belief2022 隔壁机房有个考生试出来了（监考原话）。

开始开 T1，一开始看成了中间只用经过 3 个景点，马上想到了枚举中间点对于每个点跑 dij，时间复杂度 O(nm\log m) ，还为中间那个是 m 还是 n 纠结了好久，感觉没道理啊，如果真是这个复杂度的话好怪，可能过不了。过了一会再读了遍题发现边权都是 1，每次直接 O(n) bfs 即可，没有发现读错题了。

接着看 T2，就是让你选给定行的范围内最小值最大的一行的最小值，没仔细推柿子，以为维护两个序列的区间最值就行了。

开 T3，又是又长又臭的题面。整理了一下就是 4 种操作，加边，删边，删去某个点的入边，加上某个点的入边。当且仅当状态是一个基环树森林的时候合法，暴力是 O(nq) 的，可以获得 \text{40 pts}。

大概过了 \text{20 min}，开始正式写代码，\text{20 min} 左右写完了 T1，小样例过不去，画了下图看了样例解释之后发现自己读错题了。冷静思考了下发现可以 O(n^2) 枚举 B,C 两个点，O(n^2) 预处理所有点对间的最短路。对于每个点维护下可以通行的中间点权值最大，次大，次次大的点，对于每对 B,C 枚举下这 9 种组合。\text{1h} 之后过掉了大样例的同时发现大样例很水，很容易挂分。

开始写 T2。为什么还有智障，静态区间 rmq，写线段树啊。先写了两颗只维护区间最大最小值的线段树，样例 1 过不了，发现可能还要再加上个 0，加上之后样例 2 过不了。沉下心来推了下发现在 a,b 中区间正负数的最大最小值还有 0 这五个信息都有可能用到，因为不想写讨论直接写了 2 颗维护这 5 个信息的线段树，最后枚举下组合计算。大样例跑了 \text{1.1s} 应该能过。时间过去了 \text{2h}。

开始写 T3，终于没有任何毛病的写完了 O(nq) 的暴力，过掉了小样例。

战术厕所。

对于 $n \le 200$ 的点写个了 floyd，处理初值的部分写的很丑，不知道 $k=3$ 的时候会不会被卡 T 掉。$\text{ [12,20]pts}$。 对于 $k=1$ 的点就是求树上距离，随便写掉了 $6,7,12,13$ 这 $4$ 个点。 $\text{ [28,36]pts}$。 仔细想了想，对于 $k=2$ 的点上面的 dp 是正确的拿过来，整理了下数据点分治的条件，写掉了 $8,9$ 两个点，过掉了对应样例。 $\text{ [36,44]pts}$。 时间过了 $\text{3h}$ 再一次战术厕所，回来开始想 T3 的特殊性质。 暴力维护下入度为 $1$ 点的个数就又多了 $\text{10pts}$，但是没想到另外 $\text{10 pts}$ 也是一样就可以做了。 后面的时间基本上在摆烂。 回来又坐了 $\text{5h}$ 的大巴，中间顺便吃了个饭，发现人均比我高，但是 T4 树随机那个性质决定了树高不会太大，应该可以过掉点 $4,5,14,15,16$，算上前面的共计 $\text{52pts}$。 大巴上 ZJ 发了代码，用洛谷当天的数据测了好多人的 T1,T2 发现多多少少都有挂分，过掉的人不多。 ## Day 2 1:00 到家了。 2:30 洗完澡，吃完早饭，下了 ZJ 的包看到没问题之后开始 sleep。 12:00 我醒了兄弟们，一日之计在于晨呐！ ## 总分： $100+100+50+56=306

总结：

总体来看还算可以，不过也暴露出来了许多问题：

  1. 没有对拍。写完正解或者部分分尽量跟暴力对拍，不要测完大样例就跑路。这次最大的问题是不是没时间写对拍，而是压根就没想到要对拍。

  2. 码力太弱了，前两题一共写了 \text{2h}，导致后面时间不够充裕。

  3. 仔细读题，这次至少读错了 4 次题面，浪费了很多时间。另外一定要先手模样例，这花不了太多时间，却可以避免很多错误。

  4. 没有深入挖掘性质，T3 的第二个特殊性质分很简单，却没有想到。T4 也没有发现树高的性质，虽然最后还是过了。

  5. 静态查错能力太弱