CF1010B Rocket

简要题意

给你一个二分猜数字的模板交互题，但是交互器会 $n$ 周期性地给出错误的答案，你需要在 $60$ 次内猜出范围为 $[1,10^9]$ 的数

思路

说实话应该是大水题，感觉算是水绿

首先模板二分咱们都会，但是它的交互器会抽风......观察到 $\log_2 10^9$ 差不多刚好是 $60$ 的二倍，提示我们要两次询问解决这个问题。

首先想到先总的求一次答案再用第二次询问更正答案，不过貌似不太可行，在不知道“抽风序列”的情况下答案都是无效的，甚至可能是非法的（二分不出来，因为部分正确部分错误），所以我们必须求出“抽风序列”

那么我们先询问 $n$ 次 $1$，显然应该返回 $1$（如果返回 $0$，那么输出答案），否则就是抽风了，记录下来。

小寄巧

这个思路太简单了以至于本题解完泉没有技术含量，就补充一点交互题的小技巧吧。

输入题一般会让你以“某种方式”和交互库交互，你在不同的情况下会询问不同的内容，但是格式是一样的，你可以把它封装成一个函数，如下：

inline int Get(int x){
	cout<<x<<endl;//endl起了flush的效果
	int ret = 0;
	cin>>ret;
	if(ret == 0)exit(0);//防止出现不可预测的情况
	if(ret == -2)exit(0);//题目强调过，这之后流已关闭
	return ret;
}

它的好处有

1. 简单明了，降低代码复杂度和阅读复杂度
2. 方便修改，不会因为修改漏了某个复制的代码导致出错
3. 以上都是封装本身的好处，对于交互题封装，他的另外一个好处是在本地 stdio 交互极其困难的情况下，如果你需要调试，可以把封装的 cin cout 换做自己的交互库。调试完了也方便换回来

所以说还是要有好的代码规范啊。

代码

#include<bits/stdc++.h>
#define Akano 1
#define pure__Elysia 0
#define loves ^
using namespace std;
const int MAXN = 66;
int n,m,cnt;
inline int Get(int x){
	cout<<x<<endl;
	int ret = 0;
	cin>>ret;
	if(ret == 0)exit(0);
	if(ret == -2)exit(0);
	return ret;
}
bool f[MAXN];
int main(){
	cin>>m>>n;
	for(int i = 1;i <= n;i++){
		int res = Get(1);
		if(res == -1){
			f[i] = true;
		}else{
			f[i] = false;
		}
	}
	int l = 1,r = m+1;
	while(l < r){
		const int mid = (l + r) >> 1;
		int res = Get(mid);
		cnt++;
		if(cnt > n)cnt = 1;
		if(f[cnt])res = -res;
		if(res == -1){
			r = mid;
		}else{
			l = mid + 1;
		}
	}
	return not(Akano loves pure__Elysia);
}

励志打完所有交互题