ACGO挑战赛#21题解 2.0
2025-08-13 17:36:22
发布于：江苏
看了别人的题解后我自愧不如，所以我又在原题解上做了一点点的修改（包括T4的代码，请放心食用）
T1 午枫的切蛋糕
个人难度：入门|考察内容：分支结构
由题意得，要沿着直径或者半径平分成（n+1）块蛋糕。不难看出，如果（n+1）是偶数，就能沿着直径切（因为直径只能平均切成2份，所以只能为2的倍数），否则要沿着半径切。但是我们会发现n是大于等于0的，所以（n+1）可能会等于1，因为整个蛋糕已经是1份，所以无需再切。
代码如下：
#include<bits/stdc++.h>
using namespace std;
int n;
int main(){
cin>>n;
if(n+1!=1)cout<<(n+1)/(2-(n+1)%2);
else cout<<0;
}
T2 午枫的卡片游戏
个人难度：入门|考察内容：排序
这道题要我们比较卡片点数大小，虽然小枫的出牌顺序已经固定，但是答案不会因为将位置改变而发生变化，所以我们可以先用两个数组存放卡牌点数并升序排序，如果小午的牌大于小枫的牌，那么就将小午胜的局数加一并弃掉小午和小枫的牌，否则只弃掉小午的牌并让小午的下一张牌和小枫当前的牌比较。
代码如下：
#include<bits/stdc++.h>
using namespace std;
long long n,a[1000005],b[1000005],ai=1,bi=1,num;
int main(){
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=n;i++)cin>>b[i];
sort(a+1,a+n+1);
sort(b+1,b+n+1);
while(bi<=n){//因为小午的牌的序号一定大于小枫的牌的序号，所以只需要判断小午即可
if(a[ai]<b[bi]){
num++;
ai++,bi++;//弃掉小午和小枫的牌
}else{
bi++;//弃掉小午的牌
}
}
if(num*2>n)cout<<"YES";
else cout<<"NO";
}
T3 午枫的分割数组
个人难度：入门|考察内容：贪心
既然要数量最多的数的大小，那我们可以直接只选数组中最大的一个数，因为是小午将数组切分成前后两部分，所以可以“邪恶地”只给小枫数组最后一个数，如果第1~n-1个数没有大于第n个数的数（注意，这里是大于），就输出“NO”。
代码如下：
#include<bits/stdc++.h>
using namespace std;
long long n,k1,k2,a[1000005],maxn;
int main(){
cin>>n>>k1>>k2;
for(int i=1;i<n;i++){
cin>>a[i];
maxn=max(maxn,a[i]);
}
cin>>a[n];
if(maxn>a[n])cout<<"YES";
else cout<<"NO";
}
T4 小午的构造
个人难度：普及-|考察内容：模拟
仔细观察后就会发现，ac,aa,wa三个单词都含a，所以需要多增一个变量wordx并一直重复以下操作：
如果 x > y+z+wordx :
wordx++; x--;
结束后又出现了一个问题，如果还剩一个a呢？题目中要wa的数量尽可能少并且还要在最多单词的情况下，所以我们可以把一个wa拆开:
wa a->w a a->w aa
这样就需要再做一次判断：
如果 x < y+z+wordx 并且 z>0 :
z--;
最后输出，x > y+z 的情况就完成了。
接着再来考虑 y+z > x >y 的情况，如果a的数量大于c，那么a的数量就是能组成的最多单词数，wa的数量就是a减去c的数量。
最后剩下了 x < y 的情况，那么最多只能输出a的数量，输出 x 和 0 。
代码如下：
#include<bits/stdc++.h>
using namespace std;
long long t,x,y,z,wordx;
int main(){
cin>>t;
while(t--){
wordx=0;
cin>>x>>y>>z;
if(x>wordx+y+z){
while(x>wordx+y+z){
x--;
wordx++;
}
if(x<wordx+y+z&&z!=0)z--;
cout<<x<<" "<<z<<endl;
}else cout<<x<<" "<<max(x-y,0ll)<<endl;//也可以把两种方法合成一种
//}else if(x>y)cout<<x<<" "<<x-y<<endl;
//else cout<<x<<" "<<0<<endl;
}
}
T5 午枫的mex
个人难度：入门|考察内容：位运算
这道题需要先列一个表格：
| n | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|
| 答案 | 1 | 4 | 4 | 8 | 8 | 8 | 8 | 16 |
答案看上去就是2log2(n)+1,但是我们会发现一个特殊情况，在1的时候输出的是1，所以需要一个判断。
代码如下：
#include<bits/stdc++.h>
using namespace std;
long long t,n,ans;
int main(){
cin>>t;
while(t--){
cin>>n;
if(n==1){
cout<<1<<"\n";
continue;
}
n=log2(n)+1;
ans=1;
while(n--){
ans*=2;
}
cout<<ans<<"\n";
}
}
答案虽然已经分析出来了，但是背后的原理我们也可以分析一下（如果不感兴趣可以直接跳过）
因为是异或，所以位数只减不增，我们随便举一个二进制数做例子：
1010100011
那么能使它变成最大的数就是取反之后的数：
0101011100
因为每个数取反后都会比原数小，所以取反的数就无需考虑，最后的最大值+1就是2log2(n)+1。
那么为什么1的答案是1呢？因为1只有它自己能异或，而自己异或自己的答案是0，所以最大值+1=1。
T6 午枫的陪伴时间
个人难度：普及/提高-|考察内容：贪心，动态规划
这一道题让我们选择小午的要求并计算最少花费，在n项要求中可能会有重复的日期，所以我们先需要算出一日的最少花费：
我们先举个例子：
| 陪之前 | 陪之后 | 省了多少钱 |
|---|---|---|
| 15 | 13 | 2 |
| 21 | 18 | 3 （这个省的最多，选这个） |
| 1000 | 2000 | -1000 |
| 1111 | 1111 | 0 |
long long t,n,a[1000005],nc,nv,c[1000005],v[1000005],vis[1000005];
int main(){
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int i=1;i<=n;i++){
if(vis[a[i]]){
cin>>nc>>nv;
if(nc-nv<c[a[i]]-v[a[i]]){//求最小花费
swap(nc,c[a[i]]);
swap(nv,v[a[i]]);
}
num+=nv;
}else{
vis[a[i]]=1;
cin>>c[a[i]]>>v[a[i]];
}
}
}
接着再用动态规划解决多日的最少花费：
for(int i=1;i<=n;i++)v[i]+=v[i-1];//前缀和计算花费
for(int i=1;i<=n;i++){
if(ok[i])dp[i+t-1]=dp[i-1]+c[i]+v[i+t-1]-v[i];//如果这一天可以选择，那么接下来t天都只能陪1天，不陪t-1天
dp[i]=min(dp[i],dp[i-1]+v[i]-v[i-1]);
}
代码如下：
#include<bits/stdc++.h>
using namespace std;
long long dp[1000005],a[1000005],ok[1000005];
long long t,n,num,nc,nv,c[1000005],v[1000005],vis[1000005];
int main(){
cin>>n>>t;
memset(dp,0x3f3f3f3f3f,sizeof(dp));
dp[0]=0;
for(int i=1;i<=n;i++){
cin>>a[i];
ok[a[i]]=1;
}
for(int i=1;i<=n;i++){
if(vis[a[i]]){
cin>>nc>>nv;
if(nc-nv<c[a[i]]-v[a[i]]){
swap(nc,c[a[i]]);
swap(nv,v[a[i]]);
}
num+=nv;
}else{
vis[a[i]]=1;
cin>>c[a[i]]>>v[a[i]];
}
}
for(int i=1;i<=n;i++)v[i]+=v[i-1];
for(int i=1;i<=n;i++){
if(ok[i])dp[i+t-1]=dp[i-1]+c[i]+v[i+t-1]-v[i];
dp[i]=min(dp[i],dp[i-1]+v[i]-v[i-1]);
}
cout<<num+dp[n];
}
以上是全部内容，如果觉得哪里可以优化或更正可以在评论区留言（qwq）
有帮助，赞一个