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