CSP-S 2022 第二轮 行记

寄

省流

代码

题面

Day -3

考点出来了，在七高考试 总算在成都了。

下午练手写了一道 大模拟 然后被 C++ 的除法向 0 取整坑了几个小时 QWQ

打算明天复习一下模板，避免考试写挂。

Day -2 & -1 & 0

复习了一下板子，简单刷了几道水题，也把之前的真题看了一下。顺带二刷了《命运石之门0》真的好看。

Day 1

早上起床后最后复习了一下板子，不想复习也不想颓废。下午就去考试了。

这次考试全员七高，开车几分钟就到了。然而当时进学校时离考试开始只有 20min 了，就直接进了考场。

进了考场，座位坐在最边上，旁边是 huaruoji。看了一下电脑配置 CPU 是 10 代 i7，配置挺高的。

考试开始前试题发下来了，密码是 belief2022，但愿自己可以和密码想的一样吧。

---

看了一下题，四道题中三道图论，T2 还出现了 CSP/NOIP 万年不出现的博弈题 CCF 没活了可以咬打火机。感觉这次考试不简单。

考试开始后准备做 T1，首先想到的是把图连边，然后跑一遍限制层数的 DFS 即可。连边直接算出两点间距离即可。但这样做需要用 Folyd，预处理的时间复杂度已经达到了 \(O(n^3)\)（考场上脑抽了没想到不带边权的图可直接跑 \(n\) 次 BFS 的复杂度可达 \(O(n^2)\) QAQ），于是这种做法就毙掉了。看数据范围发现 \(k\) 较小，考虑先枚举可行的 \(A\)、\(D\) 点，这样一遍 DFS 即可。然后通过两两枚举可行的 \(A\)、\(D\) 点再计算出 \(B\)、\(C\) 两点。然而这种做法随便出个菊花图就被卡掉了。又想了各种做法，但都发现不够优。此时已经过了 1.5h，代码还一笔没动，有点慌就去开 T2 了。

接下来看了一下 T2，反而发现此题极水。只需要开线段树或 ST 表维护 \(a\) 的最大值、最小值、负数最大值、正数最小值、\(0\) 的个数和 \(b\) 的最大值、最小值即可。然后询问的时候先查询 \(b\) 的最大值 \(\text{maxB}\) 和最小值 \(\text{minB}\)，两者同号则在 \(a\) 中尽量取异号绝对值最大，没有异号则取同号绝对值最小。若 \(\text{maxB}\) 和 \(\text{minB}\) 两者异号则取 \(a\) 中绝对值最小即可。于是考场上直接开了 \(6\) 颗线段树用了 40min 把这道题大样例过了。预估 100 pts。

然后看 T3，花了 10min 理解了一下题意。简单分析了一下发现只要每个点的出度为 \(1\) 就可进行反攻。于是开了邻接矩阵，直接存边和边是否可用。然后暴力加边删边，写了个 \(O(n^2)\) 的程序。预估 40pts。此时距离考试结束还有 1.5h。接下来就开始了这场考试的崩坏。。。

看了一下 T4，感觉不太可做就去看 T1 了，没看部分分就没想到 \(k = 1\) 时直接写个 LCA 就行了 QAQ。然后想了一会儿 T1 仍然想不出正解就打暴力。然而开始写 T1 的时候没看到输入“第二行包含 \(n - 1\) 个正整数”于是考试时写的是输入 \(n\) 个数，考试时又一直用文件输入输出，于是暴力就写挂了 70pts 没了 QAQ。

Day 2

心态挺爆炸的，测了一下民间数据 0 + 100 + 40 + 0 = 140pts，身边的人都是 200+ 和 300+，铁省二了，按照自己的能力至少可以拿到 70 + 100 + 40 + 16 = 226pts 的 /kk

看来读题和写暴力的能力还是要好好注意一下，写完程序后和题面逐字对照一下可能会好一点。

最后看了一下，T3 考的是万年不考的哈希，T4 DDP，在联赛中全是不常见的知识点，得好好拓展一下知识面了。

Day ???

0 + 95 + 40 + 0 = 135pts，今年这 CCF 出的数据不是一般的烂，T3 全输出 NO 有 45pts 然而我并没有这样干。。。