题目

题目概要
对于数列 $a_1,a_2,a_3,\dots,a_n$ ，满足相邻两项的差为一，且最后一项与第一项差为一。

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

数据范围与约定
$n\le 10^5$ 且 $n$ 将于输入中给出。

思路

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

问题为求其零点。

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

不难发现，现在的 $a$ 数列仍然满足 $a_x-a_{x-1}\in\{-1,1\}$ （本质是破环成链，复制了一次）。

此时， $f(x)-f(x-1)=(a_x-a_{x-1})-(a_{x+\frac{n}{2}}-a_{x-1+\frac{n}{2}})$ ，因为两者都是 ${-1,1\}$ 中的一个值，所以

$f(x)-f(x-1)\in\{+2,0,-2\}$

那么，可以看出，如果说将纵轴压缩一下，原本的 $(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 <cstdio>#include <iostream>#include <vector>#include <algorithm>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;}