CSP-S 2023 游记

初赛

95.5，已经忘了错了哪些题了，没去年做的好。省里有一个 97 的，非常厉害。

不过初赛成绩也不是很重要。

Day -2

模拟赛，打出了 300 的高分，如果在打点部分分能轻松拿下联考 rank 1，感觉手感很不错。

Day -1

模拟赛，打出了 395 的高分。C wa 了 5 pts，我的做法大概是假的，那就是运气比较好。

Day 1

（突然发现这个日期编号好像是把 0 扣掉比较符合直觉）

上午直接睡大觉睡到了 11 点，准考证和承诺书也没打，爬起来打开电脑和打印机，发现这个 canon 打印机无法识别黑色墨盒，搞了半天也没修好，不知道是第三方墨盒不靠谱还是我的使用问题。最后没办法，跑到小区在路边新装的自助打印柜机去当了回冤大头，单面黑白一张一块钱，这简直就是抢钱，但是我也只能给他抢。

顺便去便利店买了两瓶咖啡塞书包里，第二瓶 3 元。

打了个车去华科，这次到的很早，以前我都是踩点的，但是在外面排队排了不少时间，不知道为啥需要排队这个环节。

拿到机器打开 vscode 和 wsl，打了个 template，华科的机子真是好用，vscode 有 c++ extension 可以离线提供简单的代码补全，wsl 可以直接使用 asan 和 ubsan。不过要是换套键鼠然后把桌上的线整理一下会更好。

14:30 先开 t1，怀疑自己拿的是普及组的题，但是看了看确实是提高组，直接敲个搜索走人。

然后发现 t2 好像有点困难。首先这是个类似括号匹配的东西，那么就有了一个 $O(n^3)$ 的区间 dp 做法，但是这几乎没分，感觉很没思路。想了相当一段时间，联想到正常括号匹配可以构建一个栈的结构，那么同样的思路也可以套用到这题当中，不难证明直接贪心匹配是正确的，这样暴力做就 $O(n^2)$ 了。我们要求的是从某个点开始空栈的次数，这个很容易发现第一次空栈后剩余的部分就是个子问题，于是可以 dp。设 $nxt_i$ 表示 $i$ 入栈后第一次空栈的位置，那么求 $nxt_i$ 时，我们先考虑 $i+1$，若 $s_{i+1}\ne s_i$，则考虑 $nxt_{i+1}+1$，下一个候选将是 $nxt_{nxt_{i+1}+1}+1$，以此类推。不妨对于每个点处理出每个字母最后会跳到哪里，这样即可做到 $O(n|\Sigma|)$，可以通过。另外这题好像暴力跳也是对的，但是我还没有严谨证明，不过那种复杂度至少也是 $O(n|\Sigma|)$。很相似的题目：CF1223F Stack Exterminable Arrays。值域扩大到 $O(n)$，上面的做法不能直接套用，可以上主席树，当然也有其他做法。

看到 t3 就感觉十分震撼，不过读了一下觉得并不难写，直接开冲。写了不知道多久就写完了，然后发现关于对齐的部分读错题了，不过好在简单改一下就好了。我代码里没有使用任何 map 或二分之类的东西，全是暴力扫，暴力字符串匹配，所以又花了很长时间算复杂度，最后结论是复杂度为 $O(n^3L)$，其中 $L$ 为字符串最大长度，本题中 $L=10$，所以应该没啥问题。

其实前面的按理来说也还好，但是可能我比较磨蹭，总之到了 t4 只剩 50 min 不到的时间了。看到 t4 首先发现树的生长是一个分段一次函数，之前模拟赛做过个跟分段一次函数有关的东西，有点 ptsd，觉得这题很困难。后来由于这题就是要让树木生长到目标高度的最大时间最小，我说总得有个二分吧，想到二分之后发现这题变得极其简单，可以算出每个点最晚需要在什么时间种树，然后在树上跑一个类似子树 min 的东西，用 hall 定理或直接贪心判定是否可行即可。总复杂度大概是 $2\log$。想到这里只剩 20 min 多一点，已经没什么时间写了，但还是想挣扎一下，于是先写了求从 $s$ 时刻开始什么时候能长到目标高度的函数，这玩意细节巨多，写完这个就只够我拿最简单的链的部分分了，随便打了一打。

检查所有文件，所有代码重新编译一遍，交卷。

出来自测发现 t4 那个函数还是写错了，所以一分也没有。

虽然睡觉时间够了但考试还是困，我觉得咖啡还是有帮助的。另外我考试期间大概喝了超过 1 升的水，不过一次厕所也没上，有点离谱。

最后的估分是 100+100+100+0=300。并不是完美发挥。时间分配和速度有待加强。

湖北有人 ak 了，orz。

Day 2

继续睡觉睡到中午。

13:00 打华科新生赛。题目其实挺简单的。我比较喜欢 B 和 E，这个 G 和 H 出的真是意义不明，然后 D 我现在还是不会证那个结论。赛时通过 12 题，线上排名第 5，H 没来得及写完，大概因为比赛期间有的时候在摸鱼，要不然就 13 题了。感觉打得还不错。

问题在于好像无论是线下赛还是线上赛都不给武汉市且非华科学生的参赛者发奖，真的不知道为啥。

休息了一个小时，19:05 继续开始晚上的 CF Div.1，开始的时候感觉自己已经有点困了，a1 写完还纠结了一下自己到底要不要交，还是干脆不打了算了。最后下定决心交了。运气很好的很快找出了 a2 的结论，其实这个匹配的限制很弱，意识到了这点后题目其实极其简单，但问题在于很容易被平时做过的匹配题思路带偏。b 可以用类似 dijkstra 的方式做，c 对序列维扫描线逐位贪心即可，每次需要删除所有不是最小值的位，由于每一位最多被删一次，适用均摊分析，每次暴力删即可。此时大概是 1h 多一点，排名最高是 80 左右，已经是历史最佳了。

d 想了很长时间没有思路，一直都在考虑区间内的前缀 max，后缀 min，rank 之类的东西，然而这些都不方便维护。最后快结束了想到能不能对每个元素算其能作为左边部分最大值贡献到的区间，但是具体细节有些问题，于是这题最后也没能通过。不过这已经很接近正解了。

这次 system test 和 rating calculation 都很快，+105 成功升上 IM，达成了 2023 年终目标，很舒服。

希望这种状态能持续长一点的时间吧。

本作品采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可。