题解：CF2159A MAD Interactive Problem

S1lver_W0lf · 2025-10-15 00:37:57 · 题解

题解：CF2159A MAD Interactive Problem

:::info[关于交互题] 每次输出完成之后需要刷新缓存区。为了刷新缓存区并换行，可以直接输出 std::endl。 :::

分析题意

需要我们求得的 a 数组是一个长度为 2n，且 1 \sim n 在数组中严格出现 2 次。
每次提问需要给出提问的下标，然后交互库会返回这些下标的 MAD 值。MAD 值的定义在题面已经给出。
接下来分析这个条件：1 \sim n 在数组中严格出现 2 次。那么我们可以构建两个集合 K 和 U，其中 K 中为对应值确定的下标，U 中为对应值不确定的下标。我们还需要一个答案数组 ans 来存储最终的答案。
最开始，下标 1 一定在集合 U 中。接下来从 2 开始遍历下标 i 直到 2n，每次查询集合 U 中的所有元素和 i。再读取交互库返回的值 x，如果 x \not = 0，则可以得出 ans[i] = x，并将 i 加入到集合 K 中。否则 ans[i] 不确定，并将 i 加入到集合 U 中。易证不会有其他情况。
这一步执行完会提问 2n - 1 次。
接下来，从 1 开始遍历下标 i 直到 2n。如果下标 i 在集合 U 内，此时查询集合 K 中的所有元素和 i，并读取交互库返回的结果 x，则 ans[i] = x。由于在 K 中的元素对应的值不会重复出现，且元素对应的值严格包含 1 \sim n，所以正确性显然。
当第一步执行完时，集合 K 与集合 U 中元素的数量一定都为 n，所以这一步执行完会提问 n 次。
最后一共提问 3n - 1 次，严格小于 3n。

代码

#include <bits/stdc++.h>

using namespace std;

void solve(){
    int n;
    cin >> n;
    vector <int> known, unknown, ans(2 * n + 1);//known 对应集合 K，unknown 对应集合 U
    unknown.emplace_back(1);
    for(int i = 2; i <= 2 * n; i++){
        cout << "? " << unknown.size() + 1 << ' ';
        for(const auto &v : unknown)
            cout << v << ' ';
        cout << i << endl;
        int x;
        cin >> x;
        if(x)
            ans[i] = x, known.emplace_back(i);
        else
            unknown.emplace_back(i);
    }
    for(int i = 1; i <= 2 * n; i++){
        if(!ans[i]){
            cout << "? " << known.size() + 1 << ' ';
            for(const auto &x : known)
                cout << x << ' ';
            cout << i << endl;
            int x;
            cin >> x;
            ans[i] = x;
        }
    }
    cout << "! ";
    for(int i = 1; i <= 2 * n; i++)
        cout << ans[i] << " \n"[i == 2 * n];
}

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