题解 CF1290D 【Coffee Varieties (hard version)】
Fuyuki
·
·
题解
Description
有 n 个元素和一个大小为 k 的队列，你每次可以指定一个元素并执行一次查询操作：
$2$、将该元素放到队列末尾，如果队列中元素个数超过 $k$，将队首元素弹出。
额外的，你还可以进行不超过 $30000$ 次的清空队列的操作。
查询操作至多不超过 $\frac{3n^2}{2k}$ 次，并保证 $\frac{3n^2}{2k}\leq 15000$。
你需要求出这 $n$ 个元素去重之后有多少个。
$1\leq k\leq n\leq 1024$，且 $n,k$ 为 $2$ 的整数次幂。
## Solution
$k=1$ 和 $n=k$ 的情况平凡，不做考虑。
对元素去重，对每个值只保留一个元素。如果询问的时候判断该值已经出现，就将该元素去掉（需要保证该元素本身不在队列中，否则可能使得这个值的所有元素都被删去），被去掉的元素不会再次被询问（理由同上）。
将序列对 $\frac{k}{2}$ 分块，每个块内的元素依次询问之后就可以使得每个块内的相同值元素保留最多一个。之后就只需要考虑块之间的相等关系。将一个块对另一个块去重就是依次询问这两个块之间的元素。
直接枚举块需要的询问次数过多，但是可以利用重复的询问，即询问块 $(i,j)$ 和 $(j,k)$ 的话，块 $j$ 就不需要询问两次，下一次可以重复利用上一块已经在队列中的部分。
任意两个块之间都可能存在这样的相等关系，换言之就需要对任意两个无序块之间进行询问操作。
可以将一个块看做一个点，就得到了一张 $\frac{2n}{k}$ 阶完全图，需要处理的块间关系就是所有的边。每次可以在上面选取一条链，花费链上节点个数乘上 $\frac{k}{2}$ 的询问次数并删去链上所有的边。因为查询的时候需要保证查询的元素一定不在队列中，所以一条链是不能出现两个相同节点的。
选取链覆盖完全图可以采用之字形的构造（zig-zag pattern？），枚举起点 $s\in[1,\frac{n}{k}]$，并选取 $s\rightarrow s-1\rightarrow s+1\rightarrow s-2\rightarrow \dots$ 的路径。
这样的话，如果将编号从小到大按顺时针排成一圈，那么对于相差奇数的边会顺时针覆盖到，偶数的话会逆时针覆盖到。每条边会被覆盖到恰好一次。
（P.S. 这个构造方法成立当且仅当节点个数为偶数，但是 $\frac{2n}{k}$ 肯定是偶数）
这样做的询问次数是 $\frac{2n}{k}\times \frac{k}{2}\times \frac{n}{k}=\frac{n^2}{k}$ 满足要求。
```cpp
#include<bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=a;i<=b;i++)
const int N=2048;
int n,m,k,B,ans,d,tag[N];
int ask(int p){
static string tmp;
cout<<"? "<<p<<'\n',cout.flush();
return cin>>tmp,tmp=="Y";
}
int nxt(int x){return (x<=0)-x;}
void query(int p){
FOR(i,p*B+1,(p+1)*B)if(!tag[i]&&ask(i))
tag[i]=1,ans--;
}
int main(){
cin>>n>>k,B=max(1,k/2),m=n/B,ans=n;
FOR(i,0,n/k-1){
if(i)cout<<"R\n",cout.flush(),d=0;
FOR(j,1,m)query((i+d+m)%m),d=(d<=0)-d;
}
cout<<"! "<<ans<<'\n',cout.flush();
return 0;
}
```