题解：CF1746E1 Joking (Easy Version)

Federico2903 · 2025-03-09 16:42:08 · 题解

思路

考虑怎么应对交互库的说谎，即什么情况一定是确定的：

设现在的答案集合为 S，我们将其四等分为 S_1, S_2, S_3, S_4。

我们询问一次 S_1 \cup S_2，再问一次 S_1 \cup S_3。

考虑对于交互库的每种回答处理，例如回答 NO 和 NO：

注意到交互库在这两个询问中至多只能说一次谎，那么也就是说不存在 YES 和 YES 这种情况，即答案不存在于 (S_1 \cup S_2) \cap (S_1 \cup S_3) = S_1 中。

其他几种情况是类似的，每次都能使集合大小缩小为原来的 \frac{3}{4}。

但是注意到只剩下三个的时候，这个方法失效了，因为存在一种回答方案使排除的集合为空集。

设最后的集合为 \{a, b, c\}，那么我们先询问一次 a。

如果我们得到了否定的回答，则再问一次 \{a\}，如果还是否定的回答，则能确定答案在 \{b, c\} 中。

如果不满足上述情况，那么我们现在一定是最后一次得到了一个交互库对答案在 \{a\} 中的肯定回答，我们再问一次 \{b\}，如果得到了肯定回答，则答案必定不是 c（和上面的思路类似），否则答案必定不是 b。

剩下两个数直接回答就行了。

AC 代码

int query(vector <int> res) {
    cout << "? " << res.size() << " ";
    for (auto v : res) cout << v << " ";
    cout << endl;
    string str;
    cin >> str;
    if (str == "YES") return 1;
    else return 0;
}

void answer(int res) {
    cout << "! " << res << endl;
    string str;
    cin >> str;
    if (str == ":)") exit(0);
}

signed main() {
    cin >> n;
    if (n == 1) answer(1);
    if (n == 2) answer(1), answer(2);
    vector <pii> res;
    rep (i, 1, n) res.emplace_back(i, 0);
    while (res.size() > 3) {
        vector <int> res1, res2;
        rep (i, 0, (int) res.size() - 1) {
            if ((i & 3) == 0) res1.push_back(res[i].ec), res2.push_back(res[i].ec);
            if ((i & 3) == 1) res1.push_back(res[i].ec);
            if ((i & 3) == 2) res2.push_back(res[i].ec);
        }
        int q1 = query(res1), q2 = query(res2);
        if (!q1 && !q2) {
            rep (i, 0, (int) res.size() - 1) {
                if ((i & 3) == 0) res[i].fb = 1;
            }
        }
        if (!q1 && q2) {
            rep (i, 0, (int) res.size() - 1) {
                if ((i & 3) == 1) res[i].fb = 1;
            }
        }
        if (q1 && !q2) {
            rep (i, 0, (int) res.size() - 1) {
                if ((i & 3) == 2) res[i].fb = 1;
            }
        }
        if (q1 && q2) {
            rep (i, 0, (int) res.size() - 1) {
                if ((i & 3) == 3) res[i].fb = 1;
            }
        }
        vector <pii> nxt;
        for (auto [v, st] : res) {
            if (!st) nxt.emplace_back(v, st);
        }
        nxt.swap(res);
    }
    if (res.size() == 3) {
        int Q = query(vector <int>(1, res[0].ec));
        if (!Q) {
            Q = query(vector <int>(1, res[0].ec));
            if (!Q) answer(res[1].ec), answer(res[2].ec);
        }
        Q = query(vector <int>(1, res[1].ec));
        if (Q) answer(res[0].ec), answer(res[1].ec);
        else answer(res[0].ec), answer(res[2].ec);
    }
    else {
        answer(res[0].ec);
        if (res.size() > 1) answer(res[1].ec);
    }
    return 0;
}