P6960 题解

· · 题解

NOIP 模拟赛 T2。随机化交互好题。

令 a 为原题面中的 e，b 为原题面中的 o。

显然可以使用 \left\lceil\frac{n}{2}\right\rceil 次询问求出 a 中任意其中一个元素的值，全部问一遍 a_i 和 b_j 的大小关系即可。但是这样很浪费。

考虑我们求出了一个 a_i，我们还知道了所有 b_j 和这个 a_i 的大小关系。那么经过这 n 次询问后，b 被分成了两个值域的“块”，我们知道两个块的值域的 [l, r] 和它们包含哪些位置。

那么当我们求每一个 a_i，b 中的一个块会分成两个，除非 n 为偶数且 a_i = n，这种情况特判即可。通过二分我们可以知道 a_i 可能在哪两个块中。二分 check 时和块内任意一个 b_j 比较即可。得到这两个块后，暴力把块中每个元素都比较一遍，就可以把其中一个块分成两个，同时也能知道 a_i 的值。

现在问题是询问次数没有保证。考虑以一个随机的顺序问 a_i，问完 i 个 a 后每个块的期望大小约为 \frac{n}{2i}，暴力问两个块，最坏就是期望问 \frac{n}{i} 次。再加上二分的次数 \sum\limits_{i = 1}^n \log_2i，n = 10000 时期望询问次数约为 1.45 \times 10^5。实际会略大，但是能过。

const int maxn = 10050;

int n, a[maxn], b[maxn], p[maxn];

struct node {
    int l, r;
    vector<int> ps;
};

void solve(int _n) {
    n = _n;
    node u;
    u.l = 1;
    u.r = (n + 1) / 2 * 2 - 1;
    for (int i = 1; i <= (n + 1) / 2; ++i) {
        u.ps.pb(i);
    }
    vector<node> vc;
    vc.pb(u);
    mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
    for (int i = 1; i <= n / 2; ++i) {
        p[i] = i;
    }
    shuffle(p + 1, p + n / 2 + 1, rnd);
    for (int i = 1; i <= n / 2; ++i) {
        int l = 0, r = (int)vc.size() - 1;
        while (r - l + 1 > 2) {
            int mid = (l + r) >> 1;
            if (ask(p[i], vc[mid].ps[0])) {
                l = mid;
            } else {
                r = mid;
            }
        }
        bool flag = 1;
        for (int j = l; j <= r; ++j) {
            vector<int> v1, v2;
            for (int x : vc[j].ps) {
                if (ask(p[i], x)) {
                    v1.pb(x);
                } else {
                    v2.pb(x);
                }
            }
            if (v1.empty() || v2.empty()) {
                continue;
            }
            flag = 0;
            if (j) {
                a[p[i]] = vc[j - 1].r + 1;
            }
            a[p[i]] += (int)v1.size() * 2;
            node u;
            u.l = a[p[i]] + 1;
            u.r = vc[j].r;
            vc[j].r = a[p[i]] - 1;
            vc[j].ps = v1;
            u.ps = v2;
            vc.insert(vc.begin() + j + 1, u);
            break;
        }
        if (flag) {
            a[p[i]] = n;
        }
    }
    for (node u : vc) {
        b[u.ps[0]] = u.l;
    }
    vector<int> v1, v2;
    for (int i = 1; i <= n / 2; ++i) {
        v1.pb(a[i]);
    }
    for (int i = 1; i <= (n + 1) / 2; ++i) {
        v2.pb(b[i]);
    }
    report(v1, v2);
}