CSP2026游记

· · 生活·游记

CSP-J 初赛忘了多少分，CSP-S 免考了。

上午和下午都在石室文庙信息中心 301，居然和去年省选也是一个机房，真是太有幸了。

解密压缩包的密码挺好玩。先花十秒看了一遍题，发现 T1 好像是沙碧题，T3 是板子。T1 08:49:52 AC 了，发现不好对拍，就没管了。看 T2，一开始看错了，以为是 \sum a_i \le 10^9，感觉暴力冲得过去。写完一看，哦豁，样例三都过不了。然后发现读错题了，实际上是 \max a_i \le 10^9。然后老老实实弄两个指针过了。此时 09:21:11。我去，T3 也能放 CSP？这怕是在洛谷投 Unrated 公开赛都过不了审。显然从二进制高位往低位贪心，其实可以把已经因高位被筛掉的不满足要求的修改为 0，但因为昨天校内红红红红（真的）的信心赛我为了装糖四道题都用了 multiset，遂看到 J 组 T3 一眼认为要用 multiset 删东西。所以最后我写的是双 \log 的，第一个 \log 是 30，就是枚举每一位。此时 09:42:25。一开始看到 T4，O(n^2) 做法一眼，略加思考发现，假设当前牌的点数为 a_i，最后一张与当前点数相同的牌为 j，可以发现 i 与 j 最后剩下的牌是一样的。所以可以打标记。最后做到 O(m)。100+100+100+100=400，AK。此时11:40:33。自认为难度红橙橙绿。应该挂不了。

S 组 T1 一眼先排序，然后确定最大值，发现答案是单调的。于是考虑二分。写完发现一直不对，然后发现：

for(int i=1;i<=n;i++){
    cin>>a[i];
    sum[i]=sum[i-1]+a[i];
}
sort(a+1,a+n+1);

没绷住。此时 15:27:51，感觉很完蛋了。选择先开 T3，发现 A 性质好做，于 16:15:08 拿下 8 分。然后枚举起点、终点，当前在哪个店，从哪里转移，发现是 O(N^4) 的。怎么跟 DFS 同分啊。然后发现 v 是不用枚举的，然后就做到了 O(N^3)，32 分肯定有了。但是发现这个常数至少是 \frac{1}{8}，没准 N \le 5000 还有机会？此时 16:49:59，还是 100+0+[32,48]+0=[132,148]，很慌。想的是把 T4 暴力写了把时间都投给 T2。T4 15 分暴力显然，于 17:24:09 获得 15 分。还有一个小时多一点。（延时了 5 min）然后无效思考 30 min，决定打暴力。#1~#8,#12~15 应该没问题，就看 #9~#11。于 18:16:35 获得 100+[48,60]+[32,48]+15=[195,223]。检查后来到 18:27。在结局已定时静下心来，发现 T2 预处理地铁间的距离，询问时枚举起点和终点的地铁线即可。直接红温了。

S 是不是掉了。

不对，我 S 组 T2 优先队列好像写的是 pii。这不就坏了。