CSPS2025游寄

· · 生活·游记

初赛阿克了，然后不知道为什么被挂出来展示，所以几乎所有来我们考点考试的人都会看到我的神秘照片。

A 一眼题，B 首先可以只保留原图 MST 上的边，然后可以 2^k 枚举乡村的状态，然后 kruskal 就可以 O(2^kn(\log n+k)) 或 O(2^knk\log n)，但我的脑袋忽然变成了浆糊，于是就直接跳了？还好大样例只跑了 0.05s。

upd：我好像不小心写成 O(2^knk^2) 了，期待挂分。

然后就是一些神秘操作，C 很快会了一个二维数点做法，但是空间看成了 512MB，于是怒写压缩 trie，拍了一个 4.4k 的东西上去。还好过了大样例。

然后就没啥时间做 D 了，随便打了 36pts，最后（可能）会了个 O(n^4) 做法，但是好像巨大难写，没写完就摆了。

upd：其实这个做法是 O(n^3) 的，赛后写了一发过了。但也没啥用了。

总结一下，BC 各犯了一个唐，D 感觉其实也不是不能做的题，怎么会打成这样呢？感觉下周要被拷打说我 flagle 玩太多了，老是分心去做别的事了。

还好这不是 noip。

upd：100+100+100+36=336。冷知识：通过 t2 的方法是多 k 或者少 k。