CSP-S 2025 游记

yuyc · 2025-11-02 16:25:21 · 生活·游记

开场先通读题面。

T1 猜了个结论推半天式子发现是假的，然后想到可以不管性质直接贪，贪完再调整，写完的时候已经过去了 40 min。

T2 观察到 k \le 10 直接想到 O(2 ^ k\cdot (nk+m) \log (nk + m)) 的暴力做法，写了发现 road2 要跑一秒多，把 vector 改成数组，快了一点，但还是一秒多。

T3 场上不知道在想什么，以为 KMP 能过性质 A，心想着 50 分可太能接受了，懒得再多动一秒钟脑子直接 KMP。实际上复杂度应该是 O(L_1 + nL_2) 的，和 q 无关太难绷了。

T4 在每一档部分分都思考 1s 后决定写暴力走人。

回来给 T2 卡常，原本是 2^k 次排序，改成在一开始就把所有的边排好序，后面选边的时候就不用再排序了。改着改着把正确性改没了，于是准备对拍，结果写 gen 的时候又瞪出错误了。改完之后效果显著，road4 都跑得飞快。

洛谷自测 100 + 80 + 30 + 8 = 218

实际上我考场上的 T2 是拼上了性质 A 的，复现代码的时候怀疑场上数据分治写错了 /jk。

T2 原本想给并查集来个按秩合并，结果最终写成这样了：

void merge(int a,int b){
    int p = find(a),q = find(b);
    fa[p] = q;
    siz[q] += siz[p];
}

到底在干什么啊。。。

原来 T3 不保证 |t_1| =|t_2| 啊。

感觉心态挺好，打的比较松弛，但是貌似太保守了，给的思考时间太少了，写的都是一眼的做法，在 U 群问了一下这个问题，和热心大佬讨论后得出的结论是码力不够要多训 ds 和复杂计数 dp。场上容易犯蠢也是老问题了。

NOIP 加油吧。

Update：100 + 80 + 30 + 8 = 218

一分不多一分不少。