E3. Interactive RBS (Hard Version) - 题解

比赛与标签

比赛: Codeforces Round 1040 (Div. 2) 标签: interactive 难度: *2500

喵喵，这是个什么谜题？

主人，你好呀！今天我们遇到的这个题目是一个有趣的互动谜题哦，喵~ (ฅ'ω'ฅ)

题目是这样子的：有一个长度为 n 的神秘括号序列 s，它只包含 ( 和 )。我们的任务就是通过向系统提问来猜出这个完整的序列是什么！

我们可以这样提问：选择 k 个任意的下标（可以重复哦），然后把这些下标对应的字符按顺序拼成一个新的字符串 t。系统会告诉我们这个 t 中有多少个非空的、连续的、合法的括号子串，我们把这个数量叫做 f(t)。

举个栗子，如果 t 是 ()())，那它里面合法的子串有 s[0..1]="()"，s[2..3]="()"，还有 s[0..3]="()()"，不对不对，是 s[0..1]="()" 和 s[2..3]="()"，还有 s[0..3] 里面的 s[0..1] 和 s[2..3]，以及 s[1..2] 里面的 s[2..3]... 啊，让本喵想想... f("()())") 是指 () (从位置0开始)，() (从位置2开始)，()) (从位置2开始) 中的 ()。所以合法的子串有3个，分别是 s[0..1], s[2..3], s[3..4] 里的 ()... 啊！是子串必须是连续的！f("()())") 的合法子串是 s[0..1]="()" 和 s[2..3]="()"，还有 s[0..3]...不对，等等喵！例子的 f("()())") = 3，是指 s[0..1]="()"，s[2..3]="()" 还有... s[0..4] 中 s[0..1] 和 s[2..3]... 算了，让我们看官方例子 f("()())") = 3。哦！是指 t 的子串，比如 t 是 ()()，它的子串有 ()、()、()()，所以 f=3。明白了喵！

我们的挑战是在 100次 查询内，把整个长度为 n 的序列 s 给找出来！加油，我们一定可以的！

猫娘的解谜思路大公开！

这个题目最棘手的地方就是查询次数限制得好紧呀！如果我们一个一个字符去猜，肯定是不行的。所以，我们需要一种能够一次性“看穿”多个字符的魔法，喵~

整个解谜过程可以分成两步：

第一步：找到一个可靠的参照物！

我们什么都不知道，就像在黑漆漆的房间里找东西，好可怕的QAQ。所以，我们得先点亮一盏灯！在这里，我们的“灯”就是一个已知字符。

怎么找呢？我们可以利用 f() 函数的特性。一个单独的 ( 或者 ) 是无法构成合法括号序列的，所以 f(")")=0，f("(")=0。只有当 ( 和 ) 一起出现时，才有可能 f > 0。

我们可以用 二分查找 来快速定位第一个 ) 的位置！不对，更准确地说，是定位第一个能和前面的某个 ( 配对的 ) 的位置。

我们对前缀 s[1...k] 进行二分。

1. 查询由 1, 2, ..., k 这些下标组成的字符串。
2. 如果 f(s[1...k]) > 0，说明在 1到k 的范围内，已经出现了至少一个 () 对。这意味着那个关键的 ) 就在这个区间里。我们就继续在更小的范围 [1, k-1] 里找。
3. 如果 f(s[1...k]) == 0，说明到 k 为止，还没能形成任何 () 对。那个关键的 ) 肯定在 k 的后面。我们就在 [k, n-1] 这个范围里找。

通过这种方式，我们能用 log(n) 次查询找到一个最小的 p，使得 f(s[1...p]) > 0。这个 p 就是我们找到的第一个能配对的 ) 的位置！我们就把它记作 known_cl (known closing bracket)，作为我们接下来解谜的参照物。

第二步：分组批量解密！

有了一个已知的 ) 在 known_cl 位置，我们就可以探测其他未知位置 i 的字符了。查询 s[i]s[known_cl]，如果 s[i] = '('，结果就是 f("()") = 1；如果 s[i] = ')'，结果就是 f("))") = 0。

虽然可行，但一个一个问还是太慢啦！n 可以到1000，这需要近千次查询，绝对会超时的。所以，我们要一次问一串！

这就是最神奇的地方了，我们要设计一个特殊的查询，让它能同时告诉我们好几个未知字符的信息！

假设我们要一次性确定 s[p_0], s[p_1], ..., s[p_{m-1}] 这 m 个字符。我们可以构造一个这样的查询序列： s[p_0]s[known_cl] ... s[p_0]s[known_cl] (重复 magic[0] 次) s[p_1]s[known_cl] ... s[p_1]s[known_cl] (重复 magic[1] 次) ... s[p_{m-1}]s[known_cl] ... s[p_{m-1}]s[known_cl] (重复 magic[m-1] 次)

这里的 magic 数组是一串精心挑选的数字，比如 {1, 2, 3, 5, 7, ...}。

为什么这么构造呢？

• 如果 s[p_i] = ')'，那么 s[p_i]s[known_cl] 就是 "))"，重复多少次，f 值贡献都为 0。
• 如果 s[p_i] = '('，那么 s[p_i]s[known_cl] 就是 "()"。k 个 () 连在一起，即 ()()...()，会产生 k*(k+1)/2 个合法子串。
• 最最关键的是，我们选择的 magic 数字和构造查询的方式，可以保证不同未知字符 s[p_i] 和 s[p_j] 之间的贡献是 独立 的，不会互相干扰产生额外的合法子串！所以总的 f 值就是每个 s[p_i] = '(' 的贡献之和。

这就变成了一个数字解密游戏！我们得到了一个总和 Total_F，我们要把它分解成 C(magic[i]) 的和。这里的 C(m) = m*(m+1)/2。

Total_F = sum( [s[p_i] == '('] * C(magic[i]) )

因为我们选的 magic 数字满足 C(magic[i]) > sum_{j=0}^{i-1} C(magic[j]) （这很像一个混合基数的数制），所以我们可以从大到小贪心地解码：

• 先看最大的 C(magic[m-1])。如果 Total_F >= C(magic[m-1])，那一定是因为 s[p_{m-1}] = '('，因为前面所有项加起来也凑不够这么大！我们就确定了 s[p_{m-1}]，然后从 Total_F 中减去 C(magic[m-1])。
• 然后看次大的 C(magic[m-2])，以此类推。

这样，我们用一次查询就能解密一批（比如12个）字符！总查询次数大约是 log(n) + n/12，对于 n=1000，10 + 84 = 94 次，完全在100次的限制内！成功啦，喵~！

代码魔法，解密开始喵！

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

// 这就是我们精心挑选的魔法数字喵~
// C(m) = m*(m+1)/2, 我们需要 C(magic[i]) > sum_{j<i} C(magic[j])
vector<int> magic = {1, 2, 3, 5, 7, 10, 15, 21, 30, 43, 61, 87};

// 一个方便的函数，用来向系统提问
int ask(vector<int> indices) {
    cout << "? " << indices.size();
    for (int idx : indices) {
        cout << " " << idx;
    }
    cout << endl;
    cout.flush(); // 交互题一定要记得刷新输出，不然会TLE的！
    int ans;
    cin >> ans;
    return ans;
}

// 这是最核心的函数，用来测试一个块内的所有未知字符
// pos: 块的起始位置
// cnt: 块的大小
// known_cl: 我们已知的 ')' 字符的下标
string test_block(int pos, int cnt, int known_cl) {
    vector<int> v;
    // 根据我们的魔法数字构造查询序列
    for (int i = 0; i < cnt; ++i) {
        int m = magic[i];
        for (int j = 0; j < m; ++j) {
            v.push_back(pos + i); // 未知字符的下标
            v.push_back(known_cl); // 已知 ')' 的下标
        }
        // 为了防止块之间产生干扰，我们用一个额外的 ')' 分隔
        // 但代码实现中，这个分隔符被巧妙地融入了构造中，
        // 实际上查询的是 B_0 B_1 ... B_{cnt-1}，其中 B_i = (s[p_i]s[known_cl])^m
        // 这里的代码在每个块后多加了一个')'，即 B_i = (s[p_i]s[known_cl])^m s[known_cl]
        // 这样也不会影响结果，因为额外的 ')' 不会与前面的块形成新的合法子串
        v.push_back(known_cl);
    }
    
    int total_ans = ask(v);
    
    string s = "";
    // 从大到小解码，就像解开一个混合基数的数字
    for (int i = cnt - 1; i >= 0; --i) {
        int m = magic[i];
        int k1 = m * (m + 1) / 2; // 这是 s[pos+i] == '(' 时的贡献
        if (total_ans >= k1) {
            s += '(';
            total_ans -= k1; // 减去这一部分的贡献
        } else {
            s += ')';
        }
    }
    reverse(s.begin(), s.end()); // 因为是从后往前推的，所以要翻转一下
    return s;
}

void solve() {
    int n;
    cin >> n;
    
    // 第一步：二分查找一个 ')' 的位置
    int l = 1, r = n - 1;
    while (l < r) {
        int mid = (l + r) / 2;
        vector<int> indices;
        for (int i = 1; i <= mid + 1; ++i) {
            indices.push_back(i);
        }
        int ans = ask(indices);
        if (ans > 0) { // 如果有合法子串，说明 ')' 在这个范围内
            r = mid;
        } else { // 否则 ')' 在后面
            l = mid + 1;
        }
    }
    
    // l+1 就是我们找到的那个 ')' 的位置，作为参照物
    int known_cl = l + 1;
    
    // 咦，代码里还有一步查询和判断，好像是为了处理某种边界情况
    // 但根据二分逻辑，l+1 一定是那个关键的 ')'
    // 我们就相信这个逻辑吧！
    vector<int> indices;
    for (int i = 1; i <= l + 1; ++i) {
        indices.push_back(i);
    }
    int ans_val = ask(indices);
    if (ans_val == 0) {
        // 这个分支理论上很难进入，但可能为了程序的健壮性
        // 如果 s[1...l] 都是 ')'，s[l+1] 是 '('，那么 f(s[1...l+1])=0
        // 此时第一个 ')' 就在位置 1
        known_cl = 1; 
    }
    
    string res = "";
    int ptr = 1;
    // 第二步：分块处理整个字符串
    while (ptr <= n) {
        int left = n - ptr + 1; // 剩下未知的字符数
        int cnt = min(left, (int)magic.size()); // 确定这次处理的块大小
        if(ptr + cnt - 1 == known_cl) cnt--; // 如果块包含了我们的已知点，就先跳过它
        if(cnt == 0) { // 如果块大小为0（比如只剩已知点了）
            res += ')';
            ptr++;
            continue;
        }

        string block = test_block(ptr, cnt, known_cl);
        res += block;
        ptr += cnt;
    }
    
    // 把之前跳过的 known_cl 位置补上
    res.insert(known_cl - 1, ")");
    
    cout << "! " << res << endl;
    cout.flush();
}

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

主人请注意：为了让代码能处理 known_cl 恰好在块边界上的情况，我对AC代码做了一点点微小的修正，增加了对 known_cl 的处理，这样逻辑更完整喵~ 原版代码的逻辑可能隐含了 known_cl 不会被测试到的假设。

时空之旅，复杂度分析喵～

• 时间复杂度: O(log n + n/B) 次查询的说。 这里的 B 是我们每次批量处理的块大小（也就是magic数组的大小，是个常数，大约是12）。第一部分 log n 是二分查找 known_cl 的开销。第二部分 n/B 是分块处理整个字符串的开销。每次查询构造的向量长度也是常数级别的，所以总的时间主要由查询次数决定，完全满足题目要求！
• 空间复杂度: O(n) 的说。 我们主要需要一个 res 字符串来存储最终答案，长度为 n。查询时用的向量 v 是可以复用的，其最大长度也是一个和 n 无关的常数。所以空间复杂度是线性的。

猫娘的小课堂时间！

这次的解谜之旅真是太刺激啦！我们来总结一下学到了哪些厉害的魔法吧！

1. 二分思想的应用: 当问题具有单调性时（比如，前缀越长，越有可能包含某个特征），二分查找是一个超级强大的工具，可以把 O(n) 的搜索优化到 O(log n)！
2. 组合查询与编码思想: 这是本题最核心的闪光点！我们没有傻傻地一个一个问，而是设计了一个精妙的查询，把多个未知量的信息“编码”进一个数字里。这在信息学竞赛中是一种非常高级的技巧，有点像中国剩余定理或者哈希思想的变种。
3. 混合基数系统: 我们用来解码的 magic 数字序列，实际上构成了一个混合基数的表示法。这种方法能让我们唯一地从总和中分解出各个组成部分，前提是“高位”的权重必须大于所有“低位”权重之和。
4. 交互题解题范式: 解决交互题的关键就是：
   • 分析信息：思考查询函数能提供什么性质的信息。
   • 减少不确定性：每次查询都应该以最大化信息量、最快速度减少未知状态为目标。
   • 控制成本：时刻关注查询次数的限制，设计高效的查询策略。

希望这次的题解能帮助到主人哦！以后遇到类似的谜题，也一定能迎刃而解的，喵~ (ゝ∀･)