CSP-J/S 2026 游记

Day 0

打了一下洛谷模板赛，即使复习的都没有考。。。

晚上在宿舍里睡觉时被蚊子吵醒，激情并友好地夸赞了一下学校的生态环境

Day 1 · CSP-J

T1 travel · 高铁座位题（90 / 100）

没话说，输在没做过高铁

喜挂10pts

T2 string · 回文串（100 / 100）

第一反应双端队列

左右两端如果字符相同，那这两端的 \(\min(a_{\text{left}}, a_{\text{right}})\) 个直接配对消掉，不用改 如果字符不同，那要么把左边改成右边，要么把右边改成左边，取较少的那个数量加到答案里，然后把少的那堆整个吃掉

具体写法：用 \(\text{pair}<\text{long long}, \text{char}>\) 存每一段，扔进 \(deque\) 每次比较 \(front\) 和 \(back\)

• 字符相同：\(\text{ans} \mathrel{+}= 0\)，两端各减 \(\min(\text{front.len}, \text{back.len})\)，空的那端 \(pop\)
• 字符不同：把数量少的那堆整个改成另一边的字符，\(\text{ans} \mathrel{+}= \min(\text{front.len}, \text{back.len})\)，数量少的那端 \(pop\)，多的那端字符变成对面的字符
• 直到 deque 里只剩一段（奇数长度的中间），不管它

喜提100pts 今天唯一一道满分，已泪目T_T

T3 and · 按位与最大值（0 / 100）

题目：选恰好 \(m\) 个数，让它们的按位与最大

由于去年异或和，死磕DP，结果正解是贪心

喜提0pts

赛后正解：从高位到低位逐位贪心维护当前答案 \(\text{ans}\)，每次假设第 \(k\) 位可以加进 \(\text{ans}\)，然后数一下有多少个数满足 \((a_i \mathbin{\&} (\text{ans} \mathbin{|} (1\ll k))) = (\text{ans} \mathbin{|} (1\ll k))\)，如果 \(\ge m\) 就真的加进去 \(O(30n)\)，一分钟写完

T4 card · 纸牌游戏（48 / 100）

题目大意：\(n\) 局游戏，第 \(i\) 局从第 \(i\) 张牌开始打，桌面维护一个栈——遇到重复的牌就把那张牌及其后面的全部弹掉再压进来 问每个点数最终在多少局里留下来了

那纯模拟

喜提48pts

48 分什么概念？就是 CCF 的水数据让一个 \(O(n^2)\) 的暴力过了快一半的测试点

CCF 数据含水量鉴定：★★★★☆ 一个纯暴力模拟拿了 48 分，建议 CCF 把出题组叫过来看看自己出的什么数据

but，感谢CCF，膜拜Orz

J 组总分

---

Day 1 · CSP-S

T1 crystal · 能量水晶（15 / 100）

题面：\(n\) 颗水晶，能量值 \(a_i\)，每次操作可以让任意一颗 +1，至多 \(m\) 次操作，最后要让尽可能多的水晶能量值相同 问最多能凑几颗

看到 至多 \(m\) 次操作——

脑子抽疯环节

反复读题面：他可以进行至多 \(m\) 次操作-进行至多 \(m\) 次-进行至多 \(m\) 次必须-进行恰好 \(m\) 次

也就是说，我必须把 \(m\) 次操作全部用完，哪怕补过了头，嗯这很对

然后写了个雷霆大棍木出来，调了2h没调出个所以然来，直接放弃。。。老老实实写暴力拿分保NOIP去了

这样的话，目标值就不是 \(a[r]\) 了，而是某个 \(\ge a[r]\) 的值 而且为了让窗口里所有水晶都一样，这个值还必须满足 \((\text{sum} + m) \bmod \text{len} = 0\)，因为 \(m\) 次操作全花完之后总和变成 \(\text{sum}+m\)，要能被 \(\text{len}\) 整除

然后我就写了一个 \(O(n^3)\) 的暴力：枚举所有长度 \(\text{len}\)，枚举所有起点 \(i\)，算区间 \(\text{sum}\) 和 \(\max\)，然后判断 \((\text{sum} + m) \bmod \text{len} = 0\) 且 \((\text{sum} + m) / \text{len} \ge \max\)

for(int len=2;len<=n;len++){for(int i=1;i+len-1<=n;i++){int j=i+len-1;int sum=0;int maxx=*max_element(a+i+1,a+j+1);for(int k=i;k<=j;k++) sum+=a[k];if((sum+m)%len==0&&(sum+m)/len>=maxx){ans=len;}}
}

写完我还觉得挺对 但是样例 1 \(1, 2, 4, 8, 9, \, m=5\)：

• 窗口 \([1,2,4]\)：\(\text{sum}=7\), \(\text{len}=3\), \((7+5)/3=4\), \(\max=4\) → \(4 \ge 4\)，成立，\(\text{ans}=3\) 样例输出 3，对的
• 窗口 \([1,2]\)：\(\text{sum}=3\), \(\text{len}=2\), \((3+5)/2=4\), \(\max=2\) → 成立，\(\text{ans}=2\)

样例 2 \(-3, -1, 2, 2, 7, \, m=8\)：

• 窗口 \([-3,-1,2,2]\)：\(\text{sum}=0\), \(\text{len}=4\), \((0+8)/4=2\), \(\max=2\) → 成立，\(\text{ans}=4\) 样例输出 4，对的

样例都过了

然后我在这个题上耗了整整一坤时

T2 subway · 地铁（0 / 100）

已慌

快速扫题：\(m\) 个地铁站，\(n\) 条线路，每个站从地铁口到站厅要 \(w_v\)，每条线路在每个站从站厅到站台要 \(t_{i,j}\)，换乘要先回站厅 \(q\) 个询问，求 \(x\) 到 \(y\) 的最小步行时间

——分层图最短路啊！

把每个地铁站拆成 站厅层 和 线路站台层：

• 地铁口 → 站厅：边权 \(w_v\)
• 站厅 → 线路 \(i\) 站台：边权 \(t_{i,j}\)
• 同一条线路相邻站之间：边权 \(0\)（坐地铁不花步行时间）
• 线路 \(i\) 站台 → 站厅：边权 \(t_{i,j}\)（往返相同）

然后对每个询问跑一遍 Dijkstra？\(q\) 是 \(10^5\)，每次跑一遍图（\(5 \times 10^5\) 个点）铁定 T

这题应该是个多源最短路 / BFS 预处理 / 某种 trick 我脑子已经转不动了

从读题到建图太折磨人了，心态直接炸，我chovy不写了

喜提CE

T3 migrate · 双径岛屿对（0 / 100）

岛屿排成一条线，每次能飞距离 \(\le d\)，问有多少对 \((u,v)\) 最短路恰好有两条

我当时看了一眼：\(n \le 2 \times 10^6\)，多组数据 这题绝对是个 \(O(n)\) 或者 \(O(n \log n)\) 的结论题

但是已经没时间了 我写了一个 BFS 暴力：枚举每对 \((i,j)\)，跑一遍 BFS 看最短路长度是不是恰好有两条

问题是 \(\text{cnt}\) 的统计逻辑就是错的——在 BFS 里遇到 \(\text{dep}[v] > \text{dep}[u]+1\) 才更新，但是统计最短路径数的逻辑根本不对，\(\text{minn}\) 和 \(\text{cnt}\) 的配合也一塌糊涂 而且我只枚举了 \(j \ge i+3\)，理由是 距离小于等于 3 的不可能有两条最短路——这又是我自己瞎想的结论，嗯对。。。

喜提0pts

T4 hub · 研发基地（0 / 100）

树上面选恰好 \(k\) 个点，形成不超过两个连通块，让最远点到最近选中点的距离最小

我看完题面，脑子里只有一个想法

此乃何物，不写了

喜提0pts

S 组总分

Day \(\infty\) · 出分与复盘

成绩

• CSP-J：238（travel 90 + string 100 + and 0 + card 48）
• CSP-S：15（crystal 15）

J 大概二等边缘？S 这个分数……很难评

复盘

1. travel

输在没坐过高铁

**2. and **

这题真的是我整场比赛最意难平的 正解就是 30 行的逐位贪心，我因为 觉得 J 组 T3 不可能考裸贪心 而死磕 DP，最后连暴力都写挂了。。。

3. crystal

把 至多 \(m\) 次 理解成了 必须用完 \(m\) 次。。。

**4. subway / migrate / hub **

我在 T1 上花了 2.5h，剩下三题只有 1.5h，而且心态已经崩了。。。

关于 CCF 超水数据

card 那个 48 分真的是 CCF 赏饭吃 一个 \(O(n^2)\) 的纯模拟，在 \(n \le 5 \times 10^5\) 的题上拿了接近一半的分 如果 CCF 数据稍微强一点，卡掉那些 \(n = 2 \times 10^5\) 的测试点，我连 48 都没有

crystal 的 15 分也是——我的错误代码在 刚好 \(m\) 次操作能整除 的小数据上碰巧是对的，但凡出一组 \(m\) 用不完的数据我就爆0了

某种意义上，我这个分数是 CCF 用超水数据喂出来的

拜谢CCF，感谢CCF，Orz