CSP-J 2026 题解

T1 旅游(travel)

题目要求依次判断两张车票是否满足四个条件:同一车厢、同一车厢的同一排、同一车厢的同一排且在过道同侧,以及座位相邻。

逐层判断四个条件

四个条件逐渐加强,后一项成立时,前面的条件也必须成立。因此,可以让每个判断包含上一项的结果。

车厢号固定为两位,直接比较两个字符串即可。座位号的前两个字符表示排号,最后一个字符表示座位字母。在车厢相同的前提下,再比较座位号的前两个字符,就能判断是否在同一排。

过道左侧的字母是 A、B、C,右侧是 D、F。由于输入保证座位合法,可以通过座位字母是否不大于 C 来区分两侧。

同一排内,相邻的座位只有以下三组:

  • A 与 B;
  • B 与 C;
  • D 与 F。

判断前先将两个字母按从小到大排列,就不必分别处理正反顺序。不能只判断字母编码之差是否为 11:C 与 D 隔着过道,而 D 与 F 虽然编码不连续,却是相邻座位。

例如,两张票为 02 01C 和 02 01D。车厢、排号都相同,但两个座位分别位于过道两侧,因此四个判断的结果依次为 1100。

正确性与复杂度

前两个判断直接对应车厢号、排号是否相同;第三个判断进一步要求字母属于同一侧;第四个判断枚举了全部相邻座位组合。每一项都保留此前必须满足的条件,因此得到的四位结果与题目定义一致。

输入字符串长度固定,只需常数次比较,时间复杂度为 O(1)O(1),空间复杂度为 O(1)O(1)。

参考代码

#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)

字符串由 nn 段拼接而成,第 ii 段包含 aia_i 个字符 cic_i。每次可以修改一个位置的字符,求将整个字符串改成回文串的最少修改次数。

统计不同字符组成的对称位置对

设展开后的字符串长度为 LL。对于一对对称位置 kk 和 L+1−kL+1-k:

  • 字符相同,不需要修改;
  • 字符不同,至少要修改其中一个字符,修改其中一个也已经足够。

不同的对称位置对之间没有公共位置,因此可以分别处理。答案就是字符不同的对称位置对数;若长度为奇数,正中间的字符不需要修改。

直接展开字符串,再从两端逐个比较,可以在 O(L)O(L) 时间内求出答案。但本题中

L=∑i=1nai≤2×1014,L=\sum_{i=1}^{n}a_i\le 2\times 10^{14},

无法按字符展开,需要直接在输入的分段上比较。

用双指针一次匹配整批字符

用 ii 和 jj 分别指向尚未处理的最左段、最右段,并让 aia_i、aja_j 保存这两段的剩余长度。

当 i<ji<j 时,接下来的

t=min⁡(ai,aj)t=\min(a_i,a_j)

对对称位置,左侧字符全是 cic_i,右侧字符全是 cjc_j。因此可以一次处理这 tt 对:若 ci≠cjc_i\ne c_j,答案增加 tt;否则答案不变。随后从两段剩余长度中各减去 tt,至少有一段被耗尽。

例如,输入的三段是 (2,a)(2,\mathtt{a})、(2,b)(2,\mathtt{b})、(1,c)(1,\mathtt{c}),展开后为 aabbc:

左端剩余段右端剩余段本次处理的对数新增修改次数
22 个 a11 个 c1111
11 个 a22 个 b1111

最后只剩中间的一个 b,不再产生修改,答案为 22。

相邻输入段即使字符相同,也不需要预先合并。每次只依据当前两端的字符和剩余长度处理,分成几段不会影响比较结果。

代码为什么固定循环 n−1n-1 次

代码没有使用常见的双指针循环条件,而是令 zz 从 nn 减到 22。这里的 zz 表示两个指针之间还保留了多少段记录,即

z=j−i+1.z=j-i+1.

每次循环只移动一个指针:

  • 若 ai<aja_i<a_j,左段耗尽,从右段扣除 aia_i,再令 ii 增加 11;
  • 否则,右段耗尽,从左段扣除 aja_j,再令 jj 减少 11。

因此,每轮都会使 j−i+1j-i+1 减少 11,与 zz 的变化一致。循环结束时 i=ji=j,剩余内容只来自同一段,字符全部相同,不需要再修改。

当 ai=aja_i=a_j 时,代码进入第二种情况,只移动 jj,并让 aia_i 变为 00。若此时仍有 i<ji<j,下一轮会以 00 的贡献移走这个空段。因此,相等时也不必同时移动两个指针,固定循环次数仍然成立。

正确性与复杂度

在任意一轮开始时,两个指针之外的对称位置对均已处理,指针之间保存未处理字符串的分段表示。本轮处理的 tt 对位置正是剩余字符串最外侧的 tt 对,既不会遗漏,也不会与此前处理的位置重复。

字符不同的每一对恰好贡献一次必要修改,字符相同的每一对贡献为 00。结束时剩余同字符段已经是回文串,所以累加值就是最少修改次数。

一共执行 n−1n-1 轮,每轮只进行常数次操作,时间复杂度为 O(n)O(n)。保存各段需要 O(n)O(n) 空间。

单段长度不超过 10910^9,可以用 int\texttt{int} 保存;答案最多为 ⌊L/2⌋\lfloor L/2\rfloor,可能达到 101410^{14},必须使用 long long\texttt{long long}。代码中单次增加的数不超过 10910^9,累加时由答案变量承接即可。

参考代码

#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)

从 nn 个非负整数中恰好选择 mm 个,使它们的按位与最大。按位与的某一位为 11,当且仅当选出的每个数在这一位上都是 11。

从高位到低位确定答案

直接枚举选出的 mm 个数,方案数过多。也不能简单地选择最大的 mm 个数:例如从 8,7,78,7,7 中选择两个,最大的两个数按位与为 00,而选择两个 77 可以得到 77。

比较两个二进制数的大小,起决定作用的是从高到低第一个不同的位。在第 kk 位取 11 会增加 2k2^k,而所有更低位加起来最多只有

∑t=0k−12t=2k−1.\sum_{t=0}^{k-1}2^t=2^k-1.

因此,在更高位已经确定的前提下,只要当前位能够取 11,就一定应该取 11。输入满足 ai<230a_i<2^{30},所以从第 2929 位到第 00 位依次处理。

保留满足已选二进制位的候选数

初始时,所有输入位置都是候选。用 visj=0vis_j=0 表示第 jj 个数仍是候选,visj=1vis_j=1 表示它已经被排除。候选数始终包含答案中此前确定为 11 的所有二进制位。

处理第 kk 位时,统计候选中这一位为 11 的数有多少个,记为 sumsum:

  • 若 sum≥msum\ge m,可以从中恰好选出 mm 个,使这一位的按位与为 11。将答案的第 kk 位置为 11,并排除这一位为 00 的候选。
  • 若 sum<msum<m,任何 mm 个候选中都至少有一个数的这一位为 00,所以答案这一位只能为 00。候选集合保持不变,继续考虑更低位。

成功选定一位后,剩余候选仍然至少有 mm 个。重复的数按不同输入位置分别计数,因为题目允许同时选择这些位置。

例如,样例中的四个数写成四位二进制为

3=00112,15=11112,12=11002,12=11002,3=0011_2,\quad 15=1111_2,\quad 12=1100_2,\quad 12=1100_2,

要求选择 22 个数。高于第 33 位的部分都是 00,从第 33 位开始的过程如下:

当前位候选中这一位为 11 的数量处理后的候选已确定的答案
第 33 位3315,12,1215,12,12100021000_2
第 22 位3315,12,1215,12,12110021100_2
第 11 位1115,12,1215,12,12110021100_2
第 00 位1115,12,1215,12,12110021100_2

最终答案为 11002=121100_2=12。第 11 位和第 00 位无法取 11 时,不能继续排除这一位为 00 的数,否则会错误地丢弃合法选择。

正确性与复杂度

按位处理时,候选集合保存所有包含此前已选二进制位的数。若当前位有至少 mm 个候选为 11,取其中任意 mm 个就能同时保留此前的全部已选位和当前位;由于当前位的权值大于所有低位权值之和,选择这一位为 11 一定优于放弃它。

若不足 mm 个候选为 11,则在保留此前已选位的前提下,当前位无法取 11。之后候选集合只会缩小,这一位也不可能重新变得可行。处理完所有位后,剩余任意 mm 个候选的按位与都恰好等于构造出的答案,且不存在更优的选择。

每一位最多扫描数组两次,共处理 3030 位,时间复杂度为 O(30n)O(30n),空间复杂度为 O(n)O(n)。所有数以及答案都小于 2302^{30},使用 int\texttt{int} 即可。

参考代码

#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)

题目要求统计每种点数在多少局游戏的最终桌面上出现。数据范围达到 n≤5×105n\le5\times10^5,逐局模拟的 O(n2)O(n^2) 做法无法满足完整数据的要求,需要找出不同起点之间可以复用的信息。

先尝试从后往前扫描,用栈维护当前后缀的结果:遇到栈中已有的点数时,就弹出到对应位置,再放入新牌。但题目的收牌操作有明确的先后顺序,不能直接反过来执行。例如,序列 1,3,1,2,31,3,1,2,3 中,第三张牌 11 会收走此前的 1,31,3,随后再放入 2,32,3,最终留下 1,2,31,2,3;倒序套用同样的规则却会得到 1,31,3。

再考虑从起点 ii 转移到起点 i+1i+1。去掉最左侧的一张牌,可能改变后续多次收牌操作,直接维护桌面的变化并不方便。因此,可以先分析左端点本身会产生什么影响。

设起点 ii 的点数为 x=aix=a_i。打出第一张牌后,桌面最左端始终有一张点数为 xx 的牌。打出其他点数时,无论是放牌还是收牌,操作都发生在这张 xx 的右侧,不会影响它。只有再次打出 xx 时,才会收走最左侧的旧 xx 及其右侧的全部牌,再放上新的 xx,此时桌面上又只剩一张 xx。

假设右侧下一张点数为 xx 的牌位于位置 jj。打出它后,桌面状态与从位置 jj 开始、刚打出第一张牌时相同,此后要处理的牌也相同,因此从 ii 和从 jj 开始的最终结果一致。继续应用这个结论,就可以一直跳到点数 xx 最后一次出现的位置,记为 faxfa_x。无论中间的牌如何排列,从 ii 开始和从 faxfa_x 开始的最终结果都相同。

到达位置 faxfa_x 后,桌面上只有一张 xx。由于后面不会再出现 xx,它一定会保留到游戏结束;其右侧的操作,则等同于从空桌面开始处理后缀 afax+1,…,ana_{fa_x+1},\ldots,a_n。因此,最终结果就是一张 xx,接上从位置 fax+1fa_x+1 开始的游戏结果。

据此,可以把处理过程拆成两种跳转:若当前位置还不是该点数最后一次出现的位置,就先跳到最后出现的位置;若已经到达最后出现的位置,就记录这个一定会保留的点数,再跳到下一张牌。定义

nxti={faai,i<faai,i+1,i=faai.nxt_i= \begin{cases} fa_{a_i}, & i<fa_{a_i},\\ i+1, & i=fa_{a_i}. \end{cases}

从任意游戏起点沿着 nxtnxt 跳转,在每个点数最后出现的位置记录一次该点数,得到的就是这局游戏的最终桌面序列。位置 n+1n+1 表示空后缀,也就是游戏结束。

把每次跳转看成一条从 ii 指向 nxtinxt_i 的边。每个位置 1≤i≤n1\le i\le n 都有唯一的后继,而且始终满足 nxti>inxt_i>i,所以所有路径最终都会到达 n+1n+1。这些边构成一棵以 n+1n+1 为根、边指向父节点的树。

点数 xx 只会在位置 faxfa_x 被记录。因此,一局游戏结束时留有点数 xx,当且仅当这局游戏的跳转路径经过 faxfa_x。在树上,这又等价于游戏起点位于 faxfa_x 的子树中。每个位置 1,2,…,n1,2,\ldots,n 都对应一局游戏,所以点数 xx 的答案就是 faxfa_x 的子树大小。

仍以序列 1,3,1,2,31,3,1,2,3 为例,各位置的后继分别为

1→3,2→5,3→4,4→5,5→6.1\to3,\qquad2\to5,\qquad3\to4,\qquad4\to5,\qquad5\to6.

序列 1、3、1、2、3 对应的跳转树

图中圆圈内的数字表示原序列的位置编号,根节点 6=n+16=n+1 表示空后缀。每局游戏从对应的起点出发,沿父节点向根跳转。

点数 11 最后出现在位置 33,其子树包含位置 1,31,3,所以有 22 局游戏最终留有点数 11。另外两种点数同理,答案依次为 2,3,52,3,5。

子树大小也不需要通过遍历树来计算。令 tritr_i 初始为 11,表示从位置 ii 开始的那局游戏;根节点 n+1n+1 不对应游戏起点,初值为 00。由于所有后继的下标都更大,按 i=1,2,…,ni=1,2,\ldots,n 的顺序,依次执行

trnxti←trnxti+tri.tr_{nxt_i}\gets tr_{nxt_i}+tr_i.

处理位置 ii 时,它的所有子节点都已经把贡献传来,此时 tritr_i 就是它的子树大小。若 i=faaii=fa_{a_i},即可令 ansai=trians_{a_i}=tr_i。

预处理最后出现的位置、建立跳转和累加子树大小都只需线性扫描,最后输出 mm 个答案,总时间复杂度为 O(n+m)O(n+m),空间复杂度为 O(n+m)O(n+m)。

参考代码

#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]<<" ";
}

留言

可以匿名留言,无需注册或登录。昵称和邮箱均可不填,邮箱不会公开显示。