P8135 [ICPC2020 WF] QC QC

· · 题解

P8135 [ICPC2020 WF] QC QC

两种人，1 或 0。1 只说真话，0 对于询问相同的人的状态的回答相同。进行不超过 12 轮询问，每轮询问形如向第 i 个人问第 p_i 个人的状态。需保证 p_i 互不相同且 i \neq p_i。已知 1 的人数严格大于 0 的人数，试确定每个人的状态。

高妙构造题。

首先，我们只能从回答的结果反推出每个人的状态，且一定是让两个人相互询问。若不相互询问，我们难以确定任何一个人的状态，因此导致获得的信息完全无用。

考虑两个 1 相互询问，回答必然是 1, 1。1, 0 相互询问，回答 至少有一个 0。两个 0 相互询问，回答可能是任何结果。容易发现若回答为 1, 1，则两个人的状态必然相同。

根据上述结论，我们考虑将所有人划分为若干 等价类，每个等价类内部所有人的状态均相同。一开始，每个人都是一个等价类。称为 一型等价类。

接下来，将所有一型等价类两两配对并互相询问。若询问结果不是 1, 1，说明它们当中必然 至少有一个 0。将这些 大小相同 的 等价类对 两两丢到一边，称为 二型等价类。

每次配对的过程中，可能有单独的一型等价类剩余。丢到一边，称为 三型等价类。

考虑配对的最终结果。显然，若一型等价类个数 \geq 2，则还可以继续配对。若一型等价类个数等于 1，则看做三型等价类。

因此，最终不剩余任何一型等价类。根据上述三条性质，容易发现必然存在三型等价类，且最大的的三型等价类必然为 1。若不然，根据小于 2 ^ K 的不同的 2 的幂之和最大为 2 ^ K - 1 这一事实，与性质 3 矛盾。

现在我们用较少的步数确定了至少一个 1。只需要用这个 1 去 倍增 确定所有二型等价类的类型即可。倍增的思想体现为每确定一个等价类的类型，若该等价类为 1，则每次能够确定的等价类的类型会增加该等价类的数量。

除非运气特别差，12 次询问足以确定所有人的状态，因为最差结果是问出来的结果都是二型等价类，唯一的三型等价类大小为 1，且一开始用三型等价类问二型等价类的状态，得到的结果全是 0。这种情况在加入适当随机化之后出现概率可以视为 0。

#include <bits/stdc++.h>
using namespace std;

#define vint vector <int>
#define pb push_back

string query(vint p) {
    string res;
    cout << "test ";
    for(int it : p) cout << it << " ";
    cout << endl, cin >> res;
    return res;
}

const int N = 100 + 5;
int n;
vector <int> id[N], t1, t2, t3, fix;

void merge(vint &x, vint y) {for(int it : y) x.push_back(it);}
void solve() {
    cin >> n, t1.clear(), t2.clear(), t3.clear(), fix.clear();
    for(int i = 1; i <= n; i++) id[i].clear(), id[i].pb(i), t1.pb(i);
    while(t1.size()) {
        vector <int> p(n), nt1;
        for(int i = 0; i + 1 < t1.size(); i += 2) p[t1[i] - 1] = t1[i + 1], p[t1[i + 1] - 1] = t1[i];
        if(t1.size() & 1) t3.pb(t1.back());
        string res = query(p);
        for(int i = 0; i + 1 < t1.size(); i += 2) {
            int x = t1[i], y = t1[i + 1];
            if(res[x - 1] == '1' && res[y - 1] == '1') merge(id[x], id[y]), nt1.pb(x);
            else t2.pb(x), t2.pb(y);
        } t1 = nt1;
    }

    int bk = t3.back(), cur = 0;
    merge(fix, id[bk]), t3.pop_back();
    vector <int> p(n);
    for(int it : t3) p[id[bk][cur++] - 1] = it;
    string res = query(p); cur = 0;
    for(int it : t3) if(res[id[bk][cur++] - 1] == '1') merge(fix, id[it]);

    while(t2.size()) {
        int lim = min(fix.size(), t2.size());
        vector <int> p(n), nfix = fix;
        for(int i = 0; i < lim; i++) p[fix[i] - 1] = t2.back(), t2.pop_back();
        string res = query(p);
        for(int i = 0; i < lim; i++) if(res[fix[i] - 1] == '1') merge(nfix, id[p[fix[i] - 1]]);
        fix = nfix;
    }

    string ans;
    for(int i = 0; i < n; i++) ans += '0';
    for(int it : fix) ans[it - 1] = '1';
    cout << "answer " << ans << endl;
}

int main() {
    int T; cin >> T;
    while(T--) solve();
}

优化：注意到当且仅当最后一次合并时，将偶数个大小为 2 ^ K 的一型等价类两两（组成一对）丢到二型等价类时，最大三型等价类较小，不大于 2 ^ {K - 1}，且三型等价类大小总和小于 2 ^ K。但注意到此时对于所有最大的二型等价类 对 x, y，必然恰有一个为 1，恰有一个为 0。因为若两个都为 0，则可以推出 1 的个数不大于 0 的个数，与题意矛盾。这样一来，每次我们必然能成功获得一个较大的为 1 的等价类，优化显著。

一个乱搞方法（来源于 LOJ 第一篇提交）：考虑每次将两个等价类合并。对于所有不同的等价类对 (x, y)，按 \max(sz_x, sz_y) 从大到小排序，并优先选择能操作的等价类对询问。在不超过 8 次询问内能得到答案，此时大小最大的等价类即为 1，其它等价类均为 0（若为 1 就被最大等价类合并了）。

启示：构造题当中 2 的幂一般很有性质。