csp2025游记

AvisD · 2025-11-17 20:58:17 · 生活·游记

按照我之前考得差就不写游记的秉性，这篇文章不会问世。

但是想了想又不是我不写游记这场比赛就没打过，所以还是写了。

接近傍晚 4 点，我坐着大巴车来到了杭师大前的亚朵酒店。

晚上不知道为啥就是睡不着。

失眠了很久，实在无聊到想知道现在几点时，闹钟上的数字告诉我，现在已经是 11 月 1 日的 6 点了。

早上又睡了 3 个小时来补充精神，但是在此期间我落枕了。

午饭前背了我所不熟悉的 tarjan 板子和对拍板子，遗憾的是考场上我完全没有用到。

午饭后的两个小时又简单复习了一下，到了 2 点，我就去考场了。

在门口逗留一会儿到 2 点 10 分时，我进场了。

座位对面是 lottle。

忐忑地等了一会儿，比赛开始了。

我先飞速地划了一下 pdf，发现四道题题面都挺长，再回来看 T1。

几乎一秒钟，我就想到先让所有人到它最大值的地方去，然后再做调整。

调整我想了一会儿，怕调整完其他两个位置也满了。

但幸好只是一会儿我头脑就清醒了，这种情况不可能发生，于是我会 t1 了。

大概不到半小时，我过了 t1，接着我打开 t2 题面。

t2 我场上好像，一开始没看见城市和乡镇的区别。

我注意到，k 很小，所以很自然地想到 2^k，再归并边权做最小生成树，我认为这个东西的复杂度是 O(2^knk)，实际上是 O(2^k(m+nk)\log(m+nk))。

把这个写出来之后，我才发现复杂度爆了。

进一步思考了一会儿，我发现 m 条边是冗余的，只要保存原图最小生成树的边就好了。

所以我再修改了一下，写了一个我认为复杂度是 O(2^knk)，实际上是 O(2^k nk \log nk) 的代码。

把这个写出来之后，我发现复杂度错了，但并不是发现并查集也有 \log 的复杂度，而是发现我的归并写得很差，导致每次都有 k 的复杂度。

于是我又修改了一下代码，写出了一个我认为复杂度是 O(2^knk) 的东西。

这时候时间是 4 点，我划到 pdf 下一页，去看 t3 的题面了。

看完了题面，我就想到了 AC 自动机。经过一番思考后，我认为我会了这题，于是就开始写了。

我当时的思路，是对 s_{i,1} 和 s_{i,2} 分别建 AC 自动机，然后查询的时候拿 t_1 和 t_2 在上面做匹配，每次到一个点的时候加上权值。

显然易见，这个做法错完了，然而我直到测样例的时候才发现它假了。

我有两个问题：一是必须要建出 fail 树，在这棵树上查询；二是要注意 lcs 和 lcp的大小，fail树上的查询的点必须要大于等于某个值，这可以用倍增。

到这里的思路还是对的，但是这时候我一点都没想到离线处理查询，一直在想在线做法。

我先写出了建 fail 树的流程，然后乱七八糟地又建了一棵树，类似虚树，只包含 s_i 的点，然后我还是不会查询，没有想到离线偏序。

大概到五点半，仅剩一个小时的时候，我终于放弃了，注释掉了 t3 之前写的所有代码。

接下来我就写了两个低档暴力：t3 的 O(nL) 做法，关于 lcp 和 lcs 加了一点优化，和 t4 的状压做法，测完样例调完后，已经是 18:20 了。

就这样结束了吗？剩下的十分钟，我这样想着。

考试结束了，lottle 坐在我对面，所以我一结束就和他交流了题目。

经他提醒我发现了 t2 的复杂度问题，所以心情急转直下了。

估分是 100+100+25+20，当时觉得 t2 也有可能挂。

出分 100+100+50+20 ？

t2 是没人会卡路径压缩再加上一些小优化过了，t3 是因为小优化倒挂了 20。