CSP2025游记、总结

· · 生活·游记

Day0

今天是攒rp的好时候，有一点点小紧张，然而不重要。

看了 Alex_Wei 的博客，就是发的那个。感觉里面的东西很全，一些 dp 优化的东西诸如二分队列我好像还不是很熟悉，晚上看了图论，里面没有字符串，也没有数数寄巧（也不需要就是了）。

Day1

上午：看了下 考试策略 感觉对 Linux 用的更好了，之前都不是很会开时空间的，到机房试一试，发现电脑根本跑不动虚拟机...，中午吃了点清淡的饭菜，喝了杯喜欢的奈茶，回培训室睡觉。

睡姿不是很固定。13:12 醒来，洗了把脸，感觉国际部的沙发很适合睡，遂躺到 13:25。

开车，车上咋有股味...

下车后看到了很多熟悉的人，但是在考试前还是少和别人说话比较好，保持清净应该是最好的准备。

lwy来找我说话，不太想理他，排队也是留到了后面。

进考场，想着先干个300。

T1：并不太难，看出来了不管限制直接贪心做的话，只有一组会大于 \frac{n}{2} 对这组调整到别的组只到只剩下 \frac{n}{2} 个就可以了，20min过关。

T2：生成树问题，看起来就是要从 Kruskal 的角度考虑，产生两种思路：

  1. 先建立出 n 个点的 MST 然后再去加特殊点解决一些位置。

  2. 先建立出 n+k 个点的 MST 然后再去删掉一些特殊点解决一些位置。

注意到 k\le10 但是 m\le10^6，n\le10^4 可能要用到 2^k 这个东西，想了一下枚举玩 2^k 后还是要做最小生成树，然后还是 m\text{log}m 不太可行，做一个 O(n 2^k) 的状压 dp 可行吗？不太可行因为转移要枚举状态。丝毫没有注意到后面的最小生成树只需要 kn\text{log}(kn) 的复杂度因为只会用到原图最小生成树上的那几条边。

考虑想法2，自己画了个图，刚好可以通过特殊性质 A，感觉正解应该就是从这个出发的了。

首先这 k 个点应该是不会互相干扰的，至少在我的草稿纸上是这样，那么我们可以依次删除这 k 个点，看一看是不是会使得答案变小，产生了一个 km\text{log}m 的假做法，当时看着这个复杂度感觉很对，而且如果精细的写的话显然是跑不满的，不急，不动手。

仔细想一想开始手膜样例，发现芜湖，挂了，删掉一个额外点之后其他点可能出来捣乱，连上原来的点，这样就不是独立的了。

这还说啥呢，此时时间已经迫近 16:30 而我还只有不到200，我慌了。

想起去年的5min想出，3h调不出T2。一模自己的脸庞，不知何时已经烫得啥样了(没错就是晚上开个风暖洗热水澡的感觉)。

抬头一看有同机房认识的人，似乎还没过 T2。

那还有啥好说的，写完暴力跳呗？说不定 T2 很难，效仿 noip2022 呢？（其实很脑残）

看了下后面两题，大概知道要考啥，有一道计数，说不定能做。

挣扎到 16:30 不想再挣扎了，写完了暴力，大概 16:45。

挣扎的时间不多了，开始像 T3，这个题先入为主的感觉应该是用 hash 做（大纲里只有hash和kmp），那就先把查询串中不同的那一段牢下来，然后 L^2 做hash这是最基础的暴力（没想到给的模式串也可以做一样的操作，纯！）

然后就不会性质 A，看着应该不向太难啊（彻底红温），此时注意到 |t1|=|t2| 不一定成立，此时答案为 0。但很快就忘掉了（因为红温），大概想到可以用 AC 自动机维护，但这玩意不在联赛范围内（谁说一定要在呢？）。

似乎会了性质 B，按照b的位置差值分类之后可以转换成一个简单的二维数点问题！！！

好的写哈希就已经写了好一阵子，因为 T2的缘故没有任何时间了！！！

丸辣，彻底费拉！哈希还写崩了！调了一阵子调出来！

本来抱期望的 T4 也毁了，没有任何时间了，急忙拼好分拼完了。

估分算了太羞耻了，并且还出现了 T3 这样的神坑。

接下来按照许老师的话语来执行，确实没啥好担心的。

各位不必太过担心，历年选手CSP挂的分，都会在NOIP补回来，只要接下来四周：

知耻后勇，保持高昂斗志

不再摸鱼，专注题目本身

对照大纲，拒绝胡乱刷题

大纲外的常用知识点还是可以做一做的（比如T3）。

{\color{white}希望能晚点再到班上见到周依涵qwq}

qwq。

结束了：100+56+35+12=203，没啥好说的，noip加油吧