Codeforces Round 1040 (Div. 2) E1 - E3 交互题 | 思维

赛时连E1都没有开出来，一直在坐牢…赛后研究了下jiangly的代码，觉得很巧妙，遂写一篇博客，来帮助大家理解。

思路：

首先我们要有一个认识，Hard version中要求我们在 $100$ 次查询内确定一个串的每个字符组成，这就使得我们每次最少要查询 $10$ 个字符，才能保证在规定的次数中确定唯一字符串。

第二点，关于 f(s) 的性质：f(“()()”) 和 f(“()())”) 的值一样吗？… 当然是一样的，都是 3.

而且我们还可以发现，当一个括号串一直保持 “()()()()…” 重复的时候，此时只要再插入一个单一的 “)”，无论再后面接什么，这两部分 （“)” 的左右部分） 的贡献一定会被拆开。

eg：“()()()())()()” 中，左边 “()()()()” 和右边 “()()” 的贡献是分开的。

所以这启发我们可以通过状态压缩的方式来一次性多次查询一个字符串中的多个字符。

也就是说，我们查询的时候会返回一个值，表示我们询问子串中f(s)的大小，这个值化为二进制后有至少有十位，每一位都代表着我们查询的这十几位子串中每一个括号的状态 （“)” or “(”）。

而我们刚才又知道我们可以通过 “()()()…)…()()” 这样的构造方式去做分割，保证每一部分的贡献不会受到其他部分的影响。

接下来我们要思考，如何状压？

我们可以发现，对于这样一个串 “()()()()()…()()()”（共 a 组 “()”） 能产生的总贡献刚好等于 $\frac{a(a+1)}{2}$ ；

我们就可以用若干个 “$\frac{a(a+1)}{2}$” （上文已经说明，可以用单一括号分割，使得各个部分独立），来凑出 $2^i$ 来进行状态压缩。

这也就是一个常见的用三角数来完成的贪心构造了：

构造一串 $T[i]$，让 $f(T[i])=2^i$。

1. 设 $need=2^i$。
2. 从最大的 $a$ （代码里枚举到 100）往下，寻找最大的满足
   $$\frac{a(a+1)}{2}\le \text{need}$$
3. 一旦找到了，就把那段长度为 $2a+1$ 的 “()()…())” 串拼进去，做 $\text{need}-=\frac{a(a+1)}{2}$。
4. 直到 $need$ 减为 $0$。

这样得到的 $T[i]$ 就是几段三角数串拼接——每段尾部用额外的 “)” 断开，保证互不干涉——总合法子串数正好是所有这些三角数的和，也就是 $2^i$。

设 $i=5$，那么我们要凑出 $2^5=32$。
最大的三角数 $\frac{a(a+1)}{2}\le 32$ 是 $a=7$，因为 $\frac{7\cdot 8}{2}=28$。

拼入 “()()()()()()()())”（7 组 () 再一个 )），$need$ 剩下 $32-28=4$。
接着找 $\frac{a(a+1)}{2}\le 4$ 的最大 $a$：是 $a=2$，$\frac{2\cdot 3}{2}=3$。

拼入 “()()())”，$need$ 变成 $4-3=1$。
最后凑 $1$，就是 $\frac{1\cdot 2}{2}=1$ 对应 $a=1$，拼入 “())”，$need=0$。

合并起来：

T[5] = ()()()()()()()())  ()()())  ()) 
         ↑28个子串      ↑3个子串   ↑1个子串 

尾部每个多余的 “）” 保证段与段之间不串联配对，总共正好贡献 $28+3+1=32$。

而且为什么最后代码中我们呈现出来的状压不是 10，而是 12 呢？是因为我们还要有一些别的步骤去二分，二分出来一个 “)”，这样才能帮助我们构造查询数组。

而且二分的时候还得注意到底是什么情况，如果越界了，证明只有一个 “)” 而且在这个字符串的第一个；不然至少会存在一个长度为2的合法子串，也就不可能越界了。

最后当我们打算验证某一位字符是否是 “(” 的时候，我们只需要看查询返回结果中，二进制状态下这一位数字是否为1即可。

（感觉我叙述的好烂，大家看代码理解吧）

#include<bits/stdc++.h>

using namespace std;
#define int long long
#define debug(x) cerr << #x" = " << x << '\n';

vector<string> T(12);
void init() {
    for (int i = 0; i < 12; i++) {
        int m = 1 << i;
        string s;
        for (int a = 100; a >= 1; a--) {
            while (a * (a + 1) / 2 <= m) {
                m -= (a + 1) * a / 2;
                for (int j = 0; j < a; j++) s += "()";
                s += ')';
            }
        }
        T[i] = s;
    }
}

int query(vector<int> a) {
    cout << "? " << a.size();
    for (auto x : a) {
        cout << ' ' << x;
    }
    cout << endl;
    int ans;
    cin >> ans;
    return ans;
}

void solve()
{
    int n;
    cin >> n;
    string ans(n + 1, '?');

    int l = 1, r = n;
    auto check = [&](int mid) -> bool {
        vector<int> tem;
        for (int i = 0; i <= mid; i++) {
            tem.push_back((i % n) + 1);
        }
        return query(tem) > 0;
    };
    
    while (l < r) {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    int ri = l % n + 1;

    for (int i = 1; i <= n; i += 12) {
        vector<int> a;
        for (int j = i; j <= min(n, i + 11); j++) {
            auto s = T[j - i];
            for (auto c : s) {
                if (c == '(') a.push_back(j);
                else a.push_back(ri);
            }
        }
        int res = query(a);
        for (int j = i; j <= min(n, i + 11); j++) {
            if (res >> (j - i) & 1) ans[j] = '(';
            else ans[j] = ')';
        }
    }

    cout << "! " << ans.substr(1) << endl;
}

signed main()
{
    cin.tie(nullptr) -> ios::sync_with_stdio(false);

    init();
    int T = 1;
    cin >> T;
    while (T --) solve();
    return 0;
}