官方题解 | 挑战赛#23 题解

NoonMaple

2025-10-08 09:44:52

发布于：浙江

50阅读

0回复

0点赞

官方题解 | 挑战赛#23 题解

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

题目编号	题目标题	难度
T1	NOON	入门
T2	maple序列	普及-
T3	午枫的石子合并	普及-
T4	午枫的彩排2	普及/提高-
T5	午枫勇闯移动迷宫	普及/提高-
T6	午枫的创造	普及+/提高

T1 NOON

题目大意

对于一个字符串，找出有多少个 "NOON" 子串。

解题思路

枚举所有可能位置，判断是否为 "NOON" 。

参考代码

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

int main(){
    string s;cin>>s;
    int res=0;
    for(int i=0;i+3<s.size();i++){
        if(s[i]=='N' && s[i+1]=='O' && s[i+2]=='O' && s[i+3]=='N') res++;
    }
    cout<<res<<endl;
    return 0;
}

T2 maple序列

题目大意

在序列 $a$ 中选出偶数个数，使得重新排列后可以变成 "maple序列" ，求 "maple序列" 长度的最大值。

解题思路

观察到本题 $a_i$ 的数据范围很小，所以我们可以枚举 $b_1+b_{2}$ 的值，统计 "maple序列" 的长度，记录最大值即可。

参考代码

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

int cnt[N*2];

int main(){
    int n;cin>>n;
    for(int i=1;i<=n;i++){
        int x;cin>>x;
        cnt[x]++;
    }

    int ans=0;
    for(int i=1;i<N*2;i++){
        int res=0;
        for(int j=1;j<=i-j;j++){
            if(i-j==j) res+=cnt[j]/2*2;
            else res+=min(cnt[j],cnt[i-j])*2;
        }
        ans=max(ans,res);
    }
    cout<<ans<<endl;

    return 0;
}

T3 午枫的石子合并

题目大意

有 $n$ 堆石子，每次可以选择一堆将至多 $k$ 个石子移动到相邻的石子堆中，求将所有石子合并到一堆所需要的最少操作次数。

解题思路

如果要将第 $i$ 堆石子合并到第 $i+1$ 堆中，假设第 $i$ 堆有 $x$ 个石子，所需要的操作次数为 $\lceil\frac{x}{k}\rceil$ 。

如果最终所有石子会合并到第 $i$ 堆中，由于中间计算过程中涉及到上去整，所以 $[1,i-1]$ 堆一定是从第 $1$ 堆向右合并的， $[i+1,n]$ 堆一定是从第 $n$ 堆向左合并的。我们可以先预处理合并前缀所需最小操作次数以及合并后缀最小操作次数。

所以我们可以枚举最终合并到哪一堆中，统计合并成一堆所需最小操作次数即可。

参考答案

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

int n,k;
int a[N];
ll pre[N],suf[N];

int main(){
    cin>>n>>k;
    for(int i=1;i<=n;i++) cin>>a[i];
    
    ll sum=0;
    for(int i=1;i<=n;i++){
        sum+=a[i];
        pre[i]=pre[i-1]+(sum+k-1)/k;
    }
    sum=0;
    for(int i=n;i>=1;i--){
        sum+=a[i];
        suf[i]=suf[i+1]+(sum+k-1)/k;
    }

    ll res=INF;
    for(int i=1;i<=n;i++){
        res=min(res,pre[i-1]+suf[i+1]);
    }
    cout<<res<<endl;

    return 0;
}

T4 午枫的彩排2

题目大意

每次操作可以将任意个舞台灯光亮度 $+1$ 或 $-1$ ，求所有舞台灯光调整为目标值的最少操作次数。

解题思路

首先我们会发现，如果同时对第 $i$ 个舞台使用 $+1$ 操作和 $-1$ 操作，答案一定不会变得更优。因此我们可以将所有数分成两类，一类只使用 $+1$ 操作，一类只使用 $-1$ 操作。

所以我们可以对每一个舞台都分别计算出只用 $+1$ 操作和 $-1$ 操作，并用 pair<int,int> 存储，按照第一关键词排序，此时不难发现，如果第 $i$ 个舞台灯光只用 $+1$ 操作最优，那么 $[1,i]$ 的舞台灯光都用 $+1$ 操作最优，剩下的 $[i+1,n]$ 都用 $-1$ 操作。

因此可以预处理使用 $-1$ 操作的后缀 $max$ ，枚举分界点 $i$ ，计算第 $i$ 的花费和 $i+1$ 的后缀 $max$ 之和，统计最小值即可。

参考代码

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

int n,m;
int a[N],b[N];
pair<int,int> p[N];
int suf[N];

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

    for(int i=1;i<=n;i++){
        if(b[i]>a[i]) p[i]={b[i]-a[i],m-(b[i]-a[i])};
        else p[i]={m-(a[i]-b[i]),a[i]-b[i]};
    }
    sort(p+1,p+n+1);

    suf[n+1]=0;
    for(int i=n;i>=1;i--){
        suf[i]=max(suf[i+1],p[i].second);
    }

    int res=INF;
    for(int i=0;i<=n;i++){
        res=min(res,p[i].first+suf[i+1]);
    }
    cout<<res<<endl;
}

int main(){
    int T=1;cin>>T;
    while(T--){
        solve();
    }
    return 0;
}

T5 午枫勇闯移动迷宫

题目大意

有一个 $n\times m$ 的迷宫，每个格子有一种颜色，每种颜色代表一种移动方向，最多改变 $k$ 个格子的颜色，判断能否从 $(1,1)$ 移动到 $(n,m)$ 。

解题思路

考虑每个格子的上下左右四个移动方向，可以对相邻格子都建有向边，若当前格子地板的移动方向与要移动的方向相同，建一条边权为 $0$ 的有向边，若方向不同，建一条边权为 $1$ 的有向边。

于是问题就转化为了最短路问题，求出从 $(1,1)$ 到达 $(n,m)$ 需要花费的最小代价，若比 $k$ 大，则无法逃离迷宫，否则，可以逃离迷宫。

参考代码

#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9+10;

struct P{
    int dis;
    int x,y;

    bool operator<(const P& b) const {
        return dis>b.dis;
    }
};

map<char,int>dir;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

void solve(){
    int n,m,k;cin>>n>>m>>k;
    vector<vector<char>>g(n+1,vector<char>(m+1));
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>g[i][j];
        }
    }

    priority_queue<P>q;
    vector<vector<bool>>vis(n+1,vector<bool>(m+1));
    vector<vector<int>>d(n+1,vector<int>(m+1,INF));
    d[1][1]=0;
    q.push({0,1,1});
    while(!q.empty()){
        auto [dis,x,y]=q.top();
        q.pop();

        if(vis[x][y]) continue;
        vis[x][y]=true;

        for(int i=0;i<4;i++){
            int nx=x+dx[i];
            int ny=y+dy[i];
            if(nx<1 || nx>n || ny<1 || ny>m) continue;

            if(dir[g[x][y]]==i){
                if(d[nx][ny]>d[x][y]){
                    d[nx][ny]=d[x][y];
                    q.push({d[nx][ny],nx,ny});
                }
            }
            else{
                if(d[nx][ny]>d[x][y]+1){
                    d[nx][ny]=d[x][y]+1;
                    q.push({d[nx][ny],nx,ny});
                }
            }
        }
    }

    if(d[n][m]>k) cout<<"NO"<<endl;
    else cout<<"YES"<<endl;
}

int main(){
    dir['O']=0;dir['G']=1;dir['B']=2;dir['Y']=3;
    int T=1;cin>>T;
    while(T--){
        solve();
    }
    return 0;
}

T6 午枫的创造

题目大意

对于一个字符串序列，可以修改任意一个位置的字符串，问最终有多少种可能，使得所有长度至少为 $2$ 的字符串序列中的所有字符集合与原来的相同。

解题思路

首先由于每一个字符串中的字符不会重复且长度最大不会超过 $26$ ，那么我们不妨将每个小写字母用二进制表示，这样每个字符串都可以用一个整数来表示。那么对于第三点要求，就转化成：对于所有 $1\leq l<r\leq n$ ，均有 $a_l | a_{l+1}|...|a_r = b_l|b_{l+1}|...|b_r$ 。

接下来考虑如何满足题目要求的第两、三个条件。不难发现，当我们要修改位置 $i$ 的元素是，对于一个包含 $i$ 区间 $[l,r]$ ，满足 $a_l | a_{l+1}|...|a_r = b_l|b_{l+1}|...|b_r$ ，那么一定需要满足长度至少为 $2$ 的区间按位或值不变。因此，我们只需要让 $a_i$ 与其相邻的数按位或后的值不变即可。

假设当前的数为 $a_i$ ，变化后的数为 $b_i$ 且 $b_i \ne a_i$ ，与其相邻的数为 $x$ ，那么对于每一位老说有以下几种情况：

$a_i | x$ 的这一位为 $0$ ，那么 $b_i$ 的这一位一定为 $0$ ；
$a_i | x$ 的这一位为 $1$ ，并且 $x$ 的这一位为 $0$ ，那么 $b_i$ 的这一位一定为 $0$ ；
$a_i | x$ 的这一位为 $1$ ，并且 $x$ 的这一位为 $1$ ，那么 $b_i$ 的这一位可以为 $0$ ，也可以为 $1$ .

综上，不难发现，只有第三种情况 $b_i$ 会有两种情况，我们统计有 $cnt$ 位会出现这种情况，那么位置 $i$ 的方案数就有 $2^{cnt}$ 个，由于需要满足 $a_i\ne b_i$ 这个条件，还要把方案数 $-1$ 。

最后将所有位置的方案数相加，即为答案。

参考代码

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

void solve(){
    int n,m;cin>>n>>m;
    vector<int>a(n+1);
    for(int i=1;i<=n;i++){
        string s;cin>>s;
        for(auto x:s){
            a[i]+=(1ll<<(x-'a'));
        }
    }
    
    ll res=0;
    for(int i=1;i<=n;i++){
        int x=(1<<m)-1;
        if(i>1) x&=a[i-1];
        if(i<n) x&=a[i+1];

        int cnt=0;
        for(int j=0;j<m;j++){
            if(x>>j&1) cnt++;
        }
        res+=(1ll<<cnt)-1;
    }
    cout<<res<<endl;
}

int main(){
    int T=1;cin>>T;
    while(T--){
        solve();
    }
    return 0;
}