题目大意
这是一道交互题
有一个长度为(n)的未知序列(a)和一个大小为(k)的队列(S)。保证(1leqslant kleqslant nleqslant 1024)，且(n,k)都是(2)的次幂。
你可以进行以下两种操作：
-
询问：选择一个数(i(1leqslant ileqslant n))，并输出
? i- 交互程序会先检查(S)中是否包含(a_i)，是则输出
Y，否则输出N - 然后将(a_i)加入队尾，若(|S|>k)，则弹出队首。
- 交互程序会先检查(S)中是否包含(a_i)，是则输出
-
重置：输出
R，交互程序会清空队列。
保证(frac{3n^2}{2k}leqslant 15000)
你需要在不超过(frac{3n^2}{2k})次询问和不超过(30000)次重置之内得出序列(a)中不同数的数量(d)，并输出! d
构造题嘛，那就是乱搞一通的事情做法不唯一。
先说一下具体的想法。
对于每个(iin[1,n])，要确认(a_i)是否在前面出现过，最后前面没出现过的(a_i)的数量就是不同数的数量。
然后就可以开始构造了。
按块长(s=lceilfrac k2 ceil)分块，每次取两块出来询问，然后重置。
然而这样的询问次数是(frac{n^2}s-n)的，并不能通过此题。
ztc的辣鸡构造：
每次取出第一块、中间的某一块、最后一块来询问，之后再取第一块和最后一块来询问，再删掉第一块和最后一块，递归处理，直至删完。
询问次数：设有(a)块时次数为(F(a))，则(F(a)=3s(a-2)+2s+F(a-2)=frac 34a^2s-frac 12as)
代入(as=n)得总次数(large frac{3n^2}{4lceilfrac k2 ceil}-frac n2<frac{3n^2}{2k})
注意特判(n=1)