官方题解 | 挑战赛20 本次题目的总体
2025-07-15 11:56:14
发布于：广东
官方题解 | 挑战赛20
本次题目的总体难度如下，各位选手可以借此评估一下自身的技术水平
题目编号 题目标题 难度
T1 小午的222 入门
T2 午枫的01树中心 普及-
T3 午枫爱搬家2 普及-
T4 午枫的又一个01串 普及/提高-
T5 午枫的彩排 普及/提高-
T6 午枫的字符串修改 普及/提高-
T1 小午的222
题目大意
有一个形如
x
00...0
x00...0 的数字，求这个数字可以分解出多少个
2
2 。
解题思路
本题输入的数字非常大，无法用 int 或 long long 存储，可以用 string 存储。
形如
x
00
…
0
x00…0
(
x
∈
[
1
,
9
]
)
(x∈[1,9]) 的数字，可以看成
x
×
10
×
10
×
⋯
×
10
x×10×10×⋯×10 ，而
10
2
×
5
10=2×5 ，所以每个
10
10 可以分解出一个
2
2 。那么这串数字有多少个
0
0 就能分解出多少个
2
2 ，剩下
x
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
01 树，求有多少个节点与其周围所有节点的权值都不同。
解题思路
我们只需要在建好图后，对每一个点进行判断是否是中心节点。
判断每一个节点时，只需要遍历其周围所有距离为
1
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
n 件物品，每件物品有体积和价值两种属性，有一辆容量为
m
m 的卡车，求搬运的物品在没超过卡车容量的前提下最大能存放的价值。
解题思路
本题考虑用
01
01 背包求解。
设
d
p
j
dp
j
表示消耗
j
j 的容积时，能得到的最大价值。
那么状态转移为
d
p
j
m
a
x
(
d
p
j
,
d
p
j
−
w
i
+
v
i
)
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
01 串，这个串的度为相邻两位元素不相同的个数，可以进行指定操作最多
m
m 次，求出最小度是多少。
解题思路
对于一个
01
01 串，如果我们进行的操作区间不在开头也不在结尾，即
[
l
,
r
]
[l,r] 满足
1
<
l
<
r
<
n
1<l<r<n ，不难
s
l
s
l
和
s
l
−
1
s
l−1
从不同变为相同，
s
r
s
r
和
s
r
+
1
s
r+1
从不同变为相同。所以当我们对中间部分操作一次，度就会减
2
2 。
考虑完中间部分操作的影响，接下来考虑开头和结尾操作会有什么影响：
如果开头
s
1
1
s
1
=1 ，则无法操作，同理，如果结尾
s
n
0
s
n
=0 也无法操作。
如果开头
s
1
0
s
1
=0 ，我们对区间
[
1
,
r
]
[1,r]
(
1
<
r
<
n
)
(1<r<n) 做一次操作后，由于
s
1
s
1
前面没有数字了，原本就没有度，所以左端点的改变不会的度产生影响，
s
r
s
r
和
s
r
+
1
s
r+1
从不同变为相同，因此此次操作会让度减少
1
1 。同理，对结尾
s
n
1
s
n
=1 ，做一次操作也会让度减少
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
n 名演员，每位演员有特定的入场时间和退场时间，还有自身的能力值。入场时会帮助所有还在场且能力值小于等于他的演员，他会获得
w
i
−
m
i
n
w
w
i
−minw 的评分。求所有演员的评分。
解题思路
由于演员的入场顺序和入场时间有关，我们可以将所有演员按照入场顺序从小到大排序。
按照能力值为第一关键字，退场时间为第二关键字放到优先队列中，按照从小到大的顺序排序，这样当我们遍历到某一位演员
x
x 时，优先队列中第一个退场时间大于
s
x
s
x
的演员的能力值既是当前场上能力值最小的一位演员。
时间复杂度
O
(
n
l
o
g
n
)
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
q 次操作，求操作完之后的字符串。
解题思路
本题一共有两个操作，这里记第一种操作为
M
M ，第二种操作为
C
C 。
我们可以先考虑如果只有第一种操作
M
M 的话，我们可以用差分的思想完成对所有字符循环右移的移动量的记录。定义差分数组
d
d ，假设对区间
[
l
,
r
]
[l,r] 做一次
M
(
t
i
,
x
)
M(t
i
,x) 后，差分数组将进行以下变化：
d
[
l
]
d
[
l
]
+
x
d
[
r
+
1
]
d
[
r
+
1
]
−
x
d[l]=d[l]+x
d[r+1]=d[r+1]−x
最后用前缀和求出每一位的移动量即可得到最终的答案。
第一种操作我们用差分实现了，那么如果加上第二种操作，其实可以在第一种操作的基础上，记录整个字符串循环右移的偏移量
d
i
s
dis 。假设做一次
C
(
s
,
x
)
C(s,x) 后，偏移量
d
i
s
d
i
s
+
x
dis=dis+x 。
此时如果再对区间
[
l
.
r
]
[l.r] 做一次
M
(
t
i
,
x
)
M(t
i
,x) 的话，由于进行的是循环右移的操作，那么我们实际的区间需要对区间左右端点减去偏移量
d
i
s
dis ，此时就会出现越界的情况，我们需要对越界的情况进行额外的处理：
如果没有越界，差分数组
d
d 会进行以下变化：
d
[
l
−
d
i
s
]
d
[
l
−
d
i
s
]
+
x
d
[
r
−
d
i
s
+
1
]
d
[
r
−
d
i
s
+
1
]
−
x
d[l−dis]=d[l−dis]+x
d[r−dis+1]=d[r−dis+1]−x
如果左边界越界，有边界没越界，差分数组
d
d 会进行以下变化：
d
[
l
−
d
i
s
+
n
]
d
[
l
−
d
i
s
+
n
]
+
x
d
[
n
+
1
]
d
[
n
+
1
]
−
x
d
[
1
]
d
[
1
]
+
x
d
[
r
−
d
i
s
+
1
]
d
[
r
−
d
i
s
+
1
]
−
x
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 会进行以下变化：
d
[
l
−
d
i
s
+
n
]
d
[
l
−
d
i
s
+
n
]
+
x
d
[
r
−
d
i
s
+
n
]
d
[
r
−
d
i
s
+
1
]
−
x
d[l−dis+n]=d[l−dis+n]+x
d[r−dis+n]=d[r−dis+1]−x
在这个过程中，差分数组
d
d 记录的移动量可以保证在
26
26 以内，因为
26
26 为一个循环，所以在记录的过程中移动量可以直接对
26
26 取模。同理，字符串整体的偏移量
d
i
s
dis 可以保证在
n
n 以内。
最后对差分数组
d
d 做一次前缀和就能得到原串每个位置的移动量，对每个位置加上这个移动量即可得到每一位变化后的字母。最后输出的时候还要注意把偏移量
d
i
s
dis 的影响考虑进去。
时间复杂度
O
(
q
+
n
)
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];
}
这里空空如也
有帮助，赞一个