2025 CSP-J 挂分日记

· · 生活·游记

坐标：CQ 考试地点：重庆一中

上午 J 组的时间是 8:30-12:00，提前一个小时赶到了考场（bushi 貌似只有 10 min 的车程耶……），考前小睡了一会。

考试准备：

正文

T1 拼数 / number

考察字符串的基础运用，简单 2 min 打完。

T2 座位 / seat

思路是排序后用数组模拟分配过程，分到了就输出行列，没什么好说的。

T3 异或和 / xor

正解是前缀异或和 + 区间 DP，中间有个优化用异或的性质将循环的 O(n^2) 压成 O(n) ，可以拿全分。

枚举右端点 r，如果存在一个 l(lst \le l<rst) 使得异或和满足条件，那么就存在区间 (l,r] 符合条件。

当时没有想到优化，就写了个 O(n^2) 的暴力，过了前 4 个样例，实测拿到了 50 的低分。

T4 多边形 / polygon

降黄了，正解是背包DP。设 dp_{i,j} 表示选前 i 个数的和为 j 的方案数，则 dp 很容易用背包 O(nV) 地递推出来。

考场上写了个 DFS，骗得 40 的低分（都是因为我太蒻了）

一共加起来接近 300 分，说实话比我的预期还低了 20 分。

希望 CCF 少爷机能给力一点吧。