题意：交互题。定义 $f(x)$ 为严格大于 $x$ 的最小完全平方数，$g(x)$ 为小于等于 $x$ 的最大完全平方数。你需要猜一个 $\in[1, 10 ^ {12}]$ 中的一个数 $a$，用少于 64 次的询问得到答案，单次你给出 $t(t\in [0, 10 ^ 9])$，会返回 $a + t$ 是否满足 $x - g(x) < f(x) - x$。$T(T\leq 2\times 10 ^ 3)$ 组数据，2s。
首先发现 $[i ^ 2, (i + 1) ^ 2)$ 中恰好有 $i + 1$ 个满足条件的数，$i$ 个不满足条件的数，分界线为 $i(i + 1)$（该数满足）。
然后考虑找到第一个不和 $a$ 性质相同的位置。如何找到呢？注意到我们其实并不知道上界，但是我们有一个关键的性质：如果 $a$ 和 $a + t$ 在同一段，那么 $a + 2t$ 和 $a$ 中间最多只有一个分界线。具体证明可以考虑段长不降的性质。于是我们可以靠这个进行倍增，找到最小的 $b$ 使得 $a + 2 ^ b$ 和 $a + 2 ^ {b + 1}$ 性质不同。这中间显然只有一个分界线，于是我们直接在这个区间进行二分即可。
如果我们找到这个分界线的位置，显然就可以求出 $a$ 了。根据上面的结论，我们可以类似地找到下一个分界线的位置即可，这样就可以询问 $4\log \sqrt a$ 次得到答案，需要 $\approx 80$ 次，还差一点。
注意到我们已经得到了最小的 $b$，也就是说这一段的长度肯定 $> 2 ^ b$，我们没必要又从 1 开始倍增，直接从 $2 ^ b$ 即可。当然也可以使用上一段的长度倍增来寻找这一段的长度，参考代码是这种写法。容易发现这两个都只需要询问 $3\log \sqrt a$ 次，恰好通过。
实现的时候比较繁琐，可以用 5, 7, 16, 30 等几个数据调试，似乎能卡掉大部分 corner case。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
| bool query(int x)
{
if (mp.count(x)) return mp[x];
int t;
std::cout << "? " << x << std::endl, std::cin >> t;
assert(x >= 0 && x <= (int) 1e9);
if (!~t) exit(0);
return mp[x] = t;
}
void work()
{
mp.clear();
bool st = query(0);
int mid, l, r, j1, j2, bit = 0;
if (query(1) ^ st) j1 = 0;
else {
while (query(1 << bit) == st) bit ++;
l = 1 << (bit - 1), r = (1 << bit) - 1;
while (l < r) {
if (query(mid = (l + r + 1) >> 1) ^ st) r = mid - 1;
else l = mid;
}
j1 = l;
}
j1 ++;
bit = 0;
while (query((j1 << bit) + j1) ^ st) bit ++;
l = (bit == 0 ? 0 : (j1 << (bit - 1))) + j1, r = (j1 << bit) + j1 - 1;
while (l < r) {
if (query(mid = (l + r + 1) >> 1) ^ st) l = mid;
else r = mid - 1;
}
j2 = l - j1 + 1;
std::cout << "! ";
if (!st) -- j2, std::cout << (LL) j2 * j2 - j1 << std::endl;
else std::cout << j2 * (j2 + 1LL) - j1 + 1 << std::endl;
}
|