题解：CF2022D2 Asesino (Hard Version)

· · 题解

每次看到这样的题都想仔细研究出题人大脑构造 .jpg

阅读本文前请务必阅读前传。

邪恶出题人没给我们具体限制，那就尽可能的优化一下吧。

不过似乎可以猜测做法必然不会优于 n 次，那么就向 n 优化一下吧。

考验选手人类智慧的时候到了 /fendou

前传中：

if(i!=2){
    if(ask(i,1)!=ask(1,i))return i;
}else if(ask(i,n)!=ask(n,i))return i;
if(i!=2){
    if(ask(i-1,1)!=ask(1,i-1))return i-1;
}else if(ask(i-1,n)!=ask(n,i-1))return i-1;

这里太浪费技术了。

随便就可以改成下面这样吧。

if(i!=2){
    if(ask(i,1)!=ask(1,i))return i;
}else if(ask(i,n)!=ask(n,i))return i;
return i-1;

然后我们发现如果 n 是偶数，一路排查到最后只剩两位时，下面这一句是多余的：

if(ask(i,i-1)!=ask(i-1,i))

单拎出来放后面做掉即可。

于是偶数所需操作次数不超过 n 了。

后面的我都没想到。

如果 n 是奇数，按照前传的做法最坏是 n+1 次询问。

继续优化。

呃呃，可是后面操作不动了啊。

不妨从最前面开始变动。

我们在开头令 1 向 2 询问，2 向 3 询问，3 向 1 询问。

观察题面中的那个表，容易发现如果目标不在这里，那么必然会剩下奇数个「是」作为返回，否则是偶数个。

于是用 3 次排查掉了 3 个位置，否则控制住了目标位置，n 大的时候反而更加有利。

这个真是这道题最难想的部分吧。

后面就简单了，若不在这里，剩下的按照偶数处理即可，一样做到 n 次。

否则这里的 3 个数字，我们根据前面的回答至多再询问 2 次，就可以得到目标。

此时最坏为 5 次，若 n\ge 5 都已经完成。

余下一种情况是 n=3。

但是我就只能用前传中的笨蛋写法做到 4 次啊。

不管了交了。诶怎么过了。

证明是穷举吗，那很好了。那就做完咯。

注意不要用上面处理 n\ge 5 的奇数做法写 n=3，因为最坏是 5 次，单独写一个 4 次的就好。

#include<bits/stdc++.h>
using namespace std;
int ask(int x,int y){
    cout<<"? "<<x<<" "<<y<<endl;
    int flc;
    cin>>flc;
    return flc;
}
int solve(){
    int n;
    cin>>n;
    if(n==3){
        if(ask(1,2)==ask(2,1))return 3;
        if(ask(1,3)==ask(3,1))return 2;
        return 1;
    }
    if(n&1){
        int p=ask(1,2),d=ask(2,3);
        int flc=p+d+ask(3,1);
        if(flc==2||flc==0){
            if(p==ask(2,1))return 3;
            else if(d==ask(3,2))return 1;
            else return 2;
        }
    }
    for(int i=2+(n&1)*3;i+2<=n;i+=2){
        if(ask(i,i-1)!=ask(i-1,i)){
            if(i!=2){
                if(ask(i,1)!=ask(1,i))return i;
            }else if(ask(i,n)!=ask(n,i))return i;
            return i-1;
        }
    }
    return(ask(1,n)!=ask(n,1)?n:n-1);
}
int main(){
    int t;
    cin>>t;
    while(t--){
      int kel=solve();
      cout<<"! "<<kel<<endl;
    }
    return 0;
}
// 苦闷地纠结了好一会儿，路易斯终于下定决心，以做好觉悟的低沉嗓音开口：

//「我明白了。我会负责吸引师父的注意力，同期阁下你就趁那段期间……」
//「好的。」
//「用无咏唱魔术给那臭老头致命一击，送他入土为安吧。」

诶诶？是不是忘了什么？

不过似乎可以猜测做法必然不会优于 n 次，那么就向 n 优化一下吧。

猜的很难有说服力啊，到底为什么最优？就不能用 n-1 次吗？

KDL 写的神秘二分建图方式很具启发性。

每一次操作相当于在两个点间连边，如果只有 n-1 次操作，要么恰好形成一条链，要么至少有一个节点是孤点。

这样其实存在信息的传递，我们将一个环上否的次数加起来，如果不是偶数，那么目标一定在环上。这是 KDL 的发现。

然后容易发现这是环唯一有用的信息了。

注意到链什么信息都给不了，于是不可做。

环呢？

诶诶，你确定了在不在上面又有什么用呢，还是不可做。

所以假完了。

这样就是一个非常不严谨的感性证明，听说官解上面有对于这两种做法的 hack，我有点迷糊造不出来，摆了摆了。

所以大致就说明了操作次数至少是 n。彻底做完了。

Fun fact：

KDL 在补题时发现她写的神秘二分错在建了自环。

已严肃完成今日「我问我自己」大学习。

这是她的 D1 解法，非常新颖欢迎大家前去研究。