CF1543D1 RPD and Rap Sheet (Easy Version)
W00M
·
·
个人记录
CF1543D1 RPD and Rap Sheet (Easy Version)
怎么说呢~
这道题在做的时候,
我莫名的就TLE了,
可能是交互库写挂了...
这道题要求我们求出一个我们不知道且会变的数,
所以我们就需要利用它的性质.
这里它变的方式是异或,
在二进制下,
异或有一个性质,
就是互逆性,
也就是 a\ xor\ a = 0 ,
所以我们就想到每次异或上两个数异或后的结果,
并且使得与上一次异或的结果抵消掉,
这不就很简单了嘛...
我们第一次异或 0 ,
从第二次开始,
第 i 次就异或 (i - 1)\ xor\ (i - 2) ,
然后我们每次都可以把上一次的异或抵消掉并且异或上一个新的数,
这样下去,
当我们异或到第 x 次时,
我们第 $x + 1$ 次询问的正是 $x\ xor\ (x - 1)$ ,
因为我们有 $n$ 次询问机会,
且 $x$ 最大为 $n - 1$ ,
这样我们就能保证在 $n$ 次之内一定得出答案.
code:
```cpp
#include <iostream>
using namespace std;
int main(){
int t, n, k, y, i, ok;
cin >> t;
while (t--){
cin >> n >> k; y = i = ok = 0;
while (!ok){
cout << y << "\n";
i++;
y = i ^ (i - 1);
cout.flush();
cin >> ok;
}
}
return 0;
}
```
好短~