Codeforces Round 977 (Div. 2, based on COMPFEST 16 - Final Round) A-C1

​
A. Meaning Mean
2024.10.17

算法：模拟，贪心

思路：
居然时没看题解直接做出来的T^T

贪心：题目要求最后剩下的一个数，使得最大

那么我们从这个最大的最后一个数思考，最后一个数肯定时由最后两个数进行相加，再除以2，同时上下取整而得到的。

方便陈述，我们设最大的最后一个数，也就是最终答案设为ans;

设最后进行运算的两个数为 x, y;

则有 ans = （x + y ) / 2;

我们想最后剩下的一个数最大，那么被除数越大好，即（x+y) 越大 ,ans越大

(x + y )中，设x为原数组当中的最后一个（也就是最大的数），

对于y而言，我们无法控制的就按前面元素的平均值来计算即可

C++代码

#include <bits/stdc++.h>
using namespace std;#define int long long
const int N = 60;int T,n,k;
int a[N];void solve() {cin >> n;for(int i = 1; i <= n; i++) {cin >> a[i];}sort(a+1,a+1+n);  //从小到大进行排序for(int i = 1; i < n-1; i++) {a[i+1] = (a[i] + a[i+1]) / 2;}cout << (a[n-1] + a[n]) / 2 << endl;
}
signed main() {ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin >> T;while(T--) {solve();}return 0;
}

B. Maximize Mex
2024.10.17

算法：暴力枚举，排序

思路：
求最大的MEX

MEX需要连续的才行，如 0 ，1， 2 ，3，4 ，因此最后的答案一定是 小于等于 n

如果我们找到了连续区间中有空缺的部分， 这时我们就需要从小于空缺的数中找到多次出现的数字 ，将其加上 k 倍的 x。

对于由很多种情况，因此我们维护 的出现次数即可

C++代码

#include <bits/stdc++.h>
using namespace std;#define int long long
const int N = 2e5 + 10;int T,n,x;void solve(){cin >> n >> x;map<int,int>cnt;  //每个数出现次数map<int,int>add;  //每个数可以加的次数vector<int>a(n+1);for(int i = 1; i <= n; i++){cin >> a[i];cnt[a[i]] ++;} sort(a.begin()+1,a.end());//枚举 0 ~ n for(int i = 0; i <= n; i++){//如果当前数字出现次数大于1if(cnt[i] > 1) add[i % x] += cnt[i] - 1;if(!cnt[i] && add[i % x]) {cnt[i] ++;add[i % x] --;  }} for(int i = 0; i <= n; i++){if(!cnt[i]) {cout << i << endl;return;}}
}
signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin >> T;while(T--){solve();}return 0;
} 

C1. Adjust The Presentation (Easy Version)
算法：暴力枚举

思路：
一开始想了队列，但后来发现根本没必要，想的太复杂了

a[]表示：演示幻灯片的顺序， b[]表示：准备当前幻灯片的成员编号

判断当前要演示的人和准备的人是否是同一个人

由题意我们可以知道，任何一个人只与它第一次出现的位置相关；

因为一个人在之前已经演示完了就可以插入到任何位置；

我们用一个数组vis[ ] 判断当前人出现的情况；

如果当前人是已经演示过了，则跳过；

如果当前人没演示过，但是当前人不是准备这部分幻灯片，那么就是不完美的了

C++代码

#include <bits/stdc++.h>
using namespace std;//#define int long long
const int N = 2e5 + 10;int T,n,m,q;void solve() {cin >> n >> m >> q;map<int,bool>vis;vector<int> a(n + 1);for(int i = 1; i <= n; i++) {cin >> a[i];}vector<int>b(m + 1);for(int i = 1; i <= m; i++) {cin >> b[i];}int j = 1;for(int i = 1; i <= m; i++) {if(vis[b[i]]) continue;   //如果是已经播放完的人则跳过if(a[j] == b[i]) vis[b[i]] = 1 , j++;else {cout << "TIDAK" << endl;return;}}cout << "YA" << endl;
}
signed main() {ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin >> T;while(T--) {solve();}return 0;
}
​```