CSP-J 2026 题解

T1 旅游(travel)
题目要求依次判断两张车票是否满足四个条件:同一车厢、同一车厢的同一排、同一车厢的同一排且在过道同侧,以及座位相邻。
逐层判断四个条件
四个条件逐渐加强,后一项成立时,前面的条件也必须成立。因此,可以让每个判断包含上一项的结果。
车厢号固定为两位,直接比较两个字符串即可。座位号的前两个字符表示排号,最后一个字符表示座位字母。在车厢相同的前提下,再比较座位号的前两个字符,就能判断是否在同一排。
过道左侧的字母是 A、B、C,右侧是 D、F。由于输入保证座位合法,可以通过座位字母是否不大于 C 来区分两侧。
同一排内,相邻的座位只有以下三组:
A与B;B与C;D与F。
判断前先将两个字母按从小到大排列,就不必分别处理正反顺序。不能只判断字母编码之差是否为 :C 与 D 隔着过道,而 D 与 F 虽然编码不连续,却是相邻座位。
例如,两张票为 02 01C 和 02 01D。车厢、排号都相同,但两个座位分别位于过道两侧,因此四个判断的结果依次为 1100。
正确性与复杂度
前两个判断直接对应车厢号、排号是否相同;第三个判断进一步要求字母属于同一侧;第四个判断枚举了全部相邻座位组合。每一项都保留此前必须满足的条件,因此得到的四位结果与题目定义一致。
输入字符串长度固定,只需常数次比较,时间复杂度为 ,空间复杂度为 。
参考代码
#include<bits/stdc++.h>
using namespace std;
int main(){
string c1,s1,c2,s2;
cin>>c1>>s1>>c2>>s2;
bool x=c1==c2;
bool y=x&&s1[0]==s2[0]&&s1[1]==s2[1];
bool z=y&&((s1[2]<='C')==(s2[2]<='C'));
char a=s1[2],b=s2[2];
if(a>b)swap(a,b);
bool w=z&&((a=='A'&&b=='B')||(a=='B'&&b=='C')||(a=='D'&&b=='F'));
cout<<x<<y<<z<<w;
}
T2 回文串(string)
字符串由 段拼接而成,第 段包含 个字符 。每次可以修改一个位置的字符,求将整个字符串改成回文串的最少修改次数。
统计不同字符组成的对称位置对
设展开后的字符串长度为 。对于一对对称位置 和 :
- 字符相同,不需要修改;
- 字符不同,至少要修改其中一个字符,修改其中一个也已经足够。
不同的对称位置对之间没有公共位置,因此可以分别处理。答案就是字符不同的对称位置对数;若长度为奇数,正中间的字符不需要修改。
直接展开字符串,再从两端逐个比较,可以在 时间内求出答案。但本题中
无法按字符展开,需要直接在输入的分段上比较。
用双指针一次匹配整批字符
用 和 分别指向尚未处理的最左段、最右段,并让 、 保存这两段的剩余长度。
当 时,接下来的
对对称位置,左侧字符全是 ,右侧字符全是 。因此可以一次处理这 对:若 ,答案增加 ;否则答案不变。随后从两段剩余长度中各减去 ,至少有一段被耗尽。
例如,输入的三段是 、、,展开后为 aabbc:
| 左端剩余段 | 右端剩余段 | 本次处理的对数 | 新增修改次数 |
|---|---|---|---|
个 a | 个 c | ||
个 a | 个 b |
最后只剩中间的一个 b,不再产生修改,答案为 。
相邻输入段即使字符相同,也不需要预先合并。每次只依据当前两端的字符和剩余长度处理,分成几段不会影响比较结果。
代码为什么固定循环 次
代码没有使用常见的双指针循环条件,而是令 从 减到 。这里的 表示两个指针之间还保留了多少段记录,即
每次循环只移动一个指针:
- 若 ,左段耗尽,从右段扣除 ,再令 增加 ;
- 否则,右段耗尽,从左段扣除 ,再令 减少 。
因此,每轮都会使 减少 ,与 的变化一致。循环结束时 ,剩余内容只来自同一段,字符全部相同,不需要再修改。
当 时,代码进入第二种情况,只移动 ,并让 变为 。若此时仍有 ,下一轮会以 的贡献移走这个空段。因此,相等时也不必同时移动两个指针,固定循环次数仍然成立。
正确性与复杂度
在任意一轮开始时,两个指针之外的对称位置对均已处理,指针之间保存未处理字符串的分段表示。本轮处理的 对位置正是剩余字符串最外侧的 对,既不会遗漏,也不会与此前处理的位置重复。
字符不同的每一对恰好贡献一次必要修改,字符相同的每一对贡献为 。结束时剩余同字符段已经是回文串,所以累加值就是最少修改次数。
一共执行 轮,每轮只进行常数次操作,时间复杂度为 。保存各段需要 空间。
单段长度不超过 ,可以用 保存;答案最多为 ,可能达到 ,必须使用 。代码中单次增加的数不超过 ,累加时由答案变量承接即可。
参考代码
#include<bits/stdc++.h>
using namespace std;
int n;
int a[200005];
char c[200005];
int main(){
cin>>n;
for(int i=1;i<=n;++i){
cin>>a[i]>>c[i];
}
long long ans=0;
for(int i=1,j=n,z=n;z>1;z--){
if(a[i]<a[j]){
ans+=a[i]*(c[i]!=c[j]);
a[j]-=a[i];i++;
}else{
ans+=a[j]*(c[i]!=c[j]);
a[i]-=a[j];j--;
}
}
cout<<ans;
}
T3 按位与(and)
从 个非负整数中恰好选择 个,使它们的按位与最大。按位与的某一位为 ,当且仅当选出的每个数在这一位上都是 。
从高位到低位确定答案
直接枚举选出的 个数,方案数过多。也不能简单地选择最大的 个数:例如从 中选择两个,最大的两个数按位与为 ,而选择两个 可以得到 。
比较两个二进制数的大小,起决定作用的是从高到低第一个不同的位。在第 位取 会增加 ,而所有更低位加起来最多只有
因此,在更高位已经确定的前提下,只要当前位能够取 ,就一定应该取 。输入满足 ,所以从第 位到第 位依次处理。
保留满足已选二进制位的候选数
初始时,所有输入位置都是候选。用 表示第 个数仍是候选, 表示它已经被排除。候选数始终包含答案中此前确定为 的所有二进制位。
处理第 位时,统计候选中这一位为 的数有多少个,记为 :
- 若 ,可以从中恰好选出 个,使这一位的按位与为 。将答案的第 位置为 ,并排除这一位为 的候选。
- 若 ,任何 个候选中都至少有一个数的这一位为 ,所以答案这一位只能为 。候选集合保持不变,继续考虑更低位。
成功选定一位后,剩余候选仍然至少有 个。重复的数按不同输入位置分别计数,因为题目允许同时选择这些位置。
例如,样例中的四个数写成四位二进制为
要求选择 个数。高于第 位的部分都是 ,从第 位开始的过程如下:
| 当前位 | 候选中这一位为 的数量 | 处理后的候选 | 已确定的答案 |
|---|---|---|---|
| 第 位 | |||
| 第 位 | |||
| 第 位 | |||
| 第 位 |
最终答案为 。第 位和第 位无法取 时,不能继续排除这一位为 的数,否则会错误地丢弃合法选择。
正确性与复杂度
按位处理时,候选集合保存所有包含此前已选二进制位的数。若当前位有至少 个候选为 ,取其中任意 个就能同时保留此前的全部已选位和当前位;由于当前位的权值大于所有低位权值之和,选择这一位为 一定优于放弃它。
若不足 个候选为 ,则在保留此前已选位的前提下,当前位无法取 。之后候选集合只会缩小,这一位也不可能重新变得可行。处理完所有位后,剩余任意 个候选的按位与都恰好等于构造出的答案,且不存在更优的选择。
每一位最多扫描数组两次,共处理 位,时间复杂度为 ,空间复杂度为 。所有数以及答案都小于 ,使用 即可。
参考代码
#include<bits/stdc++.h>
using namespace std;
const int N=200005;
int n,m;
int a[200005];
bool vis[N];
int ans;
int main(){
cin>>n>>m;
for(int i=1;i<=n;++i)cin>>a[i];
for(int i=29;i>=0;i--){
int sum=0;
for(int j=1;j<=n;++j){
if(vis[j])continue;
if((a[j]&(1<<i)))sum++;
}
if(sum<m)continue;
ans|=(1<<i);
for(int j=1;j<=n;++j){
if(vis[j])continue;
if((a[j]&(1<<i)))continue;
vis[j]=1;
}
}
cout<<ans;
}
T4 纸牌游戏(card)
题目要求统计每种点数在多少局游戏的最终桌面上出现。数据范围达到 ,逐局模拟的 做法无法满足完整数据的要求,需要找出不同起点之间可以复用的信息。
先尝试从后往前扫描,用栈维护当前后缀的结果:遇到栈中已有的点数时,就弹出到对应位置,再放入新牌。但题目的收牌操作有明确的先后顺序,不能直接反过来执行。例如,序列 中,第三张牌 会收走此前的 ,随后再放入 ,最终留下 ;倒序套用同样的规则却会得到 。
再考虑从起点 转移到起点 。去掉最左侧的一张牌,可能改变后续多次收牌操作,直接维护桌面的变化并不方便。因此,可以先分析左端点本身会产生什么影响。
设起点 的点数为 。打出第一张牌后,桌面最左端始终有一张点数为 的牌。打出其他点数时,无论是放牌还是收牌,操作都发生在这张 的右侧,不会影响它。只有再次打出 时,才会收走最左侧的旧 及其右侧的全部牌,再放上新的 ,此时桌面上又只剩一张 。
假设右侧下一张点数为 的牌位于位置 。打出它后,桌面状态与从位置 开始、刚打出第一张牌时相同,此后要处理的牌也相同,因此从 和从 开始的最终结果一致。继续应用这个结论,就可以一直跳到点数 最后一次出现的位置,记为 。无论中间的牌如何排列,从 开始和从 开始的最终结果都相同。
到达位置 后,桌面上只有一张 。由于后面不会再出现 ,它一定会保留到游戏结束;其右侧的操作,则等同于从空桌面开始处理后缀 。因此,最终结果就是一张 ,接上从位置 开始的游戏结果。
据此,可以把处理过程拆成两种跳转:若当前位置还不是该点数最后一次出现的位置,就先跳到最后出现的位置;若已经到达最后出现的位置,就记录这个一定会保留的点数,再跳到下一张牌。定义
从任意游戏起点沿着 跳转,在每个点数最后出现的位置记录一次该点数,得到的就是这局游戏的最终桌面序列。位置 表示空后缀,也就是游戏结束。
把每次跳转看成一条从 指向 的边。每个位置 都有唯一的后继,而且始终满足 ,所以所有路径最终都会到达 。这些边构成一棵以 为根、边指向父节点的树。
点数 只会在位置 被记录。因此,一局游戏结束时留有点数 ,当且仅当这局游戏的跳转路径经过 。在树上,这又等价于游戏起点位于 的子树中。每个位置 都对应一局游戏,所以点数 的答案就是 的子树大小。
仍以序列 为例,各位置的后继分别为
图中圆圈内的数字表示原序列的位置编号,根节点 表示空后缀。每局游戏从对应的起点出发,沿父节点向根跳转。
点数 最后出现在位置 ,其子树包含位置 ,所以有 局游戏最终留有点数 。另外两种点数同理,答案依次为 。
子树大小也不需要通过遍历树来计算。令 初始为 ,表示从位置 开始的那局游戏;根节点 不对应游戏起点,初值为 。由于所有后继的下标都更大,按 的顺序,依次执行
处理位置 时,它的所有子节点都已经把贡献传来,此时 就是它的子树大小。若 ,即可令 。
预处理最后出现的位置、建立跳转和累加子树大小都只需线性扫描,最后输出 个答案,总时间复杂度为 ,空间复杂度为 。
参考代码
#include<bits/stdc++.h>
using namespace std;
const int N=500005;
int n,m;
int a[N];
int nxt[N],tr[N],fa[N];
int ans[N];
int main(){
cin>>n>>m;
for(int i=1;i<=n;++i)cin>>a[i];
for(int i=1;i<=n;++i){
fa[a[i]]=i;
}
for(int i=n;i;i--){
tr[i]=1;
if(fa[a[i]]!=i){
nxt[i]=fa[a[i]];
}else{
nxt[i]=i+1;
}
}
for(int i=1;i<=n;++i){
tr[nxt[i]]+=tr[i];
if(fa[a[i]]==i)ans[a[i]]=tr[i];
}
for(int i=1;i<=m;++i)cout<<ans[i]<<" ";
}
留言
可以匿名留言,无需注册或登录。昵称和邮箱均可不填,邮箱不会公开显示。
正在加载留言区…