ACGO2024新春欢乐赛全题解
2024-02-18 08:12:39
发布于：浙江
ACGO2024新春欢乐赛全题解
T1：
思路：
题目要求通过复制魔法糖果堆可以获得的最多的糖果数量，可以使用优先队列使小的在前，每次使用最小的两个进行操作，直到最小的两个大于 为止。
代码：
#include<bits/stdc++.h>
using namespace std;
int n,f,num,cnt;
priority_queue<int,vector<int>,greater<int> > q;
int main(){
cin>>n>>f;
while(n--) cin>>num,q.push(num);
while(true){
int a,b;
a=q.top(),q.pop(),b=q.top(),q.pop();
if(a+b<=f){
q.push(a);
q.push(a+b);
cnt++;
}
else break;
}
cout<<cnt;
}
T2:
思路：
题意是长度为 的一块地方，每次能连续打扫 个地方，几次可以打扫完，而不是每打扫到已打扫过的地方就得断。
所以这题找规律就行，长度为 ，每次可以打扫连续的 个地方，那么 就行。
代码：
#include<bits/stdc++.h>
using namespace std;
int n,k;
string c;
int main(){
cin>>n>>k>>c;
cout<<((n%k>0)?(n/k+1):(n/k));
}
T3：
思路：
给你两个数，一直把大的减去小的直到其中一个等于 为止，注意不能暴力，会TLE。
每次可以把大的数一次性减到小于原来的小的数为止。
代码：
#include<bits/stdc++.h>
using namespace std;
int a,b,n,cnt;
int main(){
cin>>a>>b;
while(a>0 && b>0){
if(a<b) swap(a,b);
cnt=a/b;
a-=cnt*b;
n+=cnt;
}
cout<<n;
}
T4：
思路：
给你一个数列，每次可以选择 数排序并移到数列末尾，求最少几次可以使数列变成升序排列的。
这题不用什么复杂的计算。
我们设定一个变量 ，每次判断输入的数是否等于所在的位置就行，不是就把 ++，判断的位置要减去 ，因为前面有 个数已经被移到末尾了，最后输出 就行。
代码：
#include<bits/stdc++.h>
using namespace std;
int n,k,cnt,num;
int main(){
cin>>n>>k;
for(int i=0;i<n;i++){
cin>>num;
if(num!=i+1-cnt) cnt++;
}
cout<<(cnt%k>0?cnt/k+1:cnt/k);
}
T5：
思路：
40pts：
使用优先队列让数字大的在前，每次每次让大的减去小的直到最大的两个相等为止。
最后输出 （ 为优先队列名称）就行。
100pts：
直接判断最大的两个数字是否相等可能会存在无法考虑的情况，如
4
2 2 3 3
可以写个函数判断队列内所有元素是否相等，全部相等返回-1，否则返回不相等的位置，然后在进行题目要求的操作就行。
输出同40pts的输出。
代码：
40pts：
#include<bits/stdc++.h>
using namespace std;
int n,num,cnt;
priority_queue <int,vector<int>,less<int> > q;
int main(){
cin>>n;
for(int i=0;i<n;i++) cin>>num,q.push(num);
while(true){
int a,b;
a=q.top(),q.pop(),b=q.top(),q.pop();
if(a==b){
cnt=a;
break;
}else{
q.push(a-b);
q.push(b);
}
}
cout<<cnt*n;
}
100pts：
#include<bits/stdc++.h>
using namespace std;
int n,num,cnt;
priority_queue <int,vector<int>,less<int> > q;
int f(priority_queue<int, vector<int>,less<int> >& q){
vector<int> v,v2;
int size=q.size();
while(!q.empty()){
int top=q.top();
v.push_back(top),v2.push_back(top),q.pop();
}
for(int i=0;i<size;i++){
q.push(v[i]);
}
auto it=unique(v.begin(),v.end());
if(it-v.begin()==1) return -1;
else{
size=q.size();
for(int i=0;i<size;i++){
if(v2[i]!=v2[i+1]) return i;
}
}
}
int main(){
cin>>n;
for(int i=0;i<n;i++) cin>>num,q.push(num);
while(true){
int idxx=f(q);
if(idxx==-1){
cnt=q.top();
break;
}else{
int m=q.top();
for(int i=0;i<idxx;i++) q.pop();
int a,b;
a=q.top(),q.pop(),b=q.top(),q.pop();
q.push(a-b);
q.push(b);
for(int i=0;i<idxx;i++) q.push(m);
}
}
cout<<cnt*n;
}
T6：
思路：
这题就像是给你一排长短不齐大葱，问你怎么切使所有大葱一样长且切的部分最少，那必然是往短的切。
我们可以输入时更新所有数中的最小数，然后再遍历一遍所有数，把每个数和最小数的差加起来，最后输出。
代码：
#include<bits/stdc++.h>
using namespace std;
long long n,min_=1000005,nums[55],cnt;
int main(){
cin>>n;
for(int i=0;i<n;i++) cin>>nums[i],min_=min(min_,nums[i]);
for(int i=0;i<n;i++) cnt+=(nums[i]-min_);
cout<<cnt;
}
T7：
思路：
这题要我们求赶跑年兽的最小需求，因为 个以上的年兽可以用 个金币一窝端一次性驱赶，所以可以分类讨论，年兽不小于 个用 个金币一次性驱赶，否则用 个金币逐个驱赶。
代码：
#include<bits/stdc++.h>
using namespace std;
int n,k,cnt,num;
int main(){
cin>>n>>k;
while(n--){
cin>>num;
if(num>=k) cnt+=k;
else cnt+=num;
}
cout<<cnt;
}
T8：
思路：
求输入最早的仅出现一次的数。
每次输入时把对应的标记数组的数增加，如果数为1则为第一次出现，标记出现的位置。
再遍历一遍输出出现最早的仅出现一次的数即可。
代码：
#include<bits/stdc++.h>
using namespace std;
int n,num,nums[10005][2],first,second=114514;
int main(){
cin>>n;
for(int i=0;i<n;i++){
cin>>num,nums[num][0]++;
if(nums[num][0]==1) nums[num][1]=i;
}
for(int i=1;i<=10000;i++){
if(nums[i][0]==1){
if(nums[i][1]<second) first=i,second=nums[num][1];
}
}
cout<<first;
}
T9：
思路：
快乐值总共为 ，每个糖果最好的情况应该都是 ，结果应该是 ，注意因为糖果最多有 个，最后的结果应该是 。
代码：
#include<bits/stdc++.h>
using namespace std;
long long n,s;
int main(){
cin>>n>>s;
n*=2;
cout<<min((s/n),n/2+1);
}
T10：
思路：
题目要求 个是否可以两两配对并保证每一组的和相加均为奇数。
稍微想一下可以发现以下规律：
说白了就是奇数与偶数相加为奇数，偶数与偶数或奇数与奇数相加为偶数。
可以得出当输入的数中，偶数与奇数数量相等时，可以保证每一组的和相加均为奇数。
代码：
#include<bits/stdc++.h>
using namespace std;
int n,num,a,b;
int main(){
cin>>n;
for(int i=0;i<n*2;i++){
cin>>num;
if(num&1) a++;
else b++;
}
cout<<(a==b?"YES":"NO");
}
我的思路不一定是最优最正确的解法，只是希望让帮助各位更好的理解题意，部分的题解可能是题目的数据不够毒瘤强度不大，只是碰巧过了。
好了，ACGO2024新春欢乐赛全题解就到这里，下次见！
全部评论 6
关于T5，有个更方便的方法。
先考虑只有两个数，那答案便是一直拿小的去减大的，注意到这和辗转相除法是一致的，于是得到两个数的答案便是他们的gcd。n个数同理，求整体gcd即可，时间复杂度nlogV。2024-02-18 来自 天津
1
有帮助，赞一个