思路
虽然咱很喜欢随机化，但是没想到这题也能随机化啊（）。其实稍微想想容易清楚就是随机化。
首先观察题目一个裸的二分，但是位置会随机移动。假设我们确定它所在区间的长度为 $len$，那么我们每次二分可以使得区间长度减少 $\frac {len} 2$，但是又会增加 $2 \times k$（他可能从左边走出区间或者右边走出区间，每次最多走出 $k$ 距离）
那么当长度为 $4 \times k$ 的时候我们就卡死了，因为每次减少的长度为 $2 \times k$，而增加的长度也是 $2 \times k$，确定区间没有变。
我们观察到这个 $k$ 实际上是非常小的，所以......自信随机化！每次当确定长度小于一个你定的值（这个地方有讲究，下面可以说一下）的时候，就随机选择区间中的一个值 $x$ 询问 $[x,x]$，如果成功就结束程序，失败的话就继续二分（记得扩大区间 $2 \times k$，因为执行了一次操作）直到区间长度小于我们定的值，继续随机化。
依旧考虑正确性，假设 $n = 10 ^ {18},k = 10$ 并且使得区间长度为 $40$（最小可确定长度），最开始我们会花费 $60$ 次找到目标区间，然后每次有 $\frac 1 {40}$ 的概率猜对，如果失败我们会花费 $5$ 次重新把区间长度定位回 $40$，所以我们保守（偏小）可以执行 $800$ 多次操作，错误率仅有 $2 \times 10^{-10}$，可以忽略
另外理论上最低长度是 $40$，不过有更优秀的长度！根据以下程序，我们发现 $59$ 才是最优区间长度，错误率仅有 $2 \times 10 ^ {-33}$。
const int times = 4400;
inline double Solve(int minLen){
int cnt = 0;
double ans = 1;
long long len = minLen + 20;
while(len > minLen){
len /= 2;
len += 20;
cnt++;
}
double poss = (double(minLen-1) / double(minLen));
for(int i = 1;i <= times / cnt;i++){
ans *= poss;
}
return ans;
}这是因为从 $60$ 次变回 $40$ 次的代价太高，我们如果调整长度，虽然单次错误率（底数）会变大，但是尝试的次数（指数）也会变大，而指数的影响比起底数要大一点，所以如果这道题稍微卡一下的话可以列一个刚才的测试程序打表看看哪个长度更优（不过为了降低随机性，这种题目一般无论什么参数正确率都很高，理论上来讲正确做法的参数不太离谱都能过）
代码
#include<bits/stdc++.h>
#define Akano 1
#define pure__Elysia 0
#define loves ^
using namespace std;
using ll = long long;
ll n,k;
mt19937_64 rng(time(0));
inline ll rd(ll l,ll r){
return (rng() % (r - l + 1)) + l;
}
inline bool Get(ll l,ll r){
cout<<l<<" "<<r<<endl;
string res;
cin>>res;
if(res == "Yes"){
if(l == r)exit(0);
return true;
}
return false;
}
int main(){
cin>>n>>k;
ll l = 1,r = n+1;
while(true){
l -= k,r += k;
l = max(l,1ll),r = min(r,n);
while(l + 4 * k < r){
const ll mid = (l + r) >> 1;
if(Get(l,mid)){
r = mid;
}else{
l = mid + 1;
}
l -= k,r += k;
l = max(l,1ll),r = min(r,n);
}
const ll now = rd(l,r);
Get(now,now);
}
return not(Akano loves pure__Elysia);
}励志打完所有交互题
Comments NOTHING