ACGO挑战赛#21 全题解
2025-08-10 22:00:01
发布于：浙江
T1.午枫的切蛋糕
题目大意
小枫有n个朋友，加上自己共n+1人，需要将蛋糕平均分成n+1份，每刀沿直径或半径切，求最少刀数。
题目思路分析
总人数m = n+1，如果m=1，无需切刀输出0。如果m为偶数，沿直径切m/2刀，每刀分两份，可平均分。如果m为奇数，沿半径从中心切m刀，直接分m份。代码通过判断m的奇偶性直接计算结果。
易错点注意
注意n=0时m=1，输出0而非其他。边界如n=1（m=2，偶，输出1）需验证奇偶逻辑正确。
AC代码
#include<bits/stdc++.h>
using namespace std;
int n;
int main(){
cin>>n;
n++;
if(n==1)cout<<0;
else if(n%2==0)cout<<n/2;
else cout<<n;
return 0;
}
T2.午枫的卡片游戏
题目大意
小枫卡片顺序固定为a[0..n-1]，小午卡片b可任意排列，每轮比大小，相同算小枫胜，求小午能否胜超过n/2轮（严格多数）。
题目思路分析
将a和b升序排序，从大到小匹配：用小午的最大b[j]尝试赢小枫的最大未匹配a[i]，若b[j]>a[i]则小午胜一轮，同时i--,j--，否则只i--丢弃a[i]。统计胜轮c，若c >= n/2 +1则YES否则NO。此贪心确保小午用最小必要的大牌赢最多轮。
易错点注意
注意相同算小枫胜，故比时严格>才计小午胜。n=1时n/2+1=1，需仔细检查边界。
AC代码
#include<bits/stdc++.h>
using namespace std;
const int N=1000010;
int n,a[N],b[N];
int main(){
cin>>n;
for(int i=0;i<n;i++)cin>>a[i];
for(int i=0;i<n;i++)cin>>b[i];
sort(a,a+n);
sort(b,b+n);
int i=n-1,j=n-1,c=0;
while(i>=0&&j>=0){
if(b[j]>a[i]){
c++;
j--;
i--;
}
else i--;
}
if(c>=n/2+1)cout<<"YES";
else cout<<"NO";
return 0;
}
T3.午枫的分割数组
题目大意
将数组v分割成前后两非空部分，小午前小枫后，各选<=k1/k2个数，最优使各自子集中频率最高数的数值最大，求小午是否一定胜（其值>小枫值）。
题目思路分析
由于k1,k2>=1，各部分最优频率最高数的值即部分最大值（选只含最大值的子集即可）。计算前缀最大p[i]（0到i的最大）和后缀最大s[i]（i到n-1的最大）。遍历分割点i=0到n-2，若存在p[i] > s[i+1]则小午取前获胜，输出YES否则NO。
易错点注意
注意分割必须非空，故i<n-1。数组索引从0，p[0]=v[0],s[n-1]=v[n-1]需正确初始化。
AC代码
#include<bits/stdc++.h>
using namespace std;
int n,k1,k2;
vector<int> v,p,s;
int main() {
cin>>n>>k1>>k2;
v.resize(n);
for(int i=0;i<n;i++)cin>>v[i];
p.resize(n);p[0]=v[0];
for(int i=1;i<n;i++)p[i]=max(p[i-1],v[i]);
s.resize(n);s[n-1]=v[n-1];
for(int i=n-2;i>=0;i--)s[i]=max(s[i+1],v[i]);
bool w=false;
for(int i=0;i<n-1;i++)if(p[i]>s[i+1]){w=true;break;}
cout<<(w?"YES":"NO");
return 0;
}
T4.小午的构造
题目大意
用x个a、y个c、z个w构造ac、aa、wa三种单词，最大化单词数m，并在m最大下最小化wa数。
题目思路分析
先用min(x,y)做ac，剩余ra = x - min(x,y)个a。最大wa为mw = min(ra,z)，最大m = ac + mw + (ra - mw)/2（剩余a做aa）。从wa=0到mw枚举，计算m = ac + wa + (ra - wa)/2，找到首个达最大m的wa作为最小wa。
易错点注意
注意ra - wa须偶数才能全做aa，否则/2 floor。T<=1e5，x,y,z<=100，枚举wa<=100高效。
AC代码
#include<bits/stdc++.h>
using namespace std;
int T,x,y,z;
int main() {
cin>>T;
while(T--) {
cin>>x>>y>>z;
int ac=min(x,y);
int ra=x-ac;
int mw=min(ra,z);
int mm=ac+mw+(ra-mw)/2;
for(int wa=0;wa<=mw;wa++) {
int m=ac+wa+(ra-wa)/2;
if(m==mm) {
cout<<mm<<" "<<wa<<endl;
break;
}
}
}
return 0;
}
T5.午枫的mex
题目大意
求mex{i ⊕ j | i ∈ [1, n], j ∈ [1, n]}，多组查询n<=1e18。
题目思路分析
对于n<=2，直接输出1（验证集合缺1或为{0,3}缺1）。对于n>2，i xor j范围[0,2n-1]内，集合覆盖[0, -1]其中 > n-1的最大幂，mex为（floor(log2(n-1))+1位）。代码计算n-1的最高位k+1，输出1LL<<k。
易错点注意
n=1或2特殊处理，避免log2(0)未定义。n=1e18用ll，移位小心溢出。
AC代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
int t;
cin >> t;
while (t--) {
ll n;
cin >> n;
if (n <= 2) {
cout << "1\n";
} else {
ll x = n - 1;
int k = 0;
while (x) {
k++;
x >>= 1;
}
cout << (1LL << k) << '\n';
}
}
return 0;
}
T6.午枫的陪伴时间
题目大意
n选项Each从起连续t天陪伴，，或不选买v_i礼物；选后[,+t-1]内其他选项不可选，求最小总花费。
题目思路分析
初始花费s = sum （全买礼物）。每个选项收益w = - ，若w>0更新起始d=a_i的最大b[d]。用dp f[i]表示前i个起始日最大收益：f[i] = max(f[i-1], f[i-t] + max(0,b[i]))，避免重叠。最终花费s - f[m]，m=n-t+1。
易错点注意
<=n-t+1，b[1..m]。dp索引从1，f[0]=0，i-t>=0检查。
AC代码
#include<bits/stdc++.h>
using namespace std;
int n, t;
vector<int> a;
vector<long long> b, f;
long long s;
int main() {
if (!(cin >> n >> t)) return 0;
a.assign(n + 1, 0);
for (int i = 1; i <= n; i++) cin >> a[i];
int m = n - t + 1;
b.assign(m + 1, 0);
f.assign(m + 1, 0);
for (int i = 1; i <= n; i++) {
long long c, v;
cin >> c >> v;
s += v;
long long w = v - c;
int d = a[i];
if (d <= m && w > b[d]) b[d] = w;
}
for (int i = 1; i <= m; i++) {
long long u = b[i] > 0 ? b[i] : 0;
long long p = (i - t >= 0) ? f[i - t] : 0;
long long q = p + u;
f[i] = max(f[i - 1], q);
}
cout << s - f[m];
return 0;
}
全部评论 13
【1补】已完成今日之所以我可以随意切换码风，是因为我没有作弊，我不需要如此隐藏，按照我的风格，我可以随时切换，用自己的方式书写我不需要有任何限制啊大学习
【6补】已完成不是哥们，现在为了不让你们怀疑，还得我还得精心把这些改的一样是吧？你看那些大型的编程比赛，有这种要求吗？大学习
【5补】已完成今日
#include<bits/stdc++.h> using namespace std; int n, t; vector<int> a; vector<long long> b, f; long long s; int main() { if (!(cin >> n >> t)) return 0; a.assign(n + 1, 0); for (int i = 1; i <= n; i++) cin >> a[i]; int m = n - t + 1; b.assign(m + 1, 0); f.assign(m + 1, 0); for (int i = 1; i <= n; i++) { long long c, v; cin >> c >> v; s += v; long long w = v - c; int d = a[i]; if (d <= m && w > b[d]) b[d] = w; } for (int i = 1; i <= m; i++) { long long u = b[i] > 0 ? b[i] : 0; long long p = (i - t >= 0) ? f[i - t] : 0; long long q = p + u; f[i] = max(f[i - 1], q); } cout << s - f[m]; return 0; }大学习
【4补】已完成今日这个那你不用补了，刚才那个我是看太长了，所以删了一段，你继续发好了，这回不删了大学习
已完成今日你对细节的追求令我敬佩，不过有些时候，人要学会变通。不是你才掌握真理，不是你掌握一切的。大学习
已完成今日不算有啥大事记吧大学习
3天前 来自 浙江
1您好，您的发言中出现了讽刺、挖苦他人等不当言论。这类言论容易引发争执，破坏社区氛围，已违反平台文明发言规范。请您立即注意言辞，避免再发表攻击性或引战内容。若再次出现类似情况，将给予禁言处理3天。感谢理解和配合，希望您共同维护社区良好氛围。
昨天 来自 浙江
0我好，我的发言中出现了讽刺、挖苦他人等不当言论。这类言论容易引发争执，破坏社区氛围，已违反平台文明发言规范。请我立即注意言辞，避免再发表攻击性或引战内容。若再次出现类似情况，将给予禁言处理3天。感谢理解和配合，希望我共同维护社区良好氛围。
昨天 来自 浙江
0您不好，您的发言中没有出现讽刺、挖苦他人等不当言论。这类言论不容易引发争执，破坏社区氛围，没有违反平台文明发言规范。您不需要立即注意言辞。若再次出现类似情况，将不给予禁言处理3天。感谢理解和配合，希望您共同维护社区良好氛围。
昨天 来自 浙江
0
您好，您的发言中出现了讽刺、挖苦他人等不当言论。这类言论容易引发争执，破坏社区氛围，已违反平台文明发言规范。请您立即注意言辞，避免再发表攻击性或引战内容。若再次出现类似情况，将给予禁言处理3天。感谢理解和配合，希望您共同维护社区良好氛围。
昨天 来自 浙江
0你说得对，但是： 我常常追忆过去。 生命瞬间定格在脑海。我将背后的时间裁剪、折叠、蜷曲，揉捻成天上朵朵白云。 云朵之间亦有分别：积云厚重，而卷云飘渺。生命里震撼的场景掠过我的思绪便一生无法忘怀，而更为普通平常的记忆在时间的冲刷下只留下些许残骸。追忆宛如入梦，太过清楚则无法愉悦自己的幻想，过分模糊却又坠入虚无。只有薄雾间的山水，面纱下的女子，那恰到好处的朦胧，才能满足我对美的苛求。 追忆总在不经意间将我裹进泛黄的纸页里。分别又重聚的朋友，推倒又重建的街道，种种线索协助着我从一个具体的时刻出发沿时间的河逆流而上。曾经的日子无法重来，我只不过是一个过客。但我仍然渴望在每一次追忆之旅中留下闲暇时间，在一个场景前驻足，在岁月的朦胧里瞭望过去的自己，感受尽可能多的甜蜜。美好的时光曾流过我的身体，我便心满意足。 过去已经凝固，我带着回忆向前，只是时常疏于保管，回忆也在改变着各自的形态。这给我的追忆旅程带来些许挑战。 我该在哪里停留？我问我自己。
3天前 来自 浙江
0不是哥们哥们哥们，现在现在现在为了不让你们怀疑怀疑怀疑，还得我还得精心精心精心把这些改的一样一样一样是吧？你看那些大型大型大型的编程比赛比赛比赛，有这种要求吗吗吗吗吗吗？
3天前 来自 浙江
0您好，您的发言中出现了讽刺、挖苦他人等不当言论。这类言论容易引发争执，破坏社区氛围，已违反平台文明发言规范。请您立即注意言辞，避免再发表攻击性或引战内容。若再次出现类似情况，将给予禁言处理3天。感谢理解和配合，希望您共同维护社区良好氛围。
昨天 来自 浙江
0我好，我的发言中出现了讽刺、挖苦他人等不当言论。这类言论容易引发争执，破坏社区氛围，已违反平台文明发言规范。请我立即注意言辞，避免再发表攻击性或引战内容。若再次出现类似情况，将给予禁言处理3天。感谢理解和配合，希望我共同维护社区良好氛围。
昨天 来自 浙江
0
已完成今日：
您在帖子中的评论被帖主删除
大学习和今日：
谢谢夸奖，可以请你gun了
大学习和今日：
请问大佬，代码思路该如何书写？请大佬指导。
大学习和今日：
码风是和你的代码不一样
大学习和今日：
题解格式规范？帅童说不用什么规范，不是luogu
大学习和今日：
不一样吗？你再仔细看看
大学习和今日：
大佬您辛苦了
大学习和今日：
不是哥们，现在为了不让你们怀疑，还得我还得精心把这些改的一样是吧？你看那些大型的编程比赛，有这种要求吗？
大学习和今日：
支持
大学习和今日：
这个那你不用补了，刚才那个我是看太长了，所以删了一段，你继续发好了，这回不删了
大学习和今日：
唉唉唉，别骂人。这样一下就失掉了你的君子风度
大学习和今日：
君子动手不动口
大学习和今日：
90 回复全部评论 3
大学习和今日：
几个月不见，榜上这么高了
大学习和今日：
不算有啥大事记吧
大学习和今日：
你可以单独发帖
大学习。
3天前 来自 浙江
0
有帮助，赞一个