【CodeForces训练记录】Codeforces Round 977 (Div. 2, based on COMPFEST 16 - Final Round)

赛后反思

做红温了，太菜了，每题都需要WA几次才能过，B题看到 MEX 选择性害怕，时间复杂度又算错了

A题

每次选择一对 \(a_i,a_j\) 把均值插入数组最后面，要想结果最大，对于两个数求均值，最后的结果一定是小于等于其中的较大值，我们可以考虑如何最大化最后一次操作，想到将最大值保留在最后再使用，这样的答案是最优的，所以我们对数组进行排序，操作 \(n-1\) 次即可

#include <bits/stdc++.h>
#define int long long

using namespace std;

void solve(){
	int n; cin>>n;
	vector<int> a;
	for(int i = 0;i<n;i++){
		int x; cin>>x;
		a.push_back(x);
	}
	sort(a.begin(),a.end());
	for(int i = 1;i<n;i++){
		a.push_back((a[0]+a[1])/2);
		a.erase(a.begin());
		a.erase(a.begin());
		sort(a.begin(),a.end());
	}
	cout<<a[0]<<endl;
}

signed main(){
	int T; cin>>T; while(T--)
	solve();
	return 0;
}

B题

求最大的 MEX，我们显然只需要考虑值域小于等于 \(n\) 的 \(a_i\) 即可，因为 MEX 需要 \({0,1,2,3,4,5}\) 这样连续的 \({a_i}\) 才行，所以最后的答案一定是 \(\le n\) 的，接下来就是考虑什么时候该对 \(a_i + x\)，如果我们找到了连续 \(a_i\) 中有空缺的部分，例如 \({2,3,4,6,7}\) 中间少了 \(5\) ，这时我们就需要从 \(\le 5\) 中找到多次出现的数字 \(a_i\)，将其加上 \(k\) 倍的 \(x\)，但是对于有些 \(a_i + kx\) 可能出现不等于这个数的情况，这时我们就要维护 \(a_i \mod x\) 的出现次数，我们循环遍历 \(0 \sim n\) ，同时维护一个 \(i \mod x\) 的值，即数字 \(i\) 的出现次数 \(- 1\)（因为还要保留至少一个 \(i\)，所以是 \(-1\)），发现空缺的部分（即出现次数为 \(0\)）的情况，判断当前 \(i \mod x\) 是否还能加上来，如果不行 MEX 就是 \(i\) 了，可以的话继续遍历下去。

#include <bits/stdc++.h>
#define int long long

using namespace std;

void solve(){
	map<int,int> cnt;
	map<int,int> add;
	int n,x; cin>>n>>x;
	vector<int> a(n + 1);
	for(int i = 1;i<=n;i++) cin>>a[i],cnt[a[i]]++;
	sort(a.begin() + 1,a.end());
	for(int i = 0;i<=n;i++){
		if(cnt[i]>1) add[i%x] += cnt[i]-1;
		if(!cnt[i]&&add[i%x]){
			cnt[i]++;
			add[i%x]--;
			continue;
		}
	}
	for(int i = 0;i<=n;i++){
		if(!cnt[i]){
			cout<<i<<endl;
			break;
		}
	}
}

signed main(){
	int T; cin>>T; while(T--)
	solve();
	return 0;
}

C题

我们发现一旦一个人演示完成后，顺序可以随便改变，所以我们遍历 \({b_i}\) ，如果当前演示的人和要求的匹配的话，就往下，同时标记这个人的顺序可以改变，若出现了之前已经演示过的人就可以直接跳过了。

#include <bits/stdc++.h>
#define int long long

using namespace std;

void solve(){
	int n,m,q; 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 now = 1;
	for(int i = 1;i<=m;i++){
		if(vis[b[i]]) continue;
		if(b[i] == a[now]) vis[a[now]]=1,now++;
		else {
			cout<<"TIDAK"<<endl;
			return;
		}
	}
	cout<<"YA"<<endl;
}

signed main(){
	int T; cin>>T; while(T--)
	solve();
	return 0;
}