CF2021
A
题意
给一个长为 \(n\) 的数组 \(a\)，每次可以选择两个元素 \(a_i,a_j\) 删除并加入元素 \(\left\lfloor \frac{a_i+a_j}{2} \right\rfloor\)，最大化最终剩下的元素。
分析
每次操作相当于将一部分数大小减半，贪心地，将值小的放在前面，值大的放在后面，这样可以保证值大的数减半次数较小。
实现可以用优先队列，时间复杂度 \(O(n \log n)\)。
B
题意
给一个长为 \(n\) 的数组 \(a\)，每次可以选择一个 \(a_i\) 将 \(a_i \leftarrow a_i+x\)，问最佳策略下 \(a\) 的 \(\operatorname{MEX}\)。
分析
维护一个桶 \(cnt\)，从小到大遍历 \(cnt\)，发现 \(cnt_i=0\) 则找到了 \(\operatorname{MEX}\)，如果 \(cnt_i > 1\) 则将其中的每个元素都加上 \(x\)，即只留一个，剩下的都往后丢。
时间复杂度 \(O(n)\)。
C1
题意
给长为 \(n\) 的数组 \(a\) 表示成员的位置，长为 \(m\) 的数组 \(b\) 表示希望成员完成任务的顺序，第 \(i\) 轮取出 \(a_1\) 与 \(b_i\) 比较，要求 \(a_1=b_i\)，比较完再把 \(a_i\) 插回 \(a\) 中任意位置，问一组 \(a,b\) 是否合法。
分析
注意到一个 \(b\) 合法当且仅当所有首次出现的数单调递增。
理由：不是首次出现的数总能通过适当地插入构造出合法解。
void solve()
{
int n,m,q; cin>>n>>m>>q;
vector<int> a(n+5),b(m+5);
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=m;i++) cin>>b[i];
vector<int> vis(n+5);
int p=0;
for(int i=1;i<=m;i++)
{
if(vis[b[i]]) continue;
if(a[p+1]==b[i]) p++, vis[a[p]]=1;
else {cout<<"TIDAK"<<endl; return;}
}
cout<<"YA"<<endl;
}