官方题解 | 挑战赛24题解
2025-11-03 10:14:09
发布于：浙江
本次题目的总体难度如下，各位选手可以借此评估一下自身的技术水平
| 题目编号 | 题目标题 | 难度 |
|---|---|---|
| T1 | 午枫喝水 | 普及- |
| T2 | 午枫的排队 | 普及- |
| T3 | 午枫坐公交 | 普及- |
| T4 | 午枫的双向奔赴2 | 普及/提高- |
| T5 | 午枫的填数游戏 | 普及/提高- |
| T6 | 午枫的字符串反转 | 普及+/提高 |
T1 午枫喝水
题目大意
分别有两个容量为 和 的杯子，经过 次操作后，求两个杯子中剩余的水的体积。
解题思路
按照题意模拟即可。
参考代码
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main(){
int k,a,b;cin>>k>>a>>b;
int nowa=0,nowb=0;
while(k--){
if(nowa==a){
nowa=0;
}
else if(nowb==0){
nowb=b;
}
else{
int ch=min(a-nowa,nowb);
nowa+=ch;
nowb-=ch;
}
}
cout<<nowa<<" "<<nowb<<endl;
return 0;
}
T2 午枫的排队
题目大意
给定 个人的回答 ，表示第 个人站在第 个人的前面。
解题思路
定义 数组记录每个人的后一个是谁，单独记录排头，通过循环依次输出所有人的编号。
参考代码
#include <bits/stdc++.h>
using namespace std;
const int N = 300010;
int nxt[N];
int main(){
int n;cin>>n;
int rt=-1;
for(int i=1;i<=n;i++){
int x;cin>>x;
if(x==-1) rt=i;
else nxt[x]=i;
}
for(int i=rt;i;i=nxt[i]){
cout<<i<<" ";
}
return 0;
}
T3 午枫坐公交
题目大意
给定 次车上人数的变化量，求最后车上可能的最小人数。
解题思路
我们可以先假设上车时车上有 人，直接用变化量计算车上的人数总变化量，下车时车上的人数总变化量为 人，在中间计算过程中，记录下最小的非正数 ，我们只需要保证在最小的人数时刻为 人，那么其他时刻的人数一定大于等于 人，故答案为 。
参考答案
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main(){
int n;cin>>n;
ll mi=0;
ll res=0;
for(int i=0;i<n;i++){
int x;cin>>x;
res+=x;
mi=min(mi,res);
}
cout<<res+abs(mi)<<endl;
return 0;
}
T4 午枫的双向奔赴2
题目大意
有两个人位于不同的起点，每次移动两人只能往同一方向移动，如果在边界或移动方向有障碍物则不移动，求两人移动到同一点的最短时长。
解题思路
考虑到两个人第一次到达某个位置时，花费的时间最短，不妨设其中一人的位置为 ，另一人的位置为 。
令 为一人到达 ，另一人到达 花费的最短时间。因为每次移动只花费 单位时间，所以通过 即可实现。
时间复杂度
参考代码
#include <bits/stdc++.h>
using namespace std;
#define PII pair<int,int>
#define fi first
#define se second
const int N = 65;
const int INF = 1e9+10;
int n;
char g[N][N];
PII p1={-1,-1},p2={-1,-1};
int d[N][N][N][N];
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
void bfs(){
memset(d,-1,sizeof d);
queue<pair<PII,PII>>q;
q.push({p1,p2});
d[p1.fi][p1.se][p2.fi][p2.se]=0;
int ans=INF;
while(!q.empty()){
auto t=q.front();q.pop();
p1=t.fi;
p2=t.se;
if(p1==p2) ans=min(ans,d[p1.fi][p1.se][p2.fi][p2.se]);
for(int i=0;i<4;i++){
int x1=p1.fi+dx[i],y1=p1.se+dy[i];
int x2=p2.fi+dx[i],y2=p2.se+dy[i];
if(g[x1][y1]=='#') x1=p1.fi,y1=p1.se;
if(g[x2][y2]=='#') x2=p2.fi,y2=p2.se;
if(d[x1][y1][x2][y2]==-1){
d[x1][y1][x2][y2]=d[p1.fi][p1.se][p2.fi][p2.se]+1;
q.push({{x1,y1},{x2,y2}});
}
}
}
if(ans==INF) cout<<-1<<endl;
else cout<<ans<<endl;
}
int main(){
cin>>n;
for(int i=0;i<=n+1;i++){
for(int j=0;j<=n+1;j++){
if(i==0 || i==n+1 || j==0 || j==n+1) g[i][j]='#';
else cin>>g[i][j];
if(g[i][j]=='P'){
if(p1.fi==-1) p1={i,j};
else p2={i,j};
}
}
}
bfs();
return 0;
}
T5 午枫的填数游戏
题目大意
最初有一个长度 的序列 和 个数对 ，对于每个数对有两种方式执行操作：
- 将 替换为 ，次操作前提是 都小于或等于 。
- 将 替换为 ，次操作前提是 都小于或等于 。
问有多少种不同的操作序列，如果不能全部都执行，则输出 0 。
解题思路
首先我们观察到 ，因此可以尝试使用 的做法实现。
我们称第 个数对操作为 操作，选择第一种执行方式称为向左操作，选择第二种执行方式成为向右操作。
考虑所有两两数对 操作之间的关系，有 ，有以下几种情况：
- 当 时，任意选择即可。
- 当 并且 时，此时这两个操作直接矛盾，答案为 。
- 当 并且 时，操作 必须向左操作，操作 必须向右操作。
- 当 并且 时，操作 必须向右操作，操作 必须向左操作。
对于第三、四种情况，可能会出现不同数对间接矛盾的情况，此时答案也为 。
我们将所有数对操作的可能情况用 进行表示，其中 表示向左向右都可， 表示只能向左， 表示只能向右。
如果所有操作之间没有矛盾，那么答案至少为 ，对于那些上述 的操作，都有两种选择，其他都只有一种选择，不妨设 的操作数为 ，那么答案为 。注意取模。
参考代码
#include <bits/stdc++.h>
using namespace std;
const int N = 200010;
const int mod = 998244353;
// dir[i]: 标记第 i 个位置是的方向。
// -1 -- 两个方向都可; 0 -- 向左; 1 -- 向右
int dir[N];
void work(int pos,int x){
if(dir[pos]==-1) dir[pos]=x;
if(dir[pos]!=x){
cout<<0<<endl;
exit(0);
}
}
int main(){
int n,q;cin>>n>>q;
vector<int>p(q+1),v(q+1);
for(int i=1;i<=q;i++){
cin>>p[i]>>v[i];
dir[i]=-1;
}
for(int i=1;i<=q;i++){
for(int j=i+1;j<=q;j++){
// 1. v[i]<=v[j]: i,j 两个位置都可做两种操作
if(v[i]<=v[j]) continue;
// 2. v[i]>v[j] and p[i]=p[j]: 矛盾, 输出0
if(p[i]==p[j]){
cout<<0<<endl;
return 0;
}
// 3. v[i]>v[j] and p[i]>p[j]: i 向右, j 向左 唯一确定
if(p[i]>p[j]){
work(i,1);
work(j,0);
}
// 4. v[i]>v[j] and p[i]<p[j]: i 向左, j 向右 唯一确定
else{
work(i,0);
work(j,1);
}
}
}
int res=1;
for(int i=1;i<=q;i++){
if(dir[i]==-1) res=res*2%mod;
}
cout<<res<<endl;
return 0;
}
T6 午枫的字符串反转
题目大意
给定一个长度为 的 串，有两种查询，第一种查询为反转区间 的 0 和 1 ，第二种查询为判断子串 是否为好字符串，好字符串的定义为字符串中任意连续的 个字符都不相同的字符串是好字符串。
解题思路
不妨设长度为 的序列 ，如果 ，则让 ，否则 。
对于第一种查询 1 L R ，由于区间 内的相邻字符的关系不会发生改变，所以对于整个序列 ，只有 和 的位置发生改变，即修改 为 以及 为 。其中，如果 或 ，则对应序列位置不发生改变。
对于第二种查询 2 L R ，如果 ，那么答案为 Yes ，否则为 No 。
对于以上操作，可以使用线段树或树状数组进行维护和查询。
参考代码
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll INF = 1e18+10;
const ll N = 1000010;
string a;
struct segtree{
int l,r;
bool is;
char cl,cr;
int lazy;
}tr[N*4];
void pushup(segtree &u,segtree &l,segtree &r){
u.cl=l.cl;
u.cr=r.cr;
if(l.is==false || r.is==false || l.cr==r.cl){
u.is=false;
}
else u.is=true;
}
void pushup(int u){
pushup(tr[u],tr[u<<1],tr[u<<1|1]);
}
void pushdown(int u){
tr[u<<1].lazy^=tr[u].lazy;
tr[u<<1|1].lazy^=tr[u].lazy;
if(tr[u].lazy){
tr[u<<1].cl^=1;
tr[u<<1].cr^=1;
tr[u<<1|1].cl^=1;
tr[u<<1|1].cr^=1;
}
tr[u].lazy=0;
}
void build(int u,int l,int r){
if(l==r){
tr[u]={l,r,1,a[l],a[l],0};
return;
}
tr[u]={l,r};
int mid=l+r>>1;
build(u<<1,l,mid);
build(u<<1|1,mid+1,r);
pushup(u);
}
void modify(int u,int l,int r,int d){
if(tr[u].l>=l && tr[u].r<=r){
tr[u].cl^=1;
tr[u].cr^=1;
tr[u].lazy^=d;
return;
}
pushdown(u);
int mid=tr[u].l+tr[u].r>>1;
if(l<=mid) modify(u<<1,l,r,d);
if(r>mid) modify(u<<1|1,l,r,d);
pushup(u);
}
segtree query(int u,int l,int r){
if(tr[u].l>=l && tr[u].r<=r){
return tr[u];
}
pushdown(u);
int mid=tr[u].l+tr[u].r>>1;
if(r<=mid) return query(u<<1,l,r);
else if(l>mid) return query(u<<1|1,l,r);
else{
auto left=query(u<<1,l,r);
auto right=query(u<<1|1,l,r);
segtree res;
pushup(res,left,right);
return res;
}
}
int main(){
int n,q;cin>>n>>q;
cin>>a;a=' '+a;
build(1,1,n);
while(q--){
int op,l,r;cin>>op>>l>>r;
if(op==1){
modify(1,l,r,1);
}
else{
if(query(1,l,r).is) cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
}
return 0;
}
这里空空如也
有帮助，赞一个