ACGO2024新春欢乐赛全题解

CK七星松|再发团队邀请建议趋势

2024-02-18 08:12:39

发布于：浙江

55阅读

0回复

0点赞

ACGO2024新春欢乐赛全题解

T1：

思路：

题目要求通过复制魔法糖果堆可以获得的最多的糖果数量，可以使用优先队列使小的在前，每次使用最小的两个进行操作，直到最小的两个大于 $k$ 为止。

代码：

#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:

思路：

题意是长度为 $n$ 的一块地方，每次能连续打扫 $k$ 个地方，几次可以打扫完，而不是每打扫到已打扫过的地方就得断。

所以这题找规律就行，长度为 $n$ ，每次可以打扫连续的 $k$ 个地方，那么 $\left \lceil n/k \right \rceil$ 就行。

代码：

#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：

思路：

给你两个数，一直把大的减去小的直到其中一个等于 $0$ 为止，注意不能暴力，会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：

思路：

给你一个数列，每次可以选择 $k$ 数排序并移到数列末尾，求最少几次可以使数列变成升序排列的。

这题不用什么复杂的计算。

我们设定一个变量 $cnt$ ，每次判断输入的数是否等于所在的位置就行，不是就把 $cnt$ ++，判断的位置要减去 $cnt$ ，因为前面有 $cnt$ 个数已经被移到末尾了，最后输出 $\left\lceil cnt/k \right\rceil$ 就行。

代码：

#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：

使用优先队列让数字大的在前，每次每次让大的减去小的直到最大的两个相等为止。

最后输出 $n \times q.top()$ （ $q$ 为优先队列名称）就行。

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：

思路：

这题要我们求赶跑年兽的最小需求，因为 $k$ 个以上的年兽可以用 $k$ 个金币~~一窝端~~一次性驱赶，所以可以分类讨论，年兽不小于 $k$ 个用 $k$ 个金币一次性驱赶，否则用 $a_i$ 个金币逐个驱赶。

代码：

#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：

思路：

快乐值总共为 $s$ ，每个糖果最好的情况应该都是 $n \times 2$ ，结果应该是 $s/(n \times 2)$ ，注意因为糖果最多有 $n+1$ 个，最后的结果应该是 $\min (s/(n \times 2),n+1)$ 。

代码：

#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：

思路：

题目要求 $n \times 2$ 个是否可以两两配对并保证每一组的和相加均为奇数。

稍微想一下可以发现以下规律：

$\begin{aligned} c=a+b = \begin{cases} c\And 1==1& a\And 1==1,b\And 1==0 \ \operatorname{or} \ a\And 1==0, b\And 1==1 \\ c\And 1==0 & a\And 1==0,b\And 1==0 \ \operatorname{or} \ a\And 1==1,b\And 1==1 \end{cases} \end{aligned}$

说白了就是奇数与偶数相加为奇数，偶数与偶数或奇数与奇数相加为偶数。

可以得出当输入的数中，偶数与奇数数量相等时，可以保证每一组的和相加均为奇数。

代码：

#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新春欢乐赛全题解就到这里，下次见！

有帮助，赞一个

去预览

0/2000

全部评论 6

小张张五
关于T5，有个更方便的方法。
先考虑只有两个数，那答案便是一直拿小的去减大的，注意到这和辗转相除法是一致的，于是得到两个数的答案便是他们的gcd。n个数同理，求整体gcd即可，时间复杂度nlogV。

2024-02-18 来自天津
1
- CK七星松|再发团队邀请建议趋势
  回复小张张五
  是的，我写复杂了
  
  2024-02-18 来自浙江
  0
lan_chance
orz

2024-02-18 来自广东
0
叫我杨同学
草T5我是O(n^2)

2024-02-18 来自四川
0
叫我杨同学
orz

2024-02-18 来自四川
0
‮队团加不）ด้้童帅_者仇复
古希腊掌管队列的神（bushi）

2024-02-18 来自广东
0
CK七星松|再发团队邀请建议趋势
自顶

2024-02-18 来自浙江
0