ACGO欢乐赛#39全题解
2025-02-07 14:17:11
发布于：北京
ACGO欢乐赛#39全题解
竞赛链接：ACGO欢乐赛#39
前言
这次欢乐赛的难度较12月的欢乐赛有提升，难度有一定升高，但是与元旦欢乐赛相比难度较低。对于萌新刚刚好。
这次欢乐赛我的表现不好。
想要一个盲盒，求求了。
个人难度：红 红 红 橙 红 橙
题解部分
系好安全带，我们发车啦！
T1：
题目名称：取模运算
时间限制：
空间限制：
题意分析
这道题让我们输出的结果
关键思路
为了防止爆，所以我们可以直接输出。
#include <bits/stdc++.h>
using namespace std;
int main(){
cout << (114514 % 1919810) + (1919810 % 114514);//直接计算结果并输出
return 0;
}
T2:
题目名称：2的若干次方
时间限制：.
空间限制：
题意分析
这道题输入一个正整数，输出
关键思路
可以使用<cmath>头文件中的pow()函数，pow(a,b)可以计算，求可以用pow(2,n)来计算。
#include <bits/stdc++.h>//包含有cmath头文件
using namespace std;
int main(){
int n;
cin >> n;//输入
cout <<(long long )pow(2,n) << endl;//计算2^n并输出
return 0;
}
T3：
题目名称：下棋
时间限制：.
空间限制：
题意分析
这道题让我们求棋盘上有多少颗棋子，规则是这样的：
1.一共，输入次，每次输入，表示棋子下在下棋
2.如果位置已经有棋子，则要将棋下在的位置上
3.若也有棋子，则不执行任何操作
关键思路
这道题我们可以用一个vis数组记录位置是否有棋子，如果为真，则尝试位置，如果也为真，则跳过。如果找到没有棋子的位置，就将这个点标记为true，最后循环遍历vis数组，查找值为true的元素个数
:
#include <bits/stdc++.h>
using namespace std;
int main(){
int ans = 0;//记录答案
int arr[300000] = {};//每个棋子
bool vis[300000] = {};//标记是否有棋子
int n,m;
cin >> n >> m;//输入
for (int i = 1;i <= n;i ++){
cin >> arr[i];//输入棋子位置
if(vis[arr[i]]){//如果位置上已经有棋子
if(vis[arr[i]+1]){//检测下一个位置
continue;//如果也有棋子，则跳过
}else{
vis[arr[i]+1] = true;//标记这个位置
}
}else{
vis[arr[i]] = true;//标记当前位置
}
}
for (int i = 1;i <= m;i ++){
if(vis[i]){
ans ++;//如果有棋子，记录
}
}
cout << ans ;//输出
return 0;
}
T4
题目名称：ABC游戏
时间限制：.
空间限制：
题意分析
这道题输入三个数a,b,c,求每次执行下列两个操作之一，最少几次能让三个数都相等。
操作1：选择两个数将两个数各加1
操作2：选择一个数加2
关键思路
这道题我们可以采用一种策略，要现将整体逼近于最大元素，再增加最小元素使它与其他元素相等，在先将3个数存在数组里，并排序，然后按题意模拟，求出第二大元素和第一大元素的差值，然后将第二大元素和第三大元素连续增加上前面计算好的差值，使用操作一，使第二大元素和最大元素相等，如果第三大元素还小于最大元素，就要使用操作二，有两种情况：
1.第三大元素和最大元素的差值为奇数，这时无法通过操作二直接增加到最大元素，就要将其余两个元素再各加1，这样差值就为偶数了
2.差值为偶数，可以直接将第三大元素增加，三个元素相等，万事大吉
在模拟过程中要使用变量记录操作次数
#include <bits/stdc++.h>
using namespace std;
int main(){
int t;
cin >> t;
while(t --){
int arr[4] = {};
cin >> arr[1] >> arr[2] >> arr[3];//输入a,b,c
sort(arr+1,arr+4,greater<int>());//降序排序
int ans = 0;
ans += arr[1] - max(arr[2],arr[3]);//求出第二大元素比最大元素少多少
arr[2] += ans;//增加（操作一）
arr[3] += ans;
if(arr[3] < arr[1]){//如果最小的元素还比最大元素小
if( (arr[1] - arr[3]) % 2 != 0){//差为奇数由于无法通过操作二凑相等，所以要将其余两个元素再加1
ans ++;
}
ans += ceil((arr[1] - arr[3]) / 2.0);//求出需要执行多少次操作二才能相等
}
cout << ans << endl;//输出
}
return 0;
}
T5
题目名称：看海
时间限制：.
空间限制：
题意分析
这道题输入客栈个数和每座客栈高度，求多少个客栈能看见海
关键思路
我们知道如果这个元素前面，既1-(i-1)这个区间不能有比它高的山，否则这座客栈就看不到海了，所以可以使用最朴素的暴力枚举即可，遍历前面每一座山，比较高度，这道题还好，没有极端的数据，本蒟蒻之前看到数据量达到2e5觉得可能TLE就用O(n)解法然后全WA了
#include <bits/stdc++.h>
using namespace std;
int main(){
int a1[300000] = {};//山的高度
int n;
cin >> n;
for (int i = 1;i <= n;i ++){
cin >> a1[i];//输入
}
int ans = n;//假设所有山都能看到海
for (int i = 2;i <= n;i ++){
for (int j = i - 1;j >= 1;j --){//枚举
if(a1[j] > a1[i]){//如果有山比这座山高
ans --;//排除一种可能
break;
}
}
}
cout << ans;//输出
return 0;
}
T6
题目名称：打牌
时间限制：.
空间限制：
题意分析
这道题输入个测试点，每个测试点有四个数，表示小王和小美的牌。
游戏一共两个回合。在每一回合游戏里，小王和小美都随机选择一张未反转的牌将其翻转，两张牌中数据更大的人能赢下这个回合，且赢的回合数多的人赢得整场游戏，如果赢的回合数一样多，就是平局。
关键思路
根据题意可得，只有在两场小王都赢了的情况下或者一场小王赢了，另一场平局的情况下小王才能赢。
我们可以枚举出6种小王赢了的情况：
1.小王出第1张牌，小美出第1张牌，小王第1张牌大于小美第1张牌，小王出第2张牌，小美出第2张牌，小王第2张牌大于小美第2张牌，小王赢2场，小王胜
2.小王出第1张牌，小美出第1张牌，小王第1张牌等于小美第1张牌，小王出第2张牌，小美出第2张牌，小王第2张牌大于小美第2张牌，小王赢1场，小王胜
3.小王出第1张牌，小美出第1张牌，小王第1张牌大于小美第1张牌，小王出第2张牌，小美出第2张牌，小王第2张牌等于小美第2张牌，小王赢1场，小王胜
4.小王出第1张牌，小美出第2张牌，小王第1张牌大于小美第2张牌，小王出第2张牌，小美出第1张牌，小王第2张牌大于小美第1张牌，小王赢2场，小王胜
5.小王出第1张牌，小美出第2张牌，小王第1张牌等于小美第2张牌，小王出第2张牌，小美出第1张牌，小王第2张牌大于小美第1张牌，小王赢1场，小王胜
6.小王出第1张牌，小美出第2张牌，小王第1张牌大于小美第2张牌，小王出第2张牌，小美出第1张牌，小王第2张牌等于小美第1张牌，小王赢1场，小王胜
由于出牌顺序可以变换，所以每次方案数+2
#include <bits/stdc++.h>
using namespace std;
int main(){
int t;
cin >> t;
while(t --){
int a[5];
cin >> a[1] >> a[2] >> a[3] >> a[4];
int ans = 0;
if(a[1] > a[3] && a[2] == a[4]) ans += 2;//方法1
if(a[1] == a[3] && a[2] > a[4]) ans += 2;//方法2
if(a[1] > a[3] && a[2] > a[4]) ans += 2;//方法3
if(a[1] > a[4] && a[2] == a[3]) ans += 2;//方法4
if(a[1] == a[4] && a[2] > a[3]) ans += 2;//方法5
if(a[1] > a[4] && a[2] > a[3]) ans += 2;//方法6
cout << ans << endl;
}
}
有帮助，赞一个