题目大意：交互题，有一个数$a(a\leqslant10^9)$，需要猜出它的值，一次询问为你两个数字$x,y(x,y\in[0,2\times10^9])$：
你最多询问$60$次
题解：$60$，差不多是$2\log_2n$。
令$x=ka+b(k\in\mathbb{N},0\leqslant b<a)$，$2x=(2k+[2b\geqslant a])a+(2b\bmod a)$。若$x\bmod a\geqslant2x\bmod a$，即$b\geqslant (2b\bmod a)$。当$k=0$时，$x<a\leqslant2x$。
这样就有了$a$的一个范围，然后在这个区间内二分，这题似乎我以前的二分写法不可以，需要$a\in[l,r]$时才有二分性，并且$mid\not=l$，不然询问返回都是$x$
卡点：翻译中没有$x,y\in[0,2\times10^9]$，导致我写了个简单一点的二分。发现后各种换二分方法。。。
C++ Code：
#include <cstdio>
char op[20];
int main() {
scanf("%s", op);
while (*op == ‘s‘) {
int l = 0, r = 1;
while (true) {
printf("? %d %d\n", l, r);
fflush(stdout), scanf("%s", op);
if (*op == ‘x‘) break;
l = r, r <<= 1;
}
++l;
if (l != r) {
while (l < r) {
int mid = l + r >> 1;
if (mid == l) ++mid;
printf("%d %d\n", l, r);
printf("? %d %d\n", mid, l);
fflush(stdout), scanf("%s", op);
if (*op == ‘y‘) r = mid;
else l = mid + 1;
}
}
printf("! %d\n", l);
fflush(stdout), scanf("%s", op);
}
return 0;
}
原文：https://www.cnblogs.com/Memory-of-winter/p/10351602.html