CF 1780-D. Bit Guessing Game_Codeforces Round #846 (Div. 2) D

一道交互题

有一个数字a（1<=a<=1e9），给出它的二进制表示中'1'的数目

最多30次询问，每次询问输出"- x"，之后给出a-x后的二进制表示中'1'的数目，最后以这样的形式"! ans"输出原数字ans

a最大最高位的1是在从右往左的第30位（否则如果从右往左31位为1，那么a>=2^30，即a>=1024*1024*1024，但是a<=1e9）

从右往左依次输出1<<0, 1<<1, 1<<2, ...

设减之前的'1'的位数为cnt1，减之后'1'的位数为cnt2

当输出1<<j时：

　　如果cnt2<cnt1，说明原数字中1<<j这个位置上确实是1，那么ans|=1<<j, cnt1=cnt2, flag=false

　　如果cnt2>=cnt1，说明原数字中1<<j这个位置上是0，比如1000，输出1<<0后，数字变成0111，这个时候进入flag=true模式（cnt1不更改），之后j++，然后输出1<<(j-1)，直到cnt2<cnt1

　　当cnt2<cnt1时，说明多出的1全部都减没了，相当于减去了最开始的1000中的1，此时1<<j的位置就是1000中1所在的位置，所以ans|=1, cnt1=cnt2, flag=false

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 void solve()
 4 {
 5     int cnt, ans=0;
 6     bool flag=false;
 7     scanf("%d", &cnt);
 8     for(int j=0; j<30; j++){
 9         if(cnt>0){
10             if(!flag)
11                 printf("- %d\n", 1<<j), fflush(stdout);
12             else
13                 printf("- %d\n", 1<<(j-1)), fflush(stdout);
14             int cnt2;
15             scanf("%d", &cnt2);
16             if(cnt2<cnt){
17                 ans|=1<<j;
18                 flag=false;
19                 cnt=cnt2;
20             }else{
21                 flag=true;
22             }
23         }
24     }
25     printf("! %d\n", ans);
26     fflush(stdout);
27     //比如1000，第一次减1<<0，会变成0111，cnt2>cnt所以flag=true接下来就一直1<<(j-1)，直到多出来的1减没，这样减去1<<(1-1), 1<<(2-1), 1<<(3-1)后，得到的cnt2=0<cnt1=1，这表明j=3时, 1<<3是原本数字中的位，所以ans|=1<<j，然后flag从true变成false 
28 }
29 int main(void)
30 {
31     int T=1;
32     scanf("%d", &T);
33     while(T--)solve();
34     return 0;
35 }