CSP2025游记

xiaoshu2010 · 2025-11-03 16:21:47 · 生活·游记

早上复习了历年 CSP 真题，重点关注了 DP 和贪心，自认为对上述算法有了一定的了解，应该能过前两题。

T1 一眼贪心，10分钟就想出思路，然而没过。我开始质疑自己的结论，花30分钟调假做法，然后发现自己一个数组未清空，且正解不需要使用该数组，于是过了。

T2 显然最小生成树，30分钟调完 \operatorname{O}(2^k(m+nk)\log(m+nk)) 的做法，然后一直在想如何去掉 2^k ，但未成功。

T3 用哈希过前五个测试点，然后注意到性质 A 是一个二维数点，30分钟调完，未能想到进一步的转化。

T4 打了一个显然的状压，未打 m=n 的性质，无进一步的思路。

预计得分：100+64+50+20=234

赛后发现 T2 复杂度可以做到 \operatorname{O}(2^k(m+nk))，该反思了。