题解：CF2129C3 Interactive RBS (Hard Version)

LiaoYF · 2025-08-17 22:27:06 · 题解

做法

一个比较劣的做法。

首先可以先二分出来一个右括号，右括号可以用来分割两端，后面有用。具体的二分方法就是，查询原串的一个后缀，找到最后一个不为 0 的后缀，此时一定形如 ())))))...((((，因为为 0 的串一定是 ))))(((( 这种。这样就找到了一个右括号。二分最多花费 10 次询问。于是我们还有 90 次询问，每次询问要得到至少 12 个位置。

然后考虑构造一种方法能查询一个集合中有几个左括号。最简单的构造是 i1))i2))i3))i4))，这样每个位置都互不干扰。有了这个操作如何得出答案呢？考虑放 2^{k-1} 个 i_k，即询问 i1))i2))i2))i3))i3))i3))i3))...，这样可以用一个长度为 3\times(2^k-1) 的询问得到 k 个位置，但是还不够，考虑优化查询的方式。

分割用的右括号其实是多余的，考虑直接查询 i1 i2 i2 i3 i3 i3 i3... 这种，再在最后放 2^k 个右括号。发现查询中一段连续的左括号一定会被之后的第一堆右括号全部消耗掉，且每个左括号恰好贡献 1 次（因为这一堆右括号的数量大于之前括号总数）。这样可以用一个长度为 2^{k+1}-1 的询问得到 k 个位置。每次询问最多得到 8 个位置。

发现我们每次询问的长度只有 511，后面一半都被浪费了。考虑能否构造出更高的一位，即让一个左括号产生大于 255 个正规括号子串，就不会与前面一半重复。发现一个长度为 n 的括号串最多能产生 O(n^2) 个正规括号子串。考虑构造，设 a 是询问的位置，发现可以构造出如下形式：a)a)a)a)...，如果 a 是右括号，显然不会产生任何正规括号子串。如果 a 是左括号，设放了 t 对，会产生 \frac{t(t+1)}{2} 个正规括号子串，只需要 2t 的长度。于是在后面分别放 23、33、47、67 对即可多查询 4 个位置（这几组数保证了单个括号产生的正规括号子串大于之前括号能产生的总和，因此可以知道每个左括号的位置）。这样每次询问可以查询 12 个位置，可以通过本题。

做完之后才发现二进制完全被平方吊打了，其实全部使用平方即可。

代码

#include<bits/stdc++.h>
#define int long long
#define ll long long
#define ull unsigned long long
#define pii pair<ll,ll>
#define fi first
#define se second
#define i128 __int128
#define ALL(x) x.begin(),x.end()
#define popcount(x) __builtin_popcountll(x)
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif
using namespace std;
const int INF=1e18;
const int N=100005;
const int MOD1=1e9+7,MOD2=998244353;
const int MOD=MOD1;
int query(vector<int> vec){
    cout<<"? ";
    cout<<vec.size()<<" ";
    for(auto i:vec){
        cout<<i<<" ";
    }
    cout<<"\n";
    cout.flush();
    int x;
    cin>>x;
    //debug(x);
    return x;
}
int ans[1005];
void solve_(){
    //二分出一个右括号
    int n;
    cin>>n;
    //找到最后一个不为0的位置
    int l=1,r=n,res=0;
    while(l<=r){
        int mid=(l+r)/2;
        vector<int> tmp;
        for(int i=mid;i<=n;i++){
            tmp.push_back(i);
        }
        if(query(tmp)>0){
            res=mid;
            l=mid+1;
        }else{
            r=mid-1;
        }
    }
    int pos=res+1;
    //debug(ANS,pos);
    for(int l=1;l<=n;l+=12){
        int r=min(n,l+11);
        vector<int> tmp;
        for(int i=l;i<=min(r,l+7);i++){
            //前8个
            for(int j=0;j<(1<<(i-l));j++){
                tmp.push_back(i);
            }
        }
        int x=tmp.size()+1;
        for(int i=0;i<x;i++){
            tmp.push_back(pos);
        }

        //后5个：平方
        //23*24/2=276
        if(l+8<=r){
            for(int i=0;i<23;i++){
                tmp.push_back(l+8);
                tmp.push_back(pos);
            }
        }
        tmp.push_back(pos);
        //33*34/2=561
        if(l+9<=r){
            for(int i=0;i<33;i++){
                tmp.push_back(l+9);
                tmp.push_back(pos);
            }
        }
        tmp.push_back(pos);
        //47*48/2=1128
        if(l+10<=r){
            for(int i=0;i<47;i++){
                tmp.push_back(l+10);
                tmp.push_back(pos);
            }
        }
        tmp.push_back(pos);
        //67*68/2=2278
        if(l+11<=r){
            for(int i=0;i<67;i++){
                tmp.push_back(l+11);
                tmp.push_back(pos);
            }
        }
        int res=query(tmp);
        if(res>=2278){
            res-=2278;
            ans[l+11]=0;
        }else{
            ans[l+11]=1;
        }

        if(res>=1128){
            res-=1128;
            ans[l+10]=0;
        }else{
            ans[l+10]=1;
        }
        if(res>=561){
            res-=561;
            ans[l+9]=0;
        }else{
            ans[l+9]=1;
        }

        if(res>=276){
            res-=276;
            ans[l+8]=0;
        }else{
            ans[l+8]=1;
        }

        for(int i=0;i<=7;i++){
            if(l+i<=r){
                if((res>>i)&1){
                    ans[l+i]=0;
                }else{
                    ans[l+i]=1;
                }
            }
        }
    }
    cout<<"! ";
    for(int i=1;i<=n;i++){
        cout<<(ans[i]==0?'(':')');
    }
    cout<<"\n";
    cout.flush();
}
signed main(){
    int testcase,multitest=1;
    if(multitest)cin>>testcase;
    else testcase=1;
    while(testcase--){
        solve_();
    }
    return 0;
}