题解：CF2159A MAD Interactive Problem

关于交互题

每次输出完成之后需要刷新缓存区。为了刷新缓存区并换行，可以直接输出 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

。

代码

CPP

#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();
}

题解：CF2159A MAD Interactive Problem

文章操作