2025CSP-J/S 第二轮游记

· · 生活·游记

坐标：GD-SZ

赛前

考点又是偏远地区深高高中园，不过今年没有去住酒店，从家里过去也还好。

比赛日

上午从家里出发，也是很早就到了考场。

J组

我们考场里一堆人电脑一直闪屏，备用机都不够用，万幸我的机子挺不错的。

比赛开始之后，题目下下来之后T1题都没看直接看样例秒了，打代码的同时顺便把后面几题的缺省源打了，大样例过了就没管了。

再看T2，先口胡了一个简单数学解法，写了之后所有样例都过了，但是不放心，又写了个纯模拟解法、数据生成器和对拍，拍了10万组没啥问题就关了。

T3。我第一眼看就觉得这题非常的CF。看到J组异或无非就按位考虑、异或前缀和或者结论，但是我推了一会没有结论，所以我就考虑按位或异或前缀和，而这题是区间，所以很显然用异或前缀和。我一开始只会 O(n^2) ，但是打出来之后，就发现这个暴力找和直接存桶找下标一样，所以就优化成 O(n) ，我考场用了map差点陨落，还好值域不是特别大。然后写了对拍和数据生成器，用暴力和优化后的拍了20万组，应该没啥问题。

T4。写完前三题还有2个半小时，先把最简单的40分暴力写了，直接状压就可以了。再写了数组全为1，那很显然就是 排列组合算。C(3,n)+C(4,n)+···+C(n,n)，考场上为了别出岔子，还求了逆元算，最后拼尽全力没有战胜T4。

考场预估分数: 100+100+100+64=364

赛后发现其他人全AK了，T4说是黄，呜呜呜。

午饭

中午家长们给我们带了饭到食堂吃，还不错，一位非常善良的大佬看了题之后给我讲了一下J组T4，其实是01背包，和洛谷J组模拟赛T3有点类似(周四老师还讲过，给我剁成臊子了)，只是这道是方案数，那道是可行性。

S组

还是J组那个机房，不过换了个同样好电脑的位置。

比赛开始之后一样先把缺省源啥的写了，再看T1。

T1：一开始想到了正解，结果实现写复杂了，写成分类讨论了，结果写了30分钟才发现直接存差值就可以，然后1h内把T1大样例过了，其实就是简单贪心，反悔学没学过不重要。

T4：是的没错，我先写了T4暴力，一开始以为特殊性质就是阶乘，结果不对，只会写暴力和m=n。。。20分钟写完回去看T3，发现不会，又去看T2。

T2：一看到题，k最大才10，有很大可能是状压，再看题，很显然就是求最小生成树，那就很简单了，状压k，然后直接每一个状态连边，再跑最小生成树找最小的就可以了。但是大样例一直死，一想，只需要原图先跑一次最小生成树，只保留最小生成树的边就可以了（其实这里救了我一命，我一开始极大值是INT_MAX），实现出来之后大样例过了，算了一下时间复杂度，是O(2^k*nk*log(nk))，结果代数进去的时候算错了，以为可以过就跳了，但实际上不行，赛后和老师说了才发现的，场上还以为这题是我包括模拟赛第一次场切S-T2，一出考场跟老师说老师激动坏了（不过能拿80也不错了吧哈哈）。。。

但实际上优化掉log不是很难，我会做。。。。

100pts -> 80pts

T3：看完T4看的时候不太会，写完T2再看T3还是不太会，于是不管了，直接写暴力去了，写完发现其实用哈希能优化掉一层循环，但是没时间了。。。遗憾退场。。。。

考场预估分数：100+100+15+15=230

出来之后立减20=210

赛后

拼尽全力无法战胜J组T4，如果今年J1了我也不会去圆AK梦了。

S组拼尽全力差点场切蓝（你别说，我一共做过的这一点蓝里也没几个是完全我自己写的）。

赛后出来还回忆了好久S-T2有没有开ll（赛时调试改了int），还好洛谷好心人多，都说大样例爆int了，那我应该开了。

希望能有初中生NOIP体验资格！！！