CSP-S 2022 游记

· · 个人记录

Day 0

主要是看了一下模拟赛题和自己的写的总结。

听说 LNBS 今年的系统换成 Windows 10 了。希望今年的键盘比较好用。

Day 1

三句话总结：因为没对拍而挂分。代码能力不够。因祸得福。

很烦的是系统还是 Windows 7，键盘还是一如既往的恶心……

先开了 T1，一眼鉴定为预处理长为 1 的最短路后折半，维护最大 / 次大 / 次次大，然后合并一下即可。

写完 + 调过大样例大概是 14:50，赶紧去看 T2。最开始以为 a_i, b_i \geq 0，然后想这不是 sb 题吗。然后当我看到数据范围：

于是意识到这道题要大讨论。然后写了 6 个 ST 表，等我写完了发现过不了大样例 /fn

不是很想调大讨论，于是先去看了 T3。题目描述巨长无比，看完了本来以为还要动态维护内向基环树森林，然后突然意识到出度为 1 等价于内向基环树森林，同时意味着每个点都可以到达一个环。

大型诈骗！！！但是除了暴力没啥想法，本来以为可以根号分治，然后萎了 /ll

于是先去写了暴力，然后去看 T4。暴力是显然的，Dijkstra 跑最短路即可。k = 1 也是显然的——可以直接树上前缀和 + LCA（这是伏笔）。写完了大概是 15:40，赶紧去调 T2。又理了一下思路，很快就调出来了。这时大概 16:00。

然后有想了一会 T3，感觉不太可做，于是去做 T4。

看到 k 很小，先来考虑 k = 2。

注意到有巨多随机数据的分，那数据随机时有什么性质呢？

就设 $dp_i$ 表示现在到链上第 $i$ 个点了，然后每个点可以由上一个或上上一个转移过来。然后把这档分写了，这时大概 $16:20$。 突然想到这是可以 ddp 的：你显然可以用一个 $2 \times 2$ 的矩阵来描述这个转移。然后去写了 $k = 2$ 的倍增 + 矩阵的 ddp。调完了大概 $17:00$。 开始考虑 $k = 3$，应该也是要 ddp 的。然后先考虑了一个暴力 dp，然后开写。然后尝试过一下大样例，然后《找 不 到 相 同》/fn 然后开始对拍 $n = 10$ 左右的数据，拍不出错？？？调大到 $n = 100$ 还是不出错，但调到 $n = 10^3$ 立马出错？？？ 然后我无语了，开始脑补可能是哪里错了，改了很久还是找不到相同…… 此刻我突然发现**我没有注释我的拼盘**！！！我代码里写的是 $n \leq 200$ 跑暴力，难怪…… 然后把拼盘注释了，$n = 50$ 立马出错…… 我把错误的东西抓出来，然后发现好像 $k = 3$ 时你可以跑到这条链外面去以获得更优的答案？ 于是我打了个补丁，但过了几组后又错了…… 这时已经 $18:00$ 了，我决定先去对拍。我花了大概 $10$ 分钟拍完了 T1/2，不过 T4 的 $k = 1, 2$ 没拍（伏笔 $\times 2$）。 然后我回去看 T4 的拍出错的地方，然后发现**这玩意你可以连续若干次都在链外面啊**！！！ 于是把 dp 改成二维的 $dp_{i, 0/1/2}$ 表示在离链上第 $i$ 个点距离为 $0/1/2$ 的某个权值最小的点，然后每次再枚举上一步离链的距离来转移。 最终在 $18:25$ 调过了大样例。这玩意显然是可以用一个 $6 \times 6$ 的矩阵来描述的 ddp，但我真的没时间写了…… 检查了一下文件名、`freopen` 之类的东西时间就到了。 最开始期望得分 $100 + 100 + 50 + 88 = 338$。 等有了民间数据，我才发现： - C 题暴力事实上有 $60$ 分。 - D 题我写挂了 $k = 1$。（回收伏笔） 于是目前期望得分为 $100 + 100 + 60 + 72 = 332$。~~还好，$300$ 分保住了！！！~~ 然后发生了更魔幻的事情：我拿到代码后花了半个小时改了 T4 的 $k = 1$ 并写完了 $k = 3$ 的 ddp。然而等我交到 InfOJ 上一测： ``` answer.code: In function ‘void dfs(int, int)’: answer.code:36:9: error: reference to ‘size’ is ambiguous 36 | size[u] = 1; | ^~~~ In file included from /usr/include/c++/11/string:54, from /usr/include/c++/11/bits/locale_classes.h:40, from /usr/include/c++/11/bits/ios_base.h:41, from /usr/include/c++/11/ios:42, from /usr/include/c++/11/ostream:38, from /usr/include/c++/11/iostream... ``` 额，我看到这玩意就想起了我在昨天的闲话中提到了这一条—— `size` 为关键字——然而这种事情赛时真没想起来…… 好吧，就算因祸得福了（ ------------ 就题目本身的话： - T1：bfs 求长为 $1$ 的最短路 + 维护最大 / 次大 / 次次大 + 折半。 - T2：大讨论贪心 + ST 表。 - T3：内向基环森林性质 + 哈希。 - T4：倍增 / 树剖 + ddp。 # Day 10 出成绩了，官方数据 $100 + 100 + 60 + 72 = 332$，一分没挂。 # Day 20 今天申诉结束，发获奖名单了。 看了一下省排 rk24，就算把初中和高三同学去掉也只有 rk18 /ll ~~幻想时间：要是我没有写挂 T4 的 $k = 1$，就可以有 348pts，但还是只有 rk14 /ll~~ ~~更加幻想的时间：要是我没写挂 T4 且 T3 加了卡时，就可以有 388pts，就可以有 rk2 了 /se~~ 幻想时间结束（ 这次 CSP 可以带给我什么呢？ - 无论哪道题，只要写的不是最纯粹的暴力，就一定要对拍。求稳远远比虚妄地期望自己最后 10min 切题更重要。 - 充分发扬乱搞精神——打表找规律、剪枝、卡时、卡常、随机化、模拟退火，如果有时间尽量骗分。说不定你还会在乱搞时突然想到正解。~~相信 CCF 的数据比你自己构造的水。~~ - 不要奢望自己可以写出大数据结构。 最后膜拜 400pts 学长 william555 和 360pts 学弟 goujingyu /bx