context
A
除了最小的数字每种数字都会占用一次,去重后直接输出 \(2n-1\) 即可。
B
太神秘了,先咕咕咕。
C
发现如果一个区间内存在至少一个长度 \(\ge 2\) 的同色连续段,那么这个连续段可以通过删除两个同色之间的元素来构造新的长度 \(\ge 2\) 同色连续段,否则需要用一次代价为 \(2\) 的操作来找出一段。
并且只有可能选择代价为 \(1\) 或 \(2\) 的操作。
于是判断该区间是否存在长度 \(\ge 2\) 的同色连续段即可。
D
称 \(x\gets \lfloor \frac{x+1}{2}\rfloor\) 为 \(A\) 操作。
首先有一个性质: \(x\) 如果可以写成 \(2^p\),则最多需要 \(\log_2 x\) 次 A 操作变为 \(1\),否则 需要 \(\lfloor\log_2 x\rfloor +1\) 次。
考虑 \(2^p+1\) 的数字,一旦让 \(R\) 将其 \(+1\),则 \(P\) 需要增加一次操作。
于是 \(P\) 与 \(R\) 会在一开始时争夺 \(2^p+1\),并优先操作这些数字。
后面 \(P\) 与 \(R\) 操作只需要两者都跟随对方操作的数字即可。
发现只要 \(R\) 一开始的时候每次抢到一个 \(2^p+1\) 就可以使得操作次数大 \(1\)。
假设一开始 \(2^p+1\) 有 \(x\) 个,将数字 \(a\) 变为 \(1\) 需要 \(c_a\) 次操作 \(A\)。
则答案为 \(\lfloor\frac{x}{2}\rfloor+\sum_i c_{a_i}\)。
E
首先令 \(S=\{1,2,\dots ,n^2+1\}\)。
执行 \(n\) 轮查询 \(S\),并记录 \(B_i\) 表示第 \(i\) 轮查询的返回集合,接着令 \(S\gets S\setminus B_i\)。
若存在一轮 \(|B_i| \ge n+1\) 则直接输出。
否则 \(S\) 中必定有剩余元素。
设 \(f_p\) 表示以下标为 \(p\) 结尾的 LDS 的最大长度。
结论:\(\forall i\le n,j\in B_i,f_j=i\)。
证明考虑归纳:当 \(n=1\) 时,因为此时为整个序列的前缀最大值,故显然成立。
假设 \(n=k-1\) 时成立,当 \(n=k\) 时:
因为 \(j\in B_n\) 在前 \(n-1\) 轮不可见,所以 \(B_{n-1}\) 必定存在一个下标 \(q\) 使得 \(q<j\)。因此 \(f_j\ge f_q+1=n\)。
又因为前 \(n-1\) 个递增子序列必定只能每个子序列选择一个下标,因此 \(f_j\le n\)。
因此 \(f_j=n\)。
根据此结论,直接在 \(B\) 中找一个长 \(n+1\) 的下降子序列是简单的。
void solve() {cin>>n;FOR(i,1,n+1) b[i].clear();set<int>S;FOR(i,1,n*n+1) S.insert(i);FOR(q,1,n) {cout<<"? "<<S.size()<<" ";for(int x:S) cout<<x<<" ";cout<<endl;int k;cin>>k;if(k>=n+1) {set<int>res;while(k--) {int x;cin>>x;if(res.size()<n+1) res.insert(x);}cout<<"! ";for(int x:res) cout<<x<<" ";cout<<endl;return ;} else {while(k--) {int x;cin>>x;b[q].insert(x);S.erase(S.find(x));dp[x]=q;}}}for(int x:S) b[n+1].insert(x),dp[x]=n+1;int nw=n*n+2;set<int>ans;ROF(i,n+1,1) {int x=*prev(b[i].upper_bound(nw));ans.insert(x);nw=x;}cout<<"! ";for(int x:ans) cout<<x<<" ";cout<<endl;
}