题目链接 - https://codeforces.com/contest/1780/problem/D
终端有一个需要猜的数 \(x\)，\(x\leq 10^9\)，每轮终端会给你返回一个数 \(a\) 表示 \(x\) 在二进制下有多少个 \(1\) ，你每次可以选择对终端发出
- b的请求，终端会将 \(x\) 减 \(b\)，并重复上述操作，或者直接给出对原始的 \(x\) 的答案猜测，你需要在 \(30\) 次操作以内猜出 \(x\)
二进制下 \(10^9\) 刚好 \(30\) 位，也就是说我们平均每一次操作要至少确定二进制下的一位，设 \(x = \sum c_i * 2^i\)，从 \(i = 0\) 开始，我们如果减去 \(2^i\) 后，返回值表示 \(1\) 的数量变少了，那么 \(c_i = 1\)，否则 \(c_i = 0\)
注意每一次执行这个操作的时候只能代表当前的 \(x\) 的情况，最后还是要靠这些信息推断原来的 \(x\) 的信息的
代码
#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>
using i64 = long long;
using namespace std;
const int N = 2e6 + 10, inf = 0x3f3f3f3f;
int main() {
int T; std::cin >> T;
while (T--) {
int now, then, ans = 0, t = 0; std::cin >> now;
for (int i = 0; i < 30; i++) {
printf("- %d\n", 1 << i); fflush(stdout);
std::cin >> then;
if (then < now) {ans += 1 << i;}
if (then >= now) {ans += 1 << i + 1; t++;}
now = then; if (then == t || !now) break;
}
printf("! %d\n", ans); fflush(stdout);
}
return 0;
}