CF1039B Subway Pursuit 做题记录

交互题。

11nn 里有一个运动的点,要求找到这个点,每次可以查询一个区间内有没有这个点,每次这个点往左或者往右移动 11kk 个位置,要求要在 45004500 次查询内找到这个点的位置。

首先可以用二分缩小范围,但是不难发现长度最多只能缩小到 4k4k 左右。

观察到 kk 很小,所以考虑随机化,每次随机问一个位置,若不是就扩大区间,若区间长度超过 4k4k 就重新二分。

由于 4k404k\le 40,询问次数却有 45004500 次,所以找不到答案的概率几乎为 00

代码如下:

#include <iostream>
#include <cstdio>
#include <ctime>
#include <cstdlib>

using namespace std;

long long n;
int k;
char str[15];

inline bool que(long long l,long long r)
{
	printf("%lld %lld\n",l,r);
	fflush(stdout);
	scanf("%s",str);
	return str[0]=='Y';
}

int main()
{
	srand(time(NULL));
	scanf("%lld%d",&n,&k);
	long long l=1,r=n;
	while(l<r)
	{
		if(r-l+1<=k*4)
		{
			long long pos=l+1ll*rand()*rand()%(r-l+1);
			if(que(pos,pos)) break;
			l=max(l-k,1ll),r=min(r+k,n);
		}
		else
		{
			long long mid=l+r>>1;
			if(que(l,mid)) r=min(mid+k,n),l=max(l-k,1ll);
			else r=min(r+k,n),l=max(mid+1-k,1ll);
		}
	}
	que(l,l);
	return 0;
}