2026CSP-J

虽然退役2年了，但还是做一下CSP-J叭。

#1.旅游 / travel

读入数据，按照规则进行判断。

Code：

#include
using namespace std;
int c1,c2;
int r1,r2;
char p1,p2;
int read(){int x,y;scanf("%1d%1d",&x,&y);return x*10+y;
}
int main(){c1=read(),r1=read();cin>>p1;c2=read(),r2=read();cin>>p2;if(c1==c2){printf("1");if(r1==r2){printf("1");if((p1<='C'&&p2<='C')||(p1>='D'&&p2>='D')){printf("1");if((p1<='C'&&p2<='C')){if(p1==p2-1||p2==p1-1)printf("1");else printf("0");}else{printf("1");}}else printf("00");}else printf("000");}else printf("0000");return 0;
}

#2.回文串 / string

我们只能修改，所以如果我们从字符串的两端开始，如果不同，就必须修改一个。相同的数字可能很多，可以对相同的字母做出相同的操作。设 \(p,q\) 是当前的两端，每次抵消掉 \(\min{a_p,a_q}\) 。

Code：

#include
using namespace std;
const int N=2e5+5;
typedef long long ll;
int n;
int a[N];
char ch[N];
int main(){scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d %c",&a[i],&ch[i]);}ll ans=0;int p=1,q=n;while(p

#3.按位与 / and

优先满足二进制下的最高位。因为是按位与，所以想要答案中有当前位，那么就必须找出 \(m\) 个有当前位的数字。如果有高位已经满足，考虑低位时，一定要在满足高位的情况下找到 \(m\) 个有低位的数字。可以记录当前答案 \(ans\) 。从高位向低位枚举 \(i\) ，那么所有 \(a_i\) 按位与 \(ans \ or \ 2^i\) （ \(or\) 是按位或）后有 \(m\) 个为 \(ans \ or \ 2^i\) ，那么当前位 \(i\) 是可以得到的，让 \(ans\) 成为 \(ans \ or \ 2^i\) 。

Code：

#include
using namespace std;
const int N=2e5+5;
int n,m;
int a[N];
int pw[31];
int ans;
bool check(int t){int now=ans|pw[t],tot=0;for(int i=1;i<=n;i++){if((a[i]&now)==now)tot++;}return tot>=m;
}
int main(){pw[0]=1;for(int i=1;i<=30;i++){pw[i]=pw[i-1]<<1;}scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)scanf("%d",&a[i]);for(int i=30;i>=0;i--){if(check(i))ans|=pw[i];}printf("%d\n",ans);return 0;
}

#4.纸牌游戏 / card

第 \(i\) 局的第一个是 \(a_i\) 。序列中最后一个 \(a_i\) 的位置是 \(p\) ，那么显然 \(i \sim p\) 中除了 \(a_i\) 都不会出现在最后的序列中。那么第 \(i\) 局的最终序列就是在第 \(p+1\) 局的前面添加一个 \(a_i\) 。我们设 \(f_i\) 表示第 \(1 \sim i\) 局会为 \(a_i\) 贡献 \(f_i\) 次。显然 \(f_i\) 初始都为 \(1\)。枚举到当前局 \(i\) 时，\(f_{p+1}\) 就要增加 \(f_i\) 。统计最后的 \(f_i\) 即可。

Code：

#include
using namespace std;
const int N=5e5+5;
int n,m;
int a[N];
int ed[N],f[N];
int ans[N];
int main(){scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){scanf("%d",&a[i]);ed[a[i]]=i;}for(int i=1;i<=n;i++){f[i]++;f[ed[a[i]]+1]+=f[i];ans[a[i]]+=f[i];}for(int i=1;i<=m;i++){printf("%d ",ans[i]);}return 0;
}