CSP-J 2026 四题题解
CSP-J 2026 这四道题，我按“题目在问什么、关键观察、复杂度、容易出错的地方、参考代码”的顺序整理成这篇复盘，方便同学和家长一起看，也方便赛后有需要的同学对照代码重做。
题目链接：https://qucode.cn/contest/6ae56f744f19f1fb7b47e441 平台账号可以自己注册，注册后就能在平台上提交代码。需要提醒一句：平台上的测试数据不是官方数据，只供练习参考。
建议先读题意和关键结论，再对照代码理解实现。代码可以直接提交，但每道题那句核心结论，尽量能用自己的话复述一遍。
四道题先有个整体印象：
| 题号 | 题目 | 核心方法 | 复杂度 | 容易错的地方 |
|---|---|---|---|---|
| 3272 | 旅游 / travel | 模拟，判断条件层层包含 | O(1) | 不同车厢时后三问必须为 0；过道两侧不算相邻 |
| 3273 | 回文串 / string | 游程编码上双指针 | O(n) | 长度和答案都要 long long；左右指针进同一段就停 |
| 3274 | 按位与 / and | 从高位到低位贪心 + 计数 | O(30n) | 不能排序取前 $m$ 大 |
| 3275 | 纸牌游戏 / card | 栈结构推出链式结论，再计数递推 | O(n+m) | 逐局模拟是 O(n²)；递推方向别写反 |
3272 旅游 / travel
这题给两张二等座车票。车厢号 $c$ 在 01 到 17 之间，题目保证不是一等座的 01、16。座位号 $s$ 是两位排号加一个字母，字母只会是 A/B/C/D/F。每排从左到右是：
A B C | D F
C 和 D 中间是过道。然后依次回答四个问题，输出 4 位 01 串：是否同车厢、是否同车厢同排、是否同车厢同排同侧、是否相邻。
这里的关键是四问层层包含。第 2 问不是单独问排号是否相同，而是问“同车厢且同排”；第 3 问在第 2 问基础上再加同侧；第 4 问再加相邻。样例 5 是 02 01A 03 01A → 0000，两张票排号都是 01，但车厢不同，所以后三问全是 0。所以判断要一环扣一环地写：
if(c1==c2) a1=1;
if(a1==1 && s1.substr(0,2)==s2.substr(0,2)) a2=1;
只写“排号相同”的话，这一组会错答成 0110。
相邻的判断是：同车厢、同排、同侧，并且在该侧序列里的下标相差 1。左序列 A,B,C 下标 0、1、2，右序列 D,F 下标 0、1。所以 A-B、B-C、D-F 相邻，C-D 隔着过道，不算相邻。
复杂度 O(1)。
#include <bits/stdc++.h>
using namespace std;
string c1,s1,c2,s2;
int sideOf(char c) {
if(c=='A'||c=='B'||c=='C') return 0;
return 1;
}
int posOf(char c) {
if(c=='A') return 0;
if(c=='B') return 1;
if(c=='C') return 2;
if(c=='D') return 0;
return 1;
}
int main() {
cin >> c1 >> s1 >> c2 >> s2;
int a1=0,a2=0,a3=0,a4=0;
if(c1==c2) a1=1;
if(a1==1 && s1.substr(0,2)==s2.substr(0,2)) a2=1;
if(a2==1 && sideOf(s1[2])==sideOf(s2[2])) a3=1;
if(a3==1 && abs(posOf(s1[2])-posOf(s2[2]))==1) a4=1;
cout << a1 << a2 << a3 << a4 << endl;
return 0;
}
3273 回文串 / string
字符串不直接给，而是游程编码：一共 $n$ 段，第 $i$ 段是 $a_i$ 个小写字母 $c_i$，拼起来是 $S$。长度 $L=\sum a_i$，其中 $n\le 2\times10^{5}$，$a_i\le 10^{9}$，所以 $L$ 最大能到 $2\times10^{14}$ 左右。不能展开字符串。
每次可以把任意位置改成任意小写字母，问最少改多少个位置能让 $S$ 变成回文串。
回文要求每一对对称位置 $(i,\ L+1-i)$ 字符相同，不同对称位置对之间互不影响。所以答案就是 $1\le i\le L/2$（下取整）中满足 $S[i]\ne S[L+1-i]$ 的位置对数。问题变成：不展开怎么数。
用双指针 $l$、$r$ 按段从两端往中间走，s[i].a 记第 $i$ 段还剩多少字符，$sum$ 是总长的一半（也就是还要配对的组数），$cnt$ 是已经处理掉的组数。每一轮取：
int mi=min(s[l].a,s[r].a);
if(cnt+mi>sum) mi=sum-cnt;
如果 $l$、$r$ 两段的字符不同，这 $mi$ 组配对全都要改，答案加 $mi$。然后把两段的剩余字符数都减去 $mi$，$cnt$ 加上 $mi$。哪一段用完了，就把那个指针往中间挪一格。$cnt$ 追平 $sum$，或者 $l$、$r$ 走到一起，就停下来，中间剩下的字符贡献 0。
复杂度 O(n)，跟 $L$ 无关。
易错的地方：$\sum a_i$ 能到 $2\times10^{14}$，必须开 long long（下面代码用 #define int long long 省事）；答案也能到 $5\times10^{13}$ 这个级别，int 装不下；$r$ 是往中间走（r--），写方向别手滑；$mi$ 还要被剩下待配对的组数截断，否则会多算。
#include <bits/stdc++.h>
using namespace std;
#define int long long
struct node {
int a;
char c;
} s[200005];
int n;
signed main() {
cin >> n;
int sum=0;
for(int i=1; i<=n; i++) {
cin >> s[i].a >> s[i].c;
sum+=s[i].a;
}
sum/=2;
int l=1,r=n;
int cnt=0;
int ans=0;
while(cnt<sum && l<r) {
int mi=min(s[l].a,s[r].a);
if(cnt+mi>sum) mi=sum-cnt;
if(s[l].c!=s[r].c) ans+=mi;
s[l].a-=mi;
s[r].a-=mi;
cnt+=mi;
if(s[l].a==0) l++;
if(s[r].a==0) r--;
}
cout << ans << endl;
return 0;
}
3274 按位与 / and
给 $n$ 个非负整数，$a_i<2^{30}$，恰好选出 $m$ 个，使它们的按位与最大，输出这个最大值。注意是恰好 $m$ 个。
按位与最大，先从高位到低位贪心。设已经确定的掩码是 $ans$，现在看第 $b$ 位。令 cand = ans | (1 << b)，统计数组里有多少个数包含 $cand$ 的每一个 1 位，也就是满足 (a_i & cand) == cand 的个数 $cnt$。如果 $cnt\ge m$，说明能挑出 $m$ 个数都含这些位，它们的按位与一定也含这些位，第 $b$ 位可以保住，$ans=cand$；否则这一位只能放弃。
这样贪心的原因是高位权重大，高位能保住比“高位丢掉、低位全保”更优。另外，“至少有 $m$ 个数同时含 $cand$ 的所有 1 位”既是必要条件也是充分条件：同一位置 1，要求每个数该位都是 1；反过来，这 $m$ 个数按位与一定包含 $cand$。
复杂度 O(30n)，大约 $6\times10^{6}$ 次运算。
易错点：不能排序取前 $m$ 大，样例 2 给 31 3 1 15 7，选 31,15,7 的按位与是 $7$，这才是答案；$m=1$ 时答案就是最大值；$m=n$ 时答案就是全部按位与；$a_i$ 最大不到 $2^{30}$，循环从 29 到 0 就行。
#include <bits/stdc++.h>
using namespace std;
int a[200005];
int n,m;
int main() {
cin >> n >> m;
for(int i=1; i<=n; i++) {
cin >> a[i];
}
int ans=0;
for(int b=29; b>=0; b--) {
int cand=ans|(1<<b);
int cnt=0;
for(int i=1; i<=n; i++) {
if((a[i]&cand)==cand) cnt++;
if(cnt>=m) break;
}
if(cnt>=m) ans=cand;
}
cout << ans << endl;
return 0;
}
3275 纸牌游戏 / card
有 $n$ 张牌，点数 $a_1,a_2,\ldots,a_n$，点数范围 $1\sim m$，每种点数至少出现一次。第 $i$ 局跳过前 $i-1$ 张，依次打出 $a_i,a_{i+1},\ldots,a_n$。打出点数为 $k$ 的牌时，桌上没有 $k$ 就压到最右；桌上已经有 $k$，就收走桌上所有点数为 $k$ 的牌及其右侧全部牌，再把新 $k$ 压到最右。对每个 $1\le i\le m$，求 $n$ 局中有多少局结束时桌上还留着点数为 $i$ 的牌。
逐局模拟是 O(n²)，$n$ 到 $5\times10^{5}$，只能拿小分。桌面其实一直是一条栈：同一时刻每种点数至多一张，打出 $k$ 时把 $k$ 及它右边全部弹掉，再压入 $k$。所以栈里的元素顺序就是各自“最后出现位置”递增的顺序。
记 $L[v]$ 是点数 $v$ 在整个数组里最后一次出现的位置，$G(n+1)$ 为空，$+$ 表示栈底到栈顶的拼接。第 $s$ 局结束时的桌面满足：
G(s) = [a_s] + G(L[a_s] + 1)
原因是：$a_s$ 打出去之后进栈底，之后只有再次打出 $a_s$ 才会波及它，那一次会把栈清空只留 $a_s$。取最后一次再次打出的位置 $t=L[a_s]$，若不存在则 $t=s$，此后 $a_s$ 永不消失，栈底固定是 $a_s$，它上面的内容跟从 $t+1$ 位置重新独立打一局完全一样。
再记 $nxt[p]=L[a_p]+1$，显然 $nxt[p]>p$。于是每局桌面就是一条链：
s → nxt[s] → nxt[nxt[s]] → … → n+1（结束）
下标严格递增，$n+1$ 表示结束。
设 $cnt[p]$ 表示有多少个起点 $s$ 的链会经过位置 $p$，则：
cnt[p] = 1 + Σ cnt[q] 对所有满足 nxt[q] = p 的 q 求和
这个 $1$ 是起点 $s=p$ 自己这一票。因为 $nxt[q]>q$，按 $p$ 从 1 到 $n$ 顺序推就行：轮到 $p$ 时它的 $cnt$ 已经累加完整了，先加上自己这一票，再把整份贡献推给 $cnt[nxt[p]]$。最后：
ans[v] = Σ cnt[p] 对所有满足 a_p = v 的 p 求和
复杂度 O(n+m)。最大点 $n=5\times10^{5}$、$m=3\times10^{5}$，实测大约 0.33s。
易错点：逐个起点模拟是 O(n²)；$ans[v]\le n$，int 够；$cnt$ 的总量也不会超过 $n$，但写成 long long 更稳；$m=1$ 时只有一种点数，每局结束桌面始终有该点数，答案是 $n$。
#include <bits/stdc++.h>
using namespace std;
int a[500005];
int last[300005];
int nxt[500005];
long long cnt[500005];
long long ans[300005];
int n,m;
int main() {
cin >> n >> m;
for(int i=1; i<=n; i++) {
cin >> a[i];
}
for(int i=1; i<=n; i++) {
last[a[i]]=i;
}
for(int i=1; i<=n; i++) {
nxt[i]=last[a[i]]+1;
}
for(int i=1; i<=n; i++) {
cnt[i]+=1;
cnt[nxt[i]]+=cnt[i];
}
for(int i=1; i<=n; i++) {
ans[a[i]]+=cnt[i];
}
for(int v=1; v<=m; v++) {
if(v>1) cout << ' ';
cout << ans[v];
}
cout << endl;
return 0;
}
拿 $n=4,\ m=3,\ a=[1,2,1,3]$ 走一遍。最后出现位置是 $L:1\to3,\ 2\to2,\ 3\to4$，所以 $nxt[1..4]=[4,3,4,5]$。链是 $1\to4$、$2\to3\to4$、$3\to4$、$4$，于是 $cnt[1]=1,\ cnt[2]=1,\ cnt[3]=2,\ cnt[4]=4$，$ans[1]=cnt[1]+cnt[3]=3$，$ans[2]=cnt[2]=1$，$ans[3]=cnt[4]=4$，输出 3 1 4。
travel 主要考读题，string 考不展开时的双指针，and 考按位贪心，card 考从栈里看出链式结构再计数。代码可以照着敲，但每道题那句核心结论尽量能自己复述一遍。写完拿小样例手推一次，比盯着屏幕找错快。
评论 0