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++){
		//如果当前数字出现次数大于1
		if(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;
}
​```