【游记】CSP2022

· · 个人记录

可能更好的阅读体验

Day -?

FZ因不可抗力取消了 CSP，只能线上 VP。

Day 1

上午打 J 组，粗略看了一下四个题，T1 快速幂板子，T2 简单数学，T3 模拟，T4 应该是个 DP，然后就开始码，五分钟把 T1 和 T2 写完了，然后明智地认为 T4 比 T3 好写，就跑去写 T4。

T4 看了一眼题目发现欧几里得距离完全是晃人的，其实就是个曼哈顿距离，然后发现建个 DAG 然后 DP 似乎是 O(n^2k) 的，于是开始码，十分钟过掉了大样例。

然后开始打 T3，发现 | 和 & 的优先级不会处理，然后发现不会处理这玩意也有 80 分，于是愉快地开始码，很快啊，码完了，写的模拟应该问题不大。

估分：100 + 100 + 80 + 100 = 380

民间数据: 100 + 100 + 80 + 100 = 380

下午去打了 S 组，发现似乎是图论专场，看了一眼题目，T1 神秘最短路，T2 一眼 DS，T3 神秘东西没看，T4 我不会的链上 DP。

看了四个题感觉 T2 是比 T1 简单的，于是开始想，然后发现对答案有影响的只有最大正数，最小正数，最大负数，最小负数，再分类一个 0。于是就变成了一个 RMQ 的板子，然后决定写两棵线段树，每棵维护 5 个 tag，然后发现算答案的时候最多带一个 25 的常数，当时没怎么管，写完发现第二个样例没过，手玩了一下发现不对劲，回去看题原来 Q 是可以看到 L 的选择的，改了一下，过了所有样例。

然后回看 T1，既然是无权图第一步显然是用 bfs 求个全源最短路，这一步是 O(n^2) 的，然后如果最暴力枚举四个点的话肯定会炸，所以考虑枚举两个点然后 O(1) 算出剩下的答案，发现第一个点和第四个点都要在 1 号的可达范围，这个性质是很好的，然后我们考虑把所有在 1 号点可达范围的标记一下，预处理一下前三大，然后就是 O(n^2) 的了，写完一发过了大样例。

T3 太神秘了先跳，写了T4 k = 1 的 LCA 板子之后又跑回来看，发现条件等价于每个点的出度都为 1，又发现 O(nq) 的暴力有 40，那赶紧码，然后又打了一个 t 为奇数的分，然后就结束了。

估分：100 + 100 + 50 + 16 = 266

民间数据：100 + 100 + 40 + 16 = 256，T3 还挂分了。

打完之后发现自己被薄纱了，一车人上了 300 甚至 AK，赛后发现 T4 如果每次把链拿出来 DP 就有 68 分，再次证明了我是傻逼的事实。

总结

随着 CSP 的结束，也意味着我学 OI 也有一年了，不管考得再差，也总是这一年的成果，希望明年不要像现在这么菜。