2024.10.14 Codeforces Round 978 (Div. 2)

比赛链接

Solved：4/7

Upsolved：5/7

Rank：447（rated 343）

D2. Asesino（Hard Version）

题意：

有 n 个人，除了一个卧底以外，其他人或者只会说真话，或者只会说谎，且他们知道彼此的身份。卧底只会说谎，但其他人都认为他只会说真话。现在你可以进行若干次询问，每次询问形如问第 i 个人第 j 个人是什么身份。现在要用最少的询问次数找到这个卧底。这里的最少指：你的询问次数不能超过“能保证在给定n的任何情况下都可以找到卧底”的询问次数。

做法：

首先注意到如果a和b都不是卧底，那么问(a,b)和问(b,a)得到的回答应该相同。

所以当n为偶数时，每次问(2k-1,2k)，如果回答不同，那么卧底就在两人之间。这时再随便找一个人（此时其他人都必不是卧底），问(2k-1,x)和(x,2k-1)。若回答仍然不同，则2k-1是卧底；否则2k是卧底。

注意如果问到n-2仍然没问到卧底，那么卧底一定在n-1和n之间，此时不用再浪费两次机会，直接确定n-1是不是卧底即可。总次数为n。

当n为奇数时，如果和偶数一样做，如果问到n-1都没问到，最后会剩一个人，答案就是n-1；如果问到n-3之前就问到了，答案小于n。但唯一问题在于：如果卧底在n-2和n-1之间，那么还需要2次机会来确定卧底，总共将需要n+1次。有什么方法去掉多出来的1次吗？

n=3时，不管怎么试都至少需要4次。

n≥5为奇数时，可以注意到另一个性质：确定三个人都不是卧底只需要三次询问——问(a,b),(b,c),(c,a)，如果这三次询问的异或和为1，那么他们一定都不是卧底。

因此先问 12，23，31 确定卧底是否在 123 中。如果在，那么再问 13 和 21 进一步确定卧底是谁。如果不在，和偶数一样做。剩两个人时直接问 (1,n) 和 (n,1)。这样还是只需要n次。

int n;
int qry(int x,int y){
    cout<<"? "<<x<<' '<<y<<endl;
    int res;
    cin>>res;
    return res;
}
void solve(){
    cin>>n;
    if(n==3){
        int x=qry(1,2),y=qry(2,1);
        if(x==y){cout<<"! "<<3<<endl;return;}
        else{
            int u=qry(1,3),v=qry(3,1);
            if(u==v){cout<<"! "<<2<<endl;return;}
            else{cout<<"! "<<1<<endl;return;}
        }
    }
    if(n&1){
        int u=qry(1,2),v=qry(2,3),w=qry(3,1);
        if(!(u^v^w)){
            int z=qry(1,3);
            if(z!=w){
                int t=qry(2,1);
                if(u==t){cout<<"! "<<3<<endl;return;}
                else{cout<<"! "<<1<<endl;return;}
            }
            else{cout<<"! "<<2<<endl;return;}
        }
        else{
            if(n==5){
                int u=qry(1,4),v=qry(4,1);
                if(u==v){cout<<"! "<<5<<endl;return;}
                else{cout<<"! "<<4<<endl;return;}
            }
            else{
                for(int i=4;i+3<=n;i+=2){
                    int x=qry(i,i+1),y=qry(i+1,i);
                    if(x!=y){
                        int u=qry(i,1),v=qry(1,i);
                        if(u!=v){cout<<"! "<<i<<endl;return;}
                        else{cout<<"! "<<i+1<<endl;return;}
                    }
                }
                int u=qry(1,n),v=qry(n,1);
                if(u==v){cout<<"! "<<n-1<<endl;return;}
                else{cout<<"! "<<n<<endl;return;}
            }
        }
    }
    for(int i=1;i+3<=n;i+=2){
        int x=qry(i,i+1),y=qry(i+1,i);
        if(x!=y){
            int u=qry(i,n),v=qry(n,i);
            if(u!=v){cout<<"! "<<i<<endl;return;}
            else{cout<<"! "<<i+1<<endl;return;}
        }
    }
    int u=qry(1,n),v=qry(n,1);
    if(u!=v){cout<<"! "<<n<<endl;return;}
    else{cout<<"! "<<n-1<<endl;return;}
}

怎么证明小于n一定不能保证呢？