本文共 2160 字，大约阅读时间需要 7 分钟。

题目

题目概要

任求一个 $x$ 使得 $a_x=a_{x+\frac{n}{2}}$ 。你有 $60$ 次机会询问 $a$ 数列中某一项的值。

数据范围与约定

思路

我们因地制宜，令 $$f(x)=a_x-a_{x+\frac{n}{2}}$$

问题为求其零点。

不妨令 $a_x=a_{x-n}(n<x)$ ，即将 $a$ 数列重复无数次。

不难发现，现在的 $a$ 数列仍然满足 $a_x-a_{x-1}\in \{$

此时， $f(x)-f(x-1)=(a_x-a_{x-1})-(a_{x+\frac{n}{2}}-a_{x-1+\frac{n}{2}})$ ，因为两者都是 $\{$

$$f(x)-f(x-1)\in \{$$

那么，可以看出，如果说将纵轴压缩一下，原本的 $(x,y)$ 压缩到 $(x,\frac{y}{2})$ ，那么 $f(x)$ 是“连续”的。

由定义，我们还发现 $$f(1)+f\left(\frac{n}{2}+1\right)=0$$

也就是说，$f(1)$ 和 $f(\frac{n}{2}+1)$ 异号。

异号，且连续，求零点，众所周知，用 二分法即可。

代码

#include 
   
    #include 
    
     #include 
     
      #include 
      
       using namespace std;inline int readint(){   	int a = 0; char c = getchar(), f = 1;	for(; c<'0' or c>'9'; c=getchar())		if(c == '-') f = -f;	for(; '0'<=c and c<='9'; c=getchar())		a = (a<<3)+(a<<1)+(c^48);	return a*f;}inline void writeint(int x){   	if(x > 9) writeint(x/10);	putchar((x%10)^48);}# define MB template < class T >MB void getMax(T &a,const T &b){    if(a < b) a = b; }MB void getMin(T &a,const T &b){    if(b < a) a = b; }int query(int x){   	printf("? %d\n",x);	fflush(stdout);	return readint();}# define f(x) (query(x)-query(x+(n>>1)))# define guess(x) { printf("! %d\n",x); return 0; }int main(){   	int n = readint(); // 难得的没有压行	int l = 1, lval = f(l), r = (n>>1), rval = f(r);	if(lval%2 != 0) guess(-1); // impossible	if(lval == 0) guess(l); if(rval == 0) guess(r);	while(true){    // 范围是(l,r)		int mid = (l+r)>>1, d = f(mid); if(d == 0) guess(mid);		if((d > 0) != (lval > 0)) r = mid; else l = mid;	} // 一定会运行一次GUESS的	return 0;}