赛后反思
做红温了，太菜了，每题都需要WA几次才能过，B题看到 MEX 选择性害怕，时间复杂度又算错了
A题
每次选择一对 \(a_i,a_j\) 把均值插入数组最后面，要想结果最大，对于两个数求均值，最后的结果一定是小于等于其中的较大值，我们可以考虑如何最大化最后一次操作，想到将最大值保留在最后再使用，这样的答案是最优的，所以我们对数组进行排序，操作 \(n-1\) 次即可
#include <bits/stdc++.h>
#define int long longusing 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 longusing 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 longusing 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;
}
