题目概述

交互题，$n(n\le 10^5)$ 个人接成环，手上拿着一个数 $a_i$ 。$i$ 和 $i\ mod\ n+1$ 相邻，保证相邻人之间的数之差绝对值不超过 $1$ ，而 $i$ 和 $(i+{n\over 2}-1)\ mod\ n+1$ 是对家。你可以询问 $i$ 手上的数是什么，现在要找出一个数字相同的对家，询问次数不能超过 $60$ 次。

解题报告

英语不过关，看翻译被坑飞。这个询问次数不超过 $60$ 次一看就是二分之类的，但是不知道有什么满足二分性。由于相邻人的数之差绝对值不超过 $1$ ，即只有 $\{-1,0,1\}$ 三种情况，所以相邻对家 $(i,i+{n\over 2}),(i+1,i+{n\over 2}+1)$ 之间对家差(对家的数字之间的差)之差只有 $\{-2,0,2\}$ 三种情况。

记 $(i,i+{n\over 2})$ 的对家差为 $b(i)$ ，那么我们现在要找 $b(x)=0$ 的 $x$ ，也就是找零点。由于相邻 $b(i)$ 要么 $-2,+2$ 要么不变（奇偶性不变），于是可以先询问 $b(1)$ ，如果 $b(1)$ 是奇数那么就必定无解，如果 $b(1)=0$ 那么直接得到一个解，否则可以得到 $b({n\over 2}+1)=-b(1)$ ，也就是说 $[2,{n\over 2}]$ 是肯定有解的，直接二分找零点就行了。

示例程序

#include<cstdio>
using namespace std;

int n,L,R;

inline int getnum(int i){
    printf("? %d\n",i);fflush(stdout);
    int x;scanf("%d",&x);
    printf("? %d\n",i+(n>>1));fflush(stdout);
    int y;scanf("%d",&y);return x-y;
}
int main(){
    scanf("%d",&n);L=2;R=n>>1;int A=getnum(1);
    if (!A) return puts("! 1"),fflush(stdout),0;if (A&1) return puts("! -1"),fflush(stdout),0;
    for (int mid=L+(R-L>>1);L<=R;mid=L+(R-L>>1)){
        int now=getnum(mid);if (!now) return printf("! %d\n",mid),0;
        if (A<0&&now>0||A>0&&now<0) R=mid-1; else L=mid+1;
    }return 0;
}