挑战赛#29 | 官方题解

userId_undefined
NoonMaple
7月全勤卷王出道萌新时空双修者快乐小狗题解仙人传道者

2026-03-25 11:32:02

发布于：浙江

440阅读
0回复
0点赞

挑战赛29题解

本次题目的总体难度如下，各位选手可以借此评估一下自身的技术水平

题目编号 题目标题 难度
T1 午枫的字符串移动3 入门
T2 午枫的染色游戏 普及-
T3 小枫的X 普及/提高-
T4 小午的哈希表 普及/提高-
T5 午枫的邻居 普及/提高-
T6 小安的新数组 普及/提高-

T1 午枫的字符串移动3

题目大意

给定两个长度相同的字符串 ss 和 tt ，ss 的每个字符都可以循环右移，判断是否可以将 ss 变为 tt 。

解题思路

直接判断 ss 和 tt 的每位字符的差值是否相同即可。

参考代码

#include <bits/stdc++.h>
using namespace std;

int main(){
    string a,b;cin>>a>>b;
    for(int i=1;i<a.size();i++){
        if((a[i-1]-b[i-1]+26)%26!=(a[i]-b[i]+26)%26){
            cout<<"No"<<endl;
            return 0;
        }
    }
    cout<<"Yes"<<endl;
    return 0;
}

T2 午枫的染色游戏

题目大意

在一个 n×mn\times m 的透明网格中双方进行染色，问谁最后会赢。

解题思路

先说结论：如果 nn 和 mm 都为奇数时，小午必胜，否则小枫必胜。

  • 当 nn 和 mm 都为奇数时，小午先手只要在中心位置染色，接下来不管小枫怎么染，小午只要在小枫的中心对称位置上染上相同的颜色即可，最后一定是小午获胜。
  • 当 nn 和 mm 有一个不为奇数时，那么小枫就可以在小午染色的对称位置进行染色，最后一定是小枫获胜。

参考代码

#include <bits/stdc++.h>
using namespace std;
const int N = 200010;

#define ll long long

int main(){
    ll n,m;cin>>n>>m;
    if(n%2==1 && m%2==1) cout<<"Noon"<<endl;
    else cout<<"Maple"<<endl;
    return 0;
}

T3 小枫的X

题目大意

有一个仅包含 . 和 X 的字符串，最多替换 kk 的 . 为 X ，问最多能使多少个 X 连续。

解题思路

本体可以使用双指针或二分答案。

考虑双指针，优先滑动右端点 rr ，记录区间内 . 的数量，当数量大于 kk 时，移动左端点 ll 直至区间内 . 的数量小于等于 kk 。时间复杂度为 O(n)O(n) 。

考虑二分，我们可以用前缀和维护 X 的数量，二分求区间长度，遍历是否可以构成长度为 midmid 的字串即可。时间复杂度为 O(nlog⁡n)O(n\log n)

参考答案

方法一：双指针

#include<bits/stdc++.h>
using namespace std;

int main(){
    string s;
    int k;
	cin>>s>>k;
	s=' '+s;
    int cnt=0,ans=0;
	for(int i=1,j=0;i<s.size();i++){
		while(cnt<=k && j<s.size()){
            if(s[++j]=='.') cnt++;
        }
		ans=max(ans,j-i);

		if(s[i]=='.') cnt--;
	}
	cout<<ans;
	return 0;
}

方法二：二分

#include<bits/stdc++.h>
using namespace std;
const int N = 200010;

string t;
int k;
int s[N];

bool check(int x){
	for(int i=x-1;i<t.size();i++)
		if(s[i+1]-s[i-x+1]<=k) return true;
	return false;
}

int main(){
	cin>>t>>k;
	for(int i=0;i<t.size();i++){
		if(t[i]=='.') s[i+1]++;
		s[i+1]+=s[i];
	}

	int l=1,r=t.size();
	while(l<=r){
		int mid=(l+r)/2;
		if(check(mid)) l=mid+1;
		else r=mid-1;
	}
    cout<<l-1<<endl;
	return 0;
}

T4 小午的哈希表

题目大意

有一个 n=220n = 2^{20} 大小的数组，其实所有位置都为 −1-1 ，有 qq 次操作，每次操作会给出两个整数 opop 和 xx ，如果 op=1op=1 ，则从 x%nx\%n 的位置开始向右寻找第一个为 −1-1 的位置，找到后将此位置的值设置为 xx ；如果 op=2op=2 ，则输出数组 x%nx\%n 的值。

解题思路

首先，n=220=1048576n = 2^{20} = 1048576 ，这是数组可以开到的大小，所以我们可以用数组 aa 存储所有位置具体的数字。另外，还可以用 set 存储值为 −1-1 的位置。

查询时，如果 op=2op=2 ，则直接输出 a[x%n]a[x\%n] 即可；如果 op=1op=1 ，则可以在 set 中通过二分 lower_bound 函数找到第一个大于等于 x%nx\%n 的位置，如果没找到，则再用二分找第一个大于等于 00 的位置。

参考代码

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 200010;

int main(){
    vector<ll>a(1<<20,-1);
    set<ll>s;
    for(int i=0;i<(1<<20);i++) s.insert(i);
    
    int q;cin>>q;
    while(q--){
        ll op,x;cin>>op>>x;
        ll y=x%(1<<20);
        if(op==2) cout<<a[y]<<endl;
        else{
            auto pos=s.lower_bound(y);
            if(pos==s.end()){
                pos=s.lower_bound(0);
            }

            ll num=*pos;
            a[num]=x;
            s.erase(pos);
        }
    }
    return 0;
}

T5 午枫的邻居

题目大意

判断是否存在一种将编号为 11 到 nn 的 nn 个人的排列方式，使得以下 mm 个条件全部成立。

  • 条件：第 aia_i 个人与第 bib_i 个人必须相邻。

解题思路

简单来说，题目就是要求我们构造一条链，满足所有点对相邻的条件。

如果要构成一条链，需要满足：

  • 每个点的度最大为 22 。
  • 不存在环。

我们只需要判断以上两个条件是否都满足即可。对所有的点对关系建图，第一个条件直接记录每个点的度，判断是否存在点的度大于等于 33 的；第二个条件用 dfsdfs 或并查集判断图中是否存在环即可。

参考代码

#include <bits/stdc++.h>
using namespace std;
const int N = 100010;

int n,m;
vector<int>v[N];
int in[N];
bool vis[N];
bool flag;

void dfs(int u,int fa){
    if(vis[u] || flag){
        flag=true;
        return;
    }
    vis[u]=true;
    
    for(auto x:v[u]){
        if(x==fa) continue;
        dfs(x,u);
    }
}

int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int a,b;cin>>a>>b;
        v[a].push_back(b);
        v[b].push_back(a);
        in[a]++;
        in[b]++;
        if(in[a]>2 || in[b]>2) flag=true;
    }

    for(int i=1;i<=n;i++){
        if(vis[i]) continue;

        dfs(i,-1);
    }

    if(flag) cout<<"No"<<endl;
    else cout<<"Yes"<<endl;
    return 0;
}

T6 小安的新数组

题目大意

给定两个非递减数组 a,ba,b 满足 ai≤bia_i\leq b_i ，求非递减数组 cc 满足 ai≤ci≤bia_i\leq c_i\leq b_i 的个数，并对 998244353998244353 取模。

解题思路

考虑 DPDP。

状态表示：令 fi,jf_{i,j} 表示在数组 cc 的前 ii 个中且 ai≤ci≤ja_i\leq c_i \leq j 的数量。
状态计算：显然，fi,jf_{i,j}​ 一定包含 fi,j−1f_{i,j−1}​ 和 fi−1,jf_{i−1,j}​。所以转移方程如下（注意：jj 需要满足 j≤bi−1j\leq b_{i−1}​）：

{fi,j=fi,j−1+fi−1,j if j≤bi−1fi,j=fi,j−1+fi−1,bj−1 if j>bi−1\begin{cases} f_{i,j}=f_{i,j-1}+f_{i-1,j} & \text{ if } j\leq b_{i-1}\\ f_{i,j}=f_{i,j-1}+f_{i-1,b_{j-1}} & \text{ if } j>b_{i-1} \end{cases}

在递推之前先处理一下 i=1i=1 的状态，即递推起点。

最终结果为 fn,bnf_{n,b_n} 。

参考代码

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 3010;
const int mod = 998244353;

int a[N],b[N];
ll dp[N][N];   // 前 i 个数, 第 i 个数选小于 j 的方案数

int main(){
    int n;cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) cin>>b[i];

    for(int i=a[1];i<=b[1];i++) dp[1][i]=i-a[1]+1;
    for(int i=2;i<=n;i++){
        for(int j=a[i];j<=b[i];j++){
            dp[i][j]=(dp[i][j]+dp[i-1][min(b[i-1],j)])%mod;
            if(j>0) dp[i][j]=(dp[i][j]+dp[i][j-1])%mod;
        }
    }
    cout<<dp[n][b[n]]<<endl;
    return 0;
}
userId_undefined
去预览
0/2000

全部评论 64

热门讨论