官方题解 | 挑战赛20

NoonMaple

2025-07-14 08:13:05

发布于：浙江

115阅读

0回复

0点赞

官方题解 | 挑战赛20

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

题目编号	题目标题	难度
T1	小午的222	入门
T2	午枫的01树中心	普及-
T3	午枫爱搬家2	普及-
T4	午枫的又一个01串	普及/提高-
T5	午枫的彩排	普及/提高-
T6	午枫的字符串修改	普及/提高-

T1 小午的222

题目大意

有一个形如 $x00...0$ 的数字，求这个数字可以分解出多少个 $2$ 。

解题思路

本题输入的数字非常大，无法用 int 或 long long 存储，可以用 string 存储。

形如 $x00\dots0$ $(x\in[1,9])$ 的数字，可以看成 $x\times 10\times10\times \dots\times10$ ，而 $10=2\times5$ ，所以每个 $10$ 可以分解出一个 $2$ 。那么这串数字有多少个 $0$ 就能分解出多少个 $2$ ，剩下 $x$ 单独分解一下，即可得到答案。

参考代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'

signed main(){
    string s;cin>>s;
    int res=(int)s.size()-1;
    int x=s[0]-'0';
    while(x && x%2==0){
        x/=2;
        res++;
    }
    cout<<res<<endl;
}

T2 午枫的01树中心

题目大意

有一棵 $01$ 树，求有多少个节点与其周围所有节点的权值都不同。

解题思路

我们只需要在建好图后，对每一个点进行判断是否是中心节点。

判断每一个节点时，只需要遍历其周围所有距离为 $1$ 的节点是否与他的权值不相同即可。

参考代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'

signed main(){
    int n;cin>>n;
    vector<int>c(n+1);
    for(int i=1;i<=n;i++) cin>>c[i];
    vector<vector<int>>v(n+1);
    for(int i=1;i<n;i++){
        int a,b;cin>>a>>b;
        v[a].push_back(b);
        v[b].push_back(a);
    }

    int res=0;
    for(int i=1;i<=n;i++){
        int flag=1;
        for(auto x:v[i]){
            if(!(c[x]^c[i])) flag=0;
        }
        res+=flag;
    }
    cout<<res<<endl;
}

T3 午枫爱搬家2

题目大意

有 $n$ 件物品，每件物品有体积和价值两种属性，有一辆容量为 $m$ 的卡车，求搬运的物品在没超过卡车容量的前提下最大能存放的价值。

解题思路

本题考虑用 $01$ 背包求解。

设 $dp_{j}$ 表示消耗 $j$ 的容积时，能得到的最大价值。

那么状态转移为 $dp_{j}=max(dp_{j},dp_{j-w_i}+v_i)$ 。

参考代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'

signed main(){
    int n,m;cin>>n>>m;
    vector<int>w(n+1),v(n+1);
    for(int i=1;i<=n;i++) cin>>w[i]>>v[i];

    vector<int>dp(m+1);
    for(int i=1;i<=n;i++){
        for(int j=m;j>=w[i];j--){
            dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
        }
    }

    cout<<dp[m]<<endl;
}

T4 午枫的又一个01串

题目大意

给定一个 $01$ 串，这个串的度为相邻两位元素不相同的个数，可以进行指定操作最多 $m$ 次，求出最小度是多少。

解题思路

对于一个 $01$ 串，如果我们进行的操作区间不在开头也不在结尾，即 $[l,r]$ 满足 $1<l<r<n$ ，不难 $s_l$ 和 $s_{l-1}$ 从不同变为相同， $s_r$ 和 $s_{r+1}$ 从不同变为相同。所以当我们对中间部分操作一次，度就会减 $2$ 。

考虑完中间部分操作的影响，接下来考虑开头和结尾操作会有什么影响：

如果开头 $s_1=1$ ，则无法操作，同理，如果结尾 $s_n=0$ 也无法操作。

如果开头 $s_1=0$ ，我们对区间 $[1,r]$ $(1<r<n)$ 做一次操作后，由于 $s_1$ 前面没有数字了，原本就没有度，所以左端点的改变不会的度产生影响， $s_r$ 和 $s_{r+1}$ 从不同变为相同，因此此次操作会让度减少 $1$ 。同理，对结尾 $s_n=1$ ，做一次操作也会让度减少 $1$ 。

因此，先求出原串的度，优先对串的中间部分进行操作，在判断开头结尾的情况做出相应操作，计算度的减少量即可。

参考代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'

void solve(){
    int n,m;cin>>n>>m;
    string s;cin>>s;s=' '+s;
    if(n==1){
        cout<<0<<endl;
        return;
    }

    int cnt=0;
    for(int i=1;i<n;i++){
        if(s[i]!=s[i+1]) cnt++;
    }

    if(cnt<2){
        cout<<cnt<<endl;
        return;
    }

    int ex=0;
    if(s[1]=='0') ex++;
    if(s.back()=='1') ex++;

    int need=0;
    need=(cnt-ex)/2;
    if(m>=need+ex) cout<<min(1ll,cnt)<<endl;
    else{
        if(ex==0) cout<<cnt-2*m<<endl;
        else if(ex==1){
            if(m<=need) cout<<cnt-2*m<<endl;
            else cout<<cnt-2*need-min(ex,m-need)<<endl;
        }
        else if(ex==2){
            if(m<=need) cout<<cnt-2*m<<endl;
            else cout<<cnt-2*need-min(ex,m-need)<<endl;
        }
    }
}

signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int T=1;//cin>>T;
    while(T--){
        solve();
    }
    return 0;
}

T5 午枫的彩排

题目大意

有 $n$ 名演员，每位演员有特定的入场时间和退场时间，还有自身的能力值。入场时会帮助所有还在场且能力值小于等于他的演员，他会获得 $w_i-minw$ 的评分。求所有演员的评分。

解题思路

由于演员的入场顺序和入场时间有关，我们可以将所有演员按照入场顺序从小到大排序。

按照能力值为第一关键字，退场时间为第二关键字放到优先队列中，按照从小到大的顺序排序，这样当我们遍历到某一位演员 $x$ 时，优先队列中第一个退场时间大于 $s_x$ 的演员的能力值既是当前场上能力值最小的一位演员。

时间复杂度 $O(nlogn)$

参考代码

#include <bits/stdc++.h>
using namespace std;
#define PII pair<int,int>
#define int long long
#define endl '\n'

struct P{
    int a,s,t;
    int id,ans;
};

bool cmp(P a,P b){return a.s<b.s;}
bool cmpid(P a,P b){return a.id<b.id;}

signed main(){
    int n;cin>>n;
    vector<P>p(n+1);
    for(int i=1;i<=n;i++){
        cin>>p[i].a>>p[i].s>>p[i].t;
        p[i].id=i;
    }

    sort(p.begin()+1,p.end(),cmp);
    priority_queue<PII,vector<PII>,greater<PII>>q;//{a[i],t[i]};
    for(int i=1;i<=n;i++){
        while(!q.empty()){
            auto [c,r]=q.top();
            if(r<=p[i].s){
                q.pop();
                continue;
            }

            if(p[i].a>c) p[i].ans=p[i].a-c;
            break;
        }
        q.push({p[i].a,p[i].t});
    }

    sort(p.begin()+1,p.end(),cmpid);
    for(int i=1;i<=n;i++) cout<<p[i].ans<<" ";
}

T6 午枫的字符串修改

题目大意

给定一个初始串，有 $q$ 次操作，求操作完之后的字符串。

解题思路

本题一共有两个操作，这里记第一种操作为 $M$ ，第二种操作为 $C$ 。

我们可以先考虑如果只有第一种操作 $M$ 的话，我们可以用差分的思想完成对所有字符循环右移的移动量的记录。定义差分数组 $d$ ，假设对区间 $[l,r]$ 做一次 $M(t_i,x)$ 后，差分数组将进行以下变化：

$d[l]=d[l]+x\\ d[r+1]=d[r+1]-x$

最后用前缀和求出每一位的移动量即可得到最终的答案。

第一种操作我们用差分实现了，那么如果加上第二种操作，其实可以在第一种操作的基础上，记录整个字符串循环右移的偏移量 $dis$ 。假设做一次 $C(s,x)$ 后，偏移量 $dis=dis+x$ 。

此时如果再对区间 $[l.r]$ 做一次 $M(t_i,x)$ 的话，由于进行的是循环右移的操作，那么我们实际的区间需要对区间左右端点减去偏移量 $dis$ ，此时就会出现越界的情况，我们需要对越界的情况进行额外的处理：

如果没有越界，差分数组 $d$ 会进行以下变化：

$d[l-dis]=d[l-dis]+x\\ d[r-dis+1]=d[r-dis+1]-x$

如果左边界越界，有边界没越界，差分数组 $d$ 会进行以下变化：

$d[l-dis+n]=d[l-dis+n]+x\\ d[n+1]=d[n+1]-x\\ d[1]=d[1]+x\\ d[r-dis+1]=d[r-dis+1]-x$

如果两个边界都越界了，差分数组 $d$ 会进行以下变化：

$d[l-dis+n]=d[l-dis+n]+x\\ d[r-dis+n]=d[r-dis+1]-x$

在这个过程中，差分数组 $d$ 记录的移动量可以保证在 $26$ 以内，因为 $26$ 为一个循环，所以在记录的过程中移动量可以直接对 $26$ 取模。同理，字符串整体的偏移量 $dis$ 可以保证在 $n$ 以内。

最后对差分数组 $d$ 做一次前缀和就能得到原串每个位置的移动量，对每个位置加上这个移动量即可得到每一位变化后的字母。最后输出的时候还要注意把偏移量 $dis$ 的影响考虑进去。

时间复杂度 $O(q+n)$

参考代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'

signed main(){
    int n;cin>>n;
    string s;cin>>s;s=' '+s;
    
    int q;cin>>q;
    vector<int>d(n+2);
    int dis=0;
    while(q--){
        int op;cin>>op;
        if(op==1){
            int l,r,x;cin>>l>>r>>x;
            if(l-dis>=1){
                d[l-dis]+=x;
                d[r-dis+1]-=x;
            }
            else{
                if(r-dis>=1){
                    d[l-dis+n]+=x;
                    d[n+1]-=x;
                    d[1]+=x;
                    d[r-dis+1]-=x;
                }
                else{
                    d[l-dis+n]+=x;
                    d[r-dis+n+1]-=x;
                }
            }
        }
        else{
            int x;cin>>x;
            dis+=x;
            dis%=n;
        }
    }

    for(int i=1;i<=n;i++) d[i]+=d[i-1];
    for(int i=1;i<=n;i++){
        d[i]%=26;
        s[i]=(s[i]-'a'+d[i])%26+'a';
    }

    for(int i=n-dis+1;i<=n;i++) cout<<s[i];
    for(int i=1;i<=n-dis;i++) cout<<s[i];
}

有帮助，赞一个

去预览

0/2000

全部评论 4

Macw08(不加团队！)
d

2025-07-15 来自陕西
0
ppl 大帝
老师老师，T5 能不能给个具体的难度（我和 cjdst 赌了），是下为黄还是中位黄还是上位黄

2025-07-14 来自浙江
0
- NoonMaple
  回复ppl 大帝
  黄还分上中下三等么，要我说是6.573189位黄
  
  2025-07-14 来自浙江
  0
- ppl 大帝
  回复NoonMaple
  %%%
  
  2025-07-14 来自浙江
  0
- ppl 大帝
  回复ppl 大帝
  @复仇者_帅童
  
  2025-07-14 来自浙江
  0
༺ཌༀ༒Maximus༒ༀད༻
d

2025-07-14 来自浙江
0
ppl 大帝
%%%

2025-07-14 来自浙江
0

官方题解 | 挑战赛20

T1 小午的222

T2 午枫的01树中心

T3 午枫爱搬家2

T4 午枫的又一个01串

T5 午枫的彩排

T6 午枫的字符串修改

全部评论 4

热门讨论