CSP2022游记

· · 个人记录

考前一定不要复习算法——zxy

Day -1

摆烂的一天，看了下 OI Wiki ，然后睡觉去了。

Day 0

上午开始打板子，打了遍线段树，树剖，淀粉质，觉得没有乐趣，于是把去年没做的 NOIP2021 T1 打了。什么，黄题都打了1h，那寄了。中午突然想起要写团校作业，网上搜了几篇，但没有抄。下午 \color{orange}{Au} 爷zxy讲了一下考场技巧，我表示深有体会，回去之后就摆了。关于我到 8:00 才发现没交团校作业这件事。晚上没有看任何的知识点，美好的一天结束了。

Day 75000006

美好的一天从睡到 10:30 开始，起来依旧很闲，随便翻了几篇 blog 和日报，看了一下有关暴力骗分和随机的小寄巧。下楼随机游走舒缓心情 0.5h，饭后赶到了一中和外校同学们面基候考，等了一个多小时才进去。

Day 1

14:25

当第一下打开 CSP2022.pdf （密码belief2022）时，我对三道图论小清新题感到大受震撼。题面看完后，不出所料没有一道一眼题。我根据多年的寄验，毫不犹豫地开了第一题。

14:35

T1题意[CSP-S 2022] 假期计划，大概是依次选择图上的4个不同点 A,B,C,D，使得满足点 1\rightarrow A,A\rightarrow B,B\rightarrow C,C\rightarrow D,D\rightarrowE 的最短距离 < k。其中点数为 n ，边数为 m。

详细数据点如下。

测试点编号 n \le m \le k \le
1 \sim 3 10 20 0
4 \sim 5 10 20 5
6 \sim 8 20 50 100
9 \sim 11 300 1000 0
12 \sim 14 300 1000 100
15 \sim 17 2500 10000 0
18 \sim 20 2500 10000 100

尝试拿满分，发现还是过于超前了，于是考虑 1~8 的 40pts 发现是送分点，枚举四个点再判断合法即可，时间复杂度 O(n^4)。

14:45

接下来考虑 9-14 的点，想了10分钟发现可以枚举 B,C 两点，这里定义两点距离 \le k 则两点相连，再统计同时与 B 和 1 相连的点作为 A ,同时与 C 和 1 相连的点作为 D ,暴力枚举 A 且满足 A,B,C 三点不同，对于每个 C 把它相连的 D 统计一下排个序，暴力选择前四个即可，为什么是前四个呢？因为 D 可能与 A,B,C 重复。时间复杂度 O(n^3)，可得 70pts。

15:15

然后想了很久，回想 70pts 的做法时脑子突然灵光一闪，既然 C 和其相连的 D 与 B 和其相连的 A 其实是等价的，那么我们可以不枚举 A，直接从 B 相连的点中选择最大的，选 D 同理，但要如何去重呢？其实可以对每个点维护与它相连的点中最大的三个，接着枚举 B,C 优先选择最大的 A 和 D 如果 A 与 c 重复则将 A 推后一个，D 与 B 同理，最后查看 A 与 D 是否重复，若不重复则选择当前的，否则将 A 或 D 推后，时间复杂度 O(n^2)，got 100pts （至少考场上这么认为的）。

15:40

开T2，题意[CSP-S 2022] 策略游戏，大概是两个人，每个人一个数组， q 组询问，询问第一个人在第一个数组的 l_1 到 r_1， 第二个人在第二个数组的 l_2 到 r_2 中分别选择两个数A_i,B_j，使得价值 C_{i,j} 为 A_i\times B_j。第一个人先选。第一个人希望 C_{i,j} 尽量大，第二个人希望 C_{i,j} 尽量小，求两个人最优情况下最终得到的价值。

详细数据点如下。

对于所有数据，1 \le n, m, q \le {10}^5，-{10}^9 \le A_i, B_i \le {10}^9。对于每轮游戏而言，1 \le l_1 \le r_1 \le n，1 \le l_2 \le r_2 \le m。

测试点编号 n, m, q \le 特殊条件
1 200 1, 2
2 200 1
3 200 2
4 \sim 5 200 无
6 1000 1, 2
7 \sim 8 1000 1
9 \sim 10 1000 2
11 \sim 12 1000 无
13 {10}^5 1, 2
14 \sim 15 {10}^5 1
16 \sim 17 {10}^5 2
18 \sim 20 {10}^5 无

其中，特殊性质 1 为：保证 A_i, B_i > 0。
特殊性质 2 为：保证对于每轮游戏而言，要么 l_1 = r_1，要么 l_2 = r_2。

感觉十分套路，分类讨论了一下后发现是个水题。

对于第一个人，如果他选择的数字是正数，第二个人总是会选择尽量小的数字，所以当第二个人不能选负数时，第一个人就选最大的正数，否则选择最小的正数，保证价值最大。

同理，当他选择负数时，第二个人总是会选择尽量大的数字，所以当第二个人不能选正数时，第一个人就选最小的负数，否则选择最大的负数，保证价值最大。

还有一种情况，当第一个人选择 0 时，价值始终为 0，不能遗漏。

于是，可以对 A 维护五个 ST表，分别表示正数最大，正数最小，负数最大，负数最小，以及是否含有 0，对 B 维护两个ST表，分别表示最大，最小，分类讨论即可。

代码细节较多，调了很久。

时间复杂度 O(n\log n + m\log m + q)，got 100pts。

16:50

此时的我意识到一个严重的问题，只剩下 1h40m 了，此时不打暴力，更待何时。于是我开了T3，题意[CSP-S 2022] 星战，大概是一张有向图，q 次修改，每次修改有4种类型，分别是

  1. 断开一条边。
  2. 断开汇集到一个点的所有边。
  3. 连接一条边。
  4. 连接汇集到一个点的所有边。

每次修改后询问图是否同时满足以下条件

  1. 图中所有点出度为 1。
  2. 图中从每一个点出发都可以找到环。

详细数据点

对于所有数据保证：1 \le n \le 5 \times {10}^5，1 \le m \le 5 \times {10}^5，1 \le q \le 5 \times {10}^5。

测试点 n \le m \le q \le 特殊限制
1 \sim 3 10 20 50 无
4 \sim 8 {10}^3 {10}^4 {10}^3 无
9 \sim 10 5 \times {10}^5 5 \times {10}^5 5 \times {10}^5 保证没有 t = 2 和 t = 4 的情况
11 \sim 12 5 \times {10}^5 5 \times {10}^5 5 \times {10}^5 保证没有 t = 4 的情况
13 \sim 16 {10}^5 5 \times {10}^5 5 \times {10}^5 无
17 \sim 20 5 \times {10}^5 5\times 10^5 5 \times {10}^5 无

一看就是不可做题，开始思考暴力。

17:10

猛地发现一个性质，就是第二个判定条件只要判定条件一成立就一定成立。

证明很简单，假设原图分为几个连通块，每一个联通块内的边数一定等于点数，那么总会有点多出一条边形成环，而每个点都有出边，所以总能指向那个环，说白了就是一个有向的基环森林。

于是考虑暴力维护点的出度和删边情况。

对于 1~8 的点，时间复杂度 O(qn)，对于 9~12 的点，时间复杂度 O(q + n)，got 60pts。

此时的我：欸既然这道题这么好骗那正解是不是也不难，逝一逝吧。

18：00

不行了，真的不行了，得开T4暴力了。

题意[CSP-S 2022] 数据传输，大概是一棵树，q 次询问，每次给出起止点，要求将树上任意点以及起点终点设为特殊点，保证将特殊点以某种方式排列时，相邻特殊点在树上的距离 \le k，求所选特殊点权值之和最小值。

详细数据点

测试点 n \le Q \le k = 特殊性质
1 10 10 2 是
2 10 10 3 是
3 200 200 2 是
4 \sim 5 200 200 3 是
6 \sim 7 2000 2000 1 否
8 \sim 9 2000 2000 2 否
10 \sim 11 2000 2000 3 否
12 \sim 13 2 \times {10}^5 2 \times {10}^5 1 否
14 5 \times {10}^4 5 \times {10}^4 2 是
15 \sim 16 {10}^5 {10}^5 2 是
17 \sim 19 2 \times {10}^5 2 \times {10}^5 2 否
20 5 \times {10}^4 5 \times {10}^4 3 是
21 \sim 22 {10}^5 {10}^5 3 是
23 \sim 25 2 \times {10}^5 2 \times {10}^5 3 否

特殊性质：保证 a_i = i + 1，而 b_i 则从 1, 2, \ldots, i 中等概率选取。

由于没有时间，稍微看了看发现打 k = 1 要用 LCA，性价比实在不高。

又看了一下，发现当 k \le 2 时最优答案下所有特殊点都在起点到终点的路径上。

火速打了个暴力 DP ，时间复杂度 O(qn) ，在随机数据下由于树高是 \log 级的，时间复杂度 O(q\log n) ，got 28pts。

18：15

开始检查文件名，文件读入读出和 long long ，检查无误后再看T4。

发现 k = 3 时特殊点最多只可能在链上向外延申一个点，据此可得 76pts 但没时间写了，而且虚拟机坏了，还要去后排调代码，于是放弃了。

最终考场预估分数 100 + 100 + 60 + 28 = 288 pts

Day 25000003

考试结束了，同学在一起吃饭。

这次大家分数普遍偏高，估分基本上都有 200+ ，此时我还没有意识到事情的严重性。

Day 50000005

回家后，在 InfOJ 上交代码，发现T1挂了 35pts QAQ，想法估计没错，估计是代码打错了，但我不是过了拍吗？

于是我永远记住了，对拍不要用太水的数据。

后来在洛谷上交了，T1只挂了 10pts 又有了些期待，希望CCF数据水一些吧。

Day 2

回头想了想T4，发现就是个烂大街的矩阵乘法套 DP 啊啊啊啊我的 72pts 木有了。

InfOJ 上更新了数据，T1少挂了 5pts 但愿官方数据水一点吧（最好像去年T1 n^2 过 70pts），求求了CCF QWQ。

Day 3

改了一天的题，一开始以为T1是没赋初值导致的挂分，改了之后发现还是挂了，于是打了个暴力拍，n = 100 的数据过了 1e6+ 组，十分痛苦。后来呢，猜猜咋地，原图只说了保证有解，没说保证连通，而自造数据是先造了一棵树，于是怎么拍都拍不出不连通。无语了。。。

总结

反正一等奖稳了，没啥好说的。

做题顺序上有点问题，要是最后先开T4就好了，不打矩乘也有 76pts 啊。

前两题整整做了 2h20m，应该做快一点的。

T1对拍太弱了，以后对拍数据造的大一点。

最终得分应该在 250~280pts 。

NOIP2022 RP++