CF1290D Coffee Varieties (hard version) 题解

题目链接：Coffee Varieties (hard version)

题意：

这是一道交互题。

给定正整数 $n,k~(1 \le k \le n \le 1024)$ ，保证 $n,k$ 是 $2$ 的整数次幂，并且 $\frac{3n^2}{2k}\le 15000$。

有 $n$ 个数 $a_1,a_2,\dots,a_n$ 初始未知，有一队列 $Q$ 初始为空。

每次查询你可以给出一个编号 $x$ ，交互系统会依次进行如下操作：

• 告诉你当前 $Q$ 中是否有与 $a_x$ 相同的数
• 将 $a_x$ 放入 $Q$ 的尾部
• 如果此时 $Q$ 中元素多于 $k$ 个，弹出队首元素

此外，你还可以重置队列，这将使得 $Q$ 中所有元素被弹出。重置队列不算入查询次数。

现请你求出 $a_1,a_2,\dots,a_n$ 中有多少个不同的数。

要求你的查询次数不超过 $\frac{3n^2}{2k}$ ，重置次数不超过 $30000$。

非常有意思的一道题。

首先把序列分成 $\frac{k}{2}$ 个块，这样依次询问每个块后就可以使得每个块内的元素是无重复的。

考虑如何将块合并。注意到对于询问 $(i,j)$ 和 $(j,k)$ ，我们可以利用队列里存在的数从而只询问一次得到答案。

那么如果将这 $\frac{2n}{k}$ 个块看作节点的话，就会得到一个 $\frac{2n}{k}$ 阶完全图。

每次我们可以选择一条链，花费节点个数乘以 $\frac{k}{2}$ 的询问次数删去这条链上的所有边。要求删掉所有的边。

选若干条链覆盖完全图的方法是“之”字形构造，即对于起点 $u \in \left[1, \frac{|V|}{2}\right]$ ，覆盖路径

$$u \to u-1\to u+1\to u-2\to\cdots$$

如下图所示

这种构造在节点总数为偶数时会覆盖每条边恰好一次，不过本题 $|V|=\frac{2n}{k}$ 显然是偶数。

证明考虑将这 $|V|$ 个点顺时针排成一圈，那么相差奇数的边会顺时针覆盖到，相差偶数的会逆时针覆盖到。

这样做的询问次数是 $\frac{2 n}{k} \times \frac{k}{2} \times \frac{n}{k}=\frac{n^2}{k}$ ，显然满足要求。

时间复杂度 $\mathcal{O}(n^2)$

代码：

#include <bits/stdc++.h>
using namespace std;
// #define int long long
// #define INF 0x3f3f3f3f3f3f3f3f
void up(int &x, int y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
#define N ((int)(2333))

int n, k, B, m, d, ans, tag[N];
int ask(int p)
{
    static string tmp;
    cout << "? " << p << '\n'; cout.flush();
    return cin >> tmp, tmp == "Y";
}
void query(int p)
{
    for(int i = p * B + 1; i <= (p + 1) * B; i++)
        if(!tag[i] && ask(i)) { tag[i] = 1, --ans; }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> k; B = max(1, k / 2); m = n / B, ans = n;
    for(int i = 0; i < n / k; i++)
    {
        if(i) { cout << "R\n"; cout.flush(); d = 0; }
        for(int j = 1; j <= m; j++) { query((i + d + m) % m); d = (d <= 0) - d; }
    }
    cout << "! " << ans << '\n'; cout.flush();
    return 0;
}

---

参考文献：

[1] https://www.luogu.com.cn/article/k4wwfwd7