CSP2025游记

· · 生活·游记

不知道怎么评价这次比赛。

前几天在家里面写题，没怎么出去。

应该是学籍的原因，我在创新港的学校所以我的考点是在高新一中沣东中学。

普及组

一开始快速看了几个题看到第二题的图差点吓死了，以前写数学题经常被这种找规律题创私。

把前两个题写完之后，开始写第三题，第三题没写正解，写了一个神秘 \text{O}(n^2) 的 dp，当时我认为这个不可能对。大概就是令 dp_i 就是截止到 i 结尾，最多多少个合法区间，f_i=\min\{dp_1,dp_2,...,dp_i\}，转移就是 dp_r =\max(dp_r,f_{l-1}+\operatorname{check}(l,r)) 这样，再用前缀异或和来优化 \text{check}。\text{check} 函数就是看一段区间合不合法，合法为 0 否则为 0。

第四题看了一下题，没什么思路就写了 n\le 20 的暴力和 a_i=1 的部分，a_i=1 答案显然是 2^n -n-\frac{n\times(n-1)}{2}，但是赛后和同学讨论的时候发现 a_i=1 这里似乎没开长整型可能会挂。

预估 100+100+60+60-20=300。

没开长整数导致的。

提高组

虽然说是主战场，但我觉得是火葬场。

都什么神仙题目。

第一题想了一个解法：每次看一个人最合适去哪里，如果合适的团队还有空位就加进去；没有了就看满意度最小的，如果当前的满意度大于团队最小满意度就把这个贡献最小的人拿出来，把新人加进去，再考虑加入次小，最小；如果新人贡献比最低贡献还要小就考虑次小，最小。每次考虑都和最低贡献进行比较。

当时只打了 \text{O}(n^3) 的暴力，没有想到可以对于 n\le200 的部分写个 dp。

第二题疑似想到正解了，就是枚举哪些村庄需要升级然后挨个跑 mst，但是当时在跑完 mst 之后没有删去村庄与城市之间的边也没看出来。

后两题不懂。

估分：20+0+0+0=20

总结：拉爆了

还有就是避雷一下高新一中沣东中学的考点，超绝 win7 没有 edge，我用的那台电脑是清朝老机时间显示 2017 年。测试样例的时候甚至不能用 Crtlv 来粘贴到 exe，需要手动粘贴。写个死循环或者递归就能把电脑安全管家炸出来，屏幕没我准考证大。键盘神仙键位空格不知道被谁摁烂了键盘上还有关机按键趁别人不注意直接现场 jc。感觉整个机房都是拿纸糊的。

我感觉唯一的优点就是 win7 电脑可以玩国际象棋。