题解：P8135 [ICPC 2020 WF] QC QC

· · 题解

和其他题解不一样，不知道为什么能过的做法。

先考虑假设我们知道一个不故障的机器怎么做，那我们第一轮可以随机询问一个值，这样就能知道他是否故障，假设他不故障下一轮就可以询问两个值，以此类推。

然后我们每一次也可以对其他的做随机询问，这样有可能对后面的递推有帮助。具体的，我们将所有机器分为 3 类，不确定是什么的，确定是故障的，确定是不故障的。

显然第二种是没啥用的，问出来不能有任何帮助，不考虑他们。第一类记为 S 第三类为 T。

我们从 S 中随机取 |T| 个出来询问，在从 S 中随机 |S|-|T| 个和剩下的询问。

然后更新一遍当前新确定的值，注意当前新确定的因为前面几次也对他做了询问，所以他也可以确定出来新的新确定的。

这样实现就是大约 10 次的，不会证，感性理解一下是每次扩展 \frac{|T|}{2} 个新的，因为前面还有记忆化的询问，所以是远大于这个的。

然后考虑怎么询问出一个不故障的机器，考虑给的性质不故障的比故障的多，那我们将所有值两两配对，如果他们互相返回的值中有 0，说明其中至少一个故障的，然后我们将他们都撇了，这样不故障的还是比故障的多！

这样一直撇一直撇最后一定全剩下不故障的，次数大概是，你考虑现在有 x 个不故障的 y 个故障的，那么期望删除 y\frac{x}{x+y} 个故障的，\frac{x}{x+y} 最少是 \frac{1}{2}，所以次数是 \log 的。

这样大概还有几次的空间，我们考虑如果 4 次都没有撇出去任何值，我们询问他们的一个环，如果都是 1 说明里面都是不故障的了。

然后你再去跑刚才的那个做法，因为你前面的询问记忆化了很多，所以实际上跑起来还是差不多 10 次的，足以通过本题（交了 10 遍 7 遍通过）。

::::info[代码]

#include<bits/stdc++.h>
using namespace std;
#define bui __builtin_popcountll
#define pii pair<int,int>
#define se second
#define fi first
#define mid ((l+r)>>1)
#define qwq cout<<"----------------------------------------------------------------------";
const int inf=1e18;
int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
void prt(int x){
    if(x<0)putchar('-'),x=-x;
    if(x<10)putchar(x+'0');
    else prt(x/10),putchar(x%10+'0');
}
int ksm(int x,int y,int mod){
    int ans=1;
    while(y){
        if(y&1ll)ans=ans*x%mod;
        y>>=1;
        x=x*x%mod;
    }
    return ans;
}
const int N=1e2+5;
int gcd(int x,int y){return (y)?gcd(y,x%y):x;}
int max(int x,int y){return (x>y)?x:y;}
int min(int x,int y){return (x<y)?x:y;}
int a[N][N];
int n;
int p[N];
bool vis[N];
char lss[N];
int val[N];
vector<int>query(vector<int>q){
    cout<<"test ";
    for(int i=0;i<q.size();i++)cout<<q[i]+1<<" ";
    cout<<endl;
    scanf("%s",lss+1);
    vector<int>tot;
    for(int i=1;i<=n;i++){
        if(lss[i]=='-')tot.push_back(-1);
        else if(lss[i]=='0')tot.push_back(0);
        else tot.push_back(1);
    }
    return tot;
}
int tot;
void sl(){
    n=read();
    srand(time(0)*114);
    int x=0;
    memset(a,-1,sizeof(a));
    vector<int>q,b,lp,rp,lx,rx;
    q.resize(n);
    int ww=0;
    for(int i=0;i<n;i++)p[i+1]=i;
    tot=n;
    int tm=0;
    while(tot>2){
//          for(int i=1;i<=tot;i++){
//              cout<<p[i]<<" ";
//          }
//          cout<<"\n";
        bool flag=1;
        for(int i=1;i<=tot;i++){
            for(int j=1;j<=tot;j++){
                if(i!=j){
                    if(a[p[i]][p[j]]!=1)flag=0;
                }
            }
        }
        if(flag)break;
        random_shuffle(p+1,p+tot+1);
        memset(vis,0,sizeof(vis));
        for(int i=1;i<=tot;i++)vis[p[i]]=1;
        lp.clear();rp.clear();lx.clear(),rx.clear();
        for(int i=0;i<n;i++){
            if(!vis[i])lx.push_back(i),rx.push_back(i);
        }
        if(tm==4){
            random_shuffle(lx.begin(),lx.end());
            for(int i=0;i<lx.size();i++){
                q[rx[i]]=lx[i];
            }
            for(int i=1;i<=tot;i++){
                q[p[i]]=p[i+1];
                if(i==tot)q[p[i]]=p[1];
            }
            b=query(q);
            for(int i=0;i<n;i++){
                if(q[i]!=-1)a[i][q[i]]=b[i];
            }
            flag=1;
            for(int i=1;i<=tot;i++){
                if(b[p[i]]!=1)flag=0;
            }
            if(flag)break;
            tm++;
            continue;
        }
        for(int i=2;i<=tot;i+=2){
            if(a[p[i]][p[i-1]]==-1)q[p[i]]=p[i-1];
            else lp.push_back(p[i-1]),rp.push_back(p[i]);
            if(a[p[i-1]][p[i]]==-1)q[p[i-1]]=p[i];
            else lp.push_back(p[i]),rp.push_back(p[i-1]);
        }
        if(n%2)lp.push_back(p[tot]),rp.push_back(p[tot]);
        random_shuffle(lp.begin(),lp.end());
        random_shuffle(lx.begin(),lx.end());
        for(int i=0;i<lp.size();i++){
            q[rp[i]]=lp[i];
        }
        for(int i=0;i<lx.size();i++){
            q[rx[i]]=lx[i];
        }
        b=query(q);
//      for(int i=0;i<n;i++){
//          cout<<b[i]<<" ";
//      }
//      cout<<"\n";
        for(int i=0;i<n;i++){
            if(q[i]!=-1)a[i][q[i]]=b[i];
        }
        int ls=0;
        for(int i=2;i<=tot;i+=2){
            if(a[p[i]][p[i-1]]==1&&a[p[i-1]][p[i]]==1){
                p[++ls]=p[i-1];
                p[++ls]=p[i];
            }
        }
        if(n%2)p[++ls]=p[tot];
        if(tot==ls)tm++;
        else tm=0;
        tot=ls;
    }
    x=p[1];
    for(int i=0;i<n;i++)p[i+1]=i;
    memset(val,-1,sizeof(val));
    int cnt=1;
    val[x]=1;
    for(int k=0;k<n;k++){
        bool flag=0;
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(val[i]==1&&a[i][j]!=-1&&val[j]==-1){
                    val[j]=a[i][j];
                    flag=1;
                    cnt++;
                }
            }
        }
        if(!flag)break;
    }
    while(cnt!=n){
        vector<int>su,ed;
        for(int i=0;i<n;i++){
            if(val[i]==1)su.push_back(i);
            if(val[i]==-1)ed.push_back(i);
            q[i]=-1;
        }
        random_shuffle(su.begin(),su.end());
        random_shuffle(ed.begin(),ed.end());
        for(int i=0;i<min(su.size(),ed.size());i++){
            q[su[i]]=ed[i];
        }
        if(su.size()<ed.size()){
            lp.clear(),rp.clear();
            for(int i=su.size();i<ed.size();i++){
                lp.push_back(ed[i]);
            }
            for(int i=0;i<ed.size();i++)rp.push_back(ed[i]);
            random_shuffle(lp.begin(),lp.end());
            random_shuffle(rp.begin(),rp.end());
            for(int i=0;i<lp.size();i++){
                q[rp[i]]=lp[i];
            }
            if(lp.size()!=1){
                for(int i=0;i<lp.size();i++){
                    if(q[rp[i]]==rp[i]){
                        if(i)swap(q[rp[i]],q[rp[i-1]]);
                        else swap(q[rp[i]],q[rp[i+1]]);
                    }
                }
            }
        }
        b=query(q);
        for(int i=0;i<n;i++){
            if(q[i]!=-1){
                a[i][q[i]]=b[i];
            }
        }
        for(int k=0;k<n;k++){
            bool flag=0;
            for(int i=0;i<n;i++){
                for(int j=0;j<n;j++){
                    if(val[i]==1&&a[i][j]!=-1&&val[j]==-1){
                        val[j]=a[i][j];
                        flag=1;
                        cnt++;
                    }
                }
            }
            if(!flag)break;
        }
    }
    cout<<"answer ";
    for(int i=0;i<n;i++)cout<<val[i];
    cout<<endl;
}
signed main(){
    int t=1;
    t=read();
    while(t--)sl();
    return 0;
}
/*
你的变量是否是局部变量？递归之后改掉就不是一个值了？（可持久化）
*/

::::