ACGO第16次欢乐赛题解
2024-01-15 10:25:43
发布于：浙江
本贴为第16次欢乐赛题解
注者:Yuilice 小张张五
T1 快乐新年
题目大意
给出一个整数，取值范围为,要求根据对应的数字去输出对应的名称。
题意分析
题目描述当中，给出了对应称呼的表格，表格如下。
| 日期 | 称呼 |
|---|---|
| 9 | 除夕 |
| 10 | 初一 |
| 11 | 初二 |
| 12 | 初三 |
| 13 | 初四 |
| 14 | 初五 |
| 15 | 初六 |
| 16 | 初七 |
解题思路
我们只需要使用if语句输出对应内容即可。
时间复杂度解析
只使用到了简单的分支语句，因此时间复杂度为
代码演示
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin >> n;
if(n == 9)cout << "除夕" << endl;
else if(n == 10)cout << "初一" << endl;
else if(n == 11)cout << "初二" << endl;
else if(n == 12)cout << "初三" << endl;
else if(n == 13)cout << "初四" << endl;
else if(n == 14)cout << "初五" << endl;
else if(n == 15)cout << "初六" << endl;
else if(n == 16)cout << "初七" << endl;
return 0;
}
T2 优才生
题目大意
题目共会给出位学生的信息，信息为:姓名、德分、才分。要求你根据给出的德分与才分划分学生的名次。
题意分析
题目描述当中，给出了学生名词排序的优先级顺序，顺序如下
1、 按照德分排序，德分较高者排名靠前。
2、 按照才分排序，才分较高者排名靠前。
3、 如果分数皆相等，最后按照名字的字典序顺序，较小者靠前。
最后根据排名，从上至下输出排名对应的学生姓名即可，需要注意，只有德才分均为60及以上的同学才可输出，每个名字独占一行。
解题思路
本题根据给出的描述，我们可以得知需要按照优先级进行排序，那么我们就可以联想到结构体排序。
根据优先级我们可以编写出一段比较函数的伪代码，其中f与k分别代表德分与才分。
if a.f != b.f
return a.f > b.f
else if a.k != b.k
return a.k > b.k
else
return a.name < b.name
最后只需要在输出的时候根据分数是否都在60分及以上输出名字即可。
时间复杂度解析
需要使用到结构体排序，共有n个元素，所以最后的时间复杂度为
代码演示
#include<bits/stdc++.h>
using namespace std;
struct Node{
string name;
int f,k;
}a[100005];
bool cmp(Node a,Node b)
{
if(a.f!=b.f)return a.f > b.f;
if(a.k!=b.k)return a.k > b.k;
return a.name < b.name;
}
int main()
{
int n;
cin >> n;
for(int i = 1 ; i <= n ; i ++ )
{
cin >> a[i].name >> a[i].f >> a[i].k ;
}
sort(a+1,a+1+n,cmp);
for(int i = 1 ; i <= n ; i ++ )
{
if(a[i].f >= 60 && a[i].k >= 60)cout << a[i].name << endl;
}
return 0;
}
T3 答题卡
题目大意
给定一个的矩阵，矩阵仅由A,B,C,D组成，代表竖着的答题卡。
随后给定一个的矩阵，矩阵仅由+,-,?所组成,代表用横着的答案去比较竖着的答题卡当中，有哪些格子的答案是正确，错误，与不确定的。
现在，假若你将答题卡横过来，求解最多有几个正确的答案与最少有几个正确的答案。
题意分析
我们可以通过题意得知，竖着的答题卡对应横着的答案，也会有几道题目正确，从而得知正确答案矩阵当中的部分信息，再去进行解题即可。
解题思路
题目最终要求的目的为两个 最多以及最少 ，那么我们就要通过枚举的方式求出不确定答案格子的总数与确定答案格子的总数即可。
首先，我们要明确不确定答案格子的定义:
- 原本位置为
?的格子一定为不确定答案 - 竖着答题卡原本错误格子
-所对应的字符，与旋转变为横着答题卡对应格子的字符不相同，也有可能是正确答案，也为不确定答案。
随后确定答案格子定义就比较简单了:
- 竖着的答题卡原本正确
+格子对应的字符与翻转过后横着的答题卡对应位置字符一致，则为正确答案。
最终，我们只需要将不确定答案总数累加上确定答案总数则为最多，只保留确定答案则为最小。
时间复杂度解析
本题使用循环对矩阵进行枚举，时间复杂度为
代码演示
##include<bits/stdc++.h>
using namespace std;
char mp[5005][5005];
char mp2[5005][5005];
char mp3[5005][5005];
int main()
{
int n;
cin >> n;
for(int i = 1; i <= n ; i ++ )
{
for(int j = 1 ; j <= n ; j ++ )
{
cin >> mp[i][j];
mp2[j][i] = mp[i][j];
}
}
int answer = 0 ;
int count = 0 ;
for(int i = 1 ; i <= n ; i ++ )
{
for(int j = 1 ; j <= n ; j ++ )
{
char x;
cin >> x;
if(x == '+' && mp2[i][j] == mp[i][j])
{
answer ++ ;
}else{
if(x == '?')count ++ ;
if(x == '-' && mp[i][j]!=mp2[i][j])count ++;
}
}
}
cout << count + answer << " " << answer << endl;
return 0;
}
T4 解题赛
题目大意
题目给出个题目(题目编号从1开始)第一次解题的得分与后续解题分数，并且给出你能够解题的题目总数，要求你计算出最大可以获取的分数总额。
题意分析
我们需要在次的解题机会当中，选择一个积分最大化的方案执行，最后输出答案即可。
但是在题目当中，我们的方案搭配有很多种，比如选择只做第一个题目，做第一个题目之后只做第二个题目等。
解题思路
根据题目意思，我们可以很快总结出两种大致最值的策略。
- 先做完所有的任务，拿取第一次的奖励之后，再将剩下的机会花在重复解题价值最高的题目当中。
- 找到重复做价值最大的谜题，然后一直做它。
这两种策略的取舍和状态具有很多种，但是我们也将答案锁定在了一个较小的范围当中，那么如何进行解题呢？我们还可以再一次进行优化。
我们不妨可以思考一下，我们可以同时枚举出这两种策略所涉及到的所有方案，然后选取出其中总价值最大的答案即可。
我们可以设定一个变量，来保存第一次做过每一个任务的积分，同时设定一个变量，来保存重复做价值最高的任务。
根据,枚举我们做到第个任务时，剩下的机会全部兑换的积分后，所获得的总积分。
最终，我们从我们枚举的所有总积分当中选取出一个最大值即可。
时间复杂度解析
本题仅使用for循环对数组进行遍历，因此时间复杂度为
代码演示
#include<bits/stdc++.h>
using namespace std;
int arr[200005];
int brr[200005];
void solve()
{
int n,k;
cin >> n >> k;
for(int i = 1 ; i <= n ; i ++ )
{
cin >> arr[i];
}
for(int j = 1; j <= n ; j ++ )
{
cin >> brr[j];
}
int answer ;
int temp;
int max_bi ;
answer = temp = max_bi = 0;
for(int i = 1 ; i <= min(n,k) ; i ++ )
{
temp += arr[i];
max_bi = max(max_bi,brr[i]);
answer = max(answer,temp + (k - i) * max_bi);
}
cout << answer << endl;
}
int main()
{
solve();
return 0;
}
T5 井字棋
题目大意
本题为多组样例测试
给出一个的矩阵，矩阵仅有三个字符.,X,O所组成，代表两个人在的矩阵上下棋的棋局，X为先手,O为后手,.为未下棋地块。以任意方向放满三个棋子为结束的标志。
请你判断给出的的矩阵是否可能会在两者对局当中出现，每组样例给出YES与NO的回答。
题意分析
根据给出的棋盘进行判断是否为合法的棋盘即可。
解题思路
矩阵最大为，我们可以通过枚举所有的情况来判断棋盘是否为合法的。
首先我们需要理清楚，怎样的棋盘为合法的，怎样的棋盘为非合法的。
- X为先手，O为后手，那么在整个合法棋盘当中
X的数量必然大于等于O，并且X下过之后O必然会添上一个，那么在整盘的棋局当中，X的数量只会比O多一个或者相等。 - 任意方向三个格子相同字符为结束，那么在一个合法棋盘当中，不可能出现两个人都获胜的情况。
我们还可以根据第二个条件继续衍生出两种不合法情况。
- 假若
X获得胜利，那么此时X的数量必然不与O相等。 - 假若
O获得胜利，那么此时O的数量必然不可能比X小1个。
整理出以上条件之后，我们只需要判断X与O之间的数量关系，再根据两者的获胜状态判断数量关系即可得出答案。
时间复杂度解析
本题使用循环对矩阵进行枚举，时间复杂度为
代码演示
#include<bits/stdc++.h>
using namespace std;
char mp[5][5];
int col[5][3];
int row[5][3];
void solve()
{
memset(col,0,sizeof col);
memset(row,0,sizeof row);
int cnt1,cnt2;
cnt1 = cnt2 = 0 ;
for(int i = 0 ; i < 3 ; i ++)
{
for(int j = 0 ; j < 3 ; j ++ )
{
cin >> mp[i][j] ;
if(mp[i][j] == 'X'){
cnt1 ++ ;
row[i][0]++;
col[j][0]++;
}
else if(mp[i][j] == 'O'){
cnt2 ++ ;
row[i][1]++;
col[j][1]++;
}
}
}
if(cnt1 - cnt2 > 1 || cnt1 < cnt2)
{
cout << "No" << endl;
return;
}
bool f1,f2;
f1=f2=false;
for(int i = 0 ; i < 3 ; i ++ )
{
if(row[i][0] >= 3)f1=true;
if(col[i][0] >= 3)f1=true;
if(row[i][1] >= 3)f2=true;
if(col[i][1] >= 3)f2=true;
}
if(mp[1][1] == mp[2][2] && mp[1][1] == mp[0][0]){
if(mp[1][1] == 'X')f1=true;
else if(mp[1][1] == 'O')f2 = true;
}
if(mp[0][2] == mp[1][1] && mp[1][1] == mp[2][0]){
if(mp[0][2] == 'O')f2=true;
else if(mp[0][2] == 'X')f1=true;
}
if((f1&&cnt1 == cnt2) || (f2&&cnt1 == cnt2+1))cout << "No" << endl;
else cout << "Yes" << endl;
}
int main()
{
int t;
cin >> t;
while(t--)
{
solve();
}
return 0;
}
T6 挖矿
题目大意
给出件商品的数量与价值，以及背包的体积，求怎样的装载策略可以在不超过背包体积的情况下让拿取物品到达价值最大化。
题意分析
求价值最大化的物品搭配策略，要求数量总额不超过背包体积。
解题思路
根据题目给出的数据范围，每个物品的最大价值，因此此题用背包去求解是固然求不了的。
我们不妨转换下题意，将每种商品视为个价值总额为的商品(不足64个的部分分离出来作为一个商品)，那么此题就可以由背包问题转型为贪心类型的问题。
那么当我们从价值最大往最小的去取时，此时的方案一定是最优的。先从最大到最小去取，当取完完整的个体后，再去考虑剩下不够64个的商品。最后判断取与不取哪种方法最优。
在取值的过程当中，我们可以利用优先队列进行维护不足64个的商品，在进行判断时直接取队首即可。
实现的方法很多，只需要将时间复杂度压缩至即可。
时间复杂度解析
利用优先队列进行维护，时间复杂度为
代码演示
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 55, INF = 1e9, MOD = 1e9 + 7;
int n, w;
long long ans;
struct st {
int s, v;
/*
重载运算符，在排序结构体时以矿物价值为关键字降序排列。
*/
bool operator < (const st &x) const {
return x.v < v;
}
} a[N];
priority_queue<long long> q;
signed main() {
scanf("%d%d", &n, &w);
for (int i = 1; i <= n; i++) scanf("%d", &a[i].s);
for (int i = 1; i <= n; i++) scanf("%d", &a[i].v);
sort(a + 1, a + 1 + n);
for (int i = 1; i <= n; i++) {
/*
如果取堆顶比取当前满格的更优，就取堆中的，直到不优或取完。
*/
while (q.size() && w && q.top() >= 64ll * a[i].v) {
w--;
ans += q.top();
q.pop();
}
/*
取满格。
*/
if (64ll * w <= a[i].s) {
/*
如果取完这次背包就会满，累加完答案后直接退出。
*/
ans += 64ll * w * a[i].v;//因为背包空间不足，取后会满，所以这里统计个数的标准是背包空间。
w = 0;
break;
}
/*
将剩余不足满格的矿物放入堆中，需要直接将总价值计算出来，所有堆中的物品占用空间都是1。
如果正好拿满，但也会将一个空的价值放入堆中，但此时不会导致错误，
因为取空的是一种非常劣的决策，根据我们的贪心策略是会避免掉这个的。
*/
int k = a[i].s / 64 * 64;//k代表这轮我取了多少个当前矿物。
ans += 1ll * k * a[i].v;//因为矿物不够拿，取后背包不会满，所以这里统计个数的标准是满格矿物数量。
a[i].s -= k;
w -= k / 64;
q.push(1ll * a[i].s * a[i].v);
}
/*
拿堆中剩余的直到拿完或背包已满。
*/
while (q.size() && w) {
ans += q.top();
w--;
q.pop();
}
printf("%lld\n", ans);
return 0;
}
有帮助，赞一个