白昼在我耳边起舞
Cetana
·
·
题解
简要题意
你有一个计数器 s，初值为 1。交互库有一个隐藏的 M。每次询问你可以给出一个 x，然后：
在保证 s 一直非负的前提下在 105 次询问内找出 M 的精确值。
---
### 简要观察
首先我们发现第一次询问只能问 $1$，问其他的都有可能让 $s$ 变成负数。
同理，接下来我们会询问 $2,4,\cdots$，直到第一次大于 $M$。
此时 $s=0$，且我们知道有一个 $k\in\N,s.t.\ M\in[2^k,2^{k+1})$，到这里大概需要不超过 $\log V$ 次询问。
然后我们可以考虑直接在 $[2^k,2^{k+1})$ 中二分 $M$，唯一的问题是为了保证 $s$ 始终非负，我们有可能需要在某些询问前额外花费一些询问次数来增大 $s$。
事实上，这里直接二分可以被卡到大约 $2\log V$，总的次数也就是大约 $3\log V$ 的量级。
---
### 优化？
直观感受是第一步已经没有优化空间了；而第二步的部分因为额外的询问会产生一定的浪费，我们考虑从这里下手。
如果我们的询问不问在区间的中点，它还能问在哪里呢？感性理解一下，我们的询问偏右是不优的，因此我们会让询问的点靠左。
考虑到现在困扰我们的是为了保障合法而多付出的询问，感觉上我们需要新增一个量来衡量我们对“失败”的承受度。
一种办法是设 $s\ge yL+(R-L)$，这里我们使用 $y$ 来大致衡量我们还可以失败多少次。
现在对于一次对 $X$ 的询问：
- 失败了，考虑 $[L,X-1]$，此时 $s'=yL-(R-L)-X\ge(y-1)L+(X-1-L)$。
- 成功了，考虑 $[X+1,R]$，此时 $s'=yL-(R-L)+X$，我们先假设它不小于 $(y+1)(X+1)+(R-X-1)$。
即现在我们将问题变成了高楼扔鸡蛋的变体，不妨设 $f_{x,y}$ 表示确定现在的 $y$ 值还剩 $x$ 次询问，最多可以找到答案的区间长度。
容易得到 $f_{x,y}=f_{x-1,y+1}+1+f_{x-1,y-1}$，边界需要特殊考虑一下，但不是重点。
---
注意到我们之前做出了一个假设。
我们现在仔细考虑一下：$[(y+1)(X+1)+(R-X-1)]-[yL+(R-L)+X]\\$ 化简得：$(y-1)(X-L)-X\le(y-1)(X-L)$。
也就是说我们每次成功的询问至多需要补充 $Val=(y-1)(X-L)$ 的值到 $s$ 中，显然所有的 $X-L$ 的总和是不超过 $R-L$ 的。
现在继续意识流分析：我们观察之前 DP 出的询问策略，可以发现随着我们的询问，区间长度大致还是以指数衰减的，而每次询问最多就使 $y$ 增加 $1$。$(y-1)$ 增大带来的影响会迅速地被 $X-L$ 的减小削弱。故我们宣称总的 $Val$ 是不超过 $3(R-L)$ 的，我们在每次要询问但发现目前的 $s$ 小于询问的 $X$ 时补充一次，一共不会补充超过 $3$ 次。
---
:::success[Code]
```cpp
#include<bits/stdc++.h>
using namespace std;
#define int long long
int T,dp[105][105];
signed main()
{
for(int i=1;i<=50;i++){
dp[i][0]=dp[i-1][1];
for(int j=1;j<=50;j++){
dp[i][j]=dp[i-1][j+1]+1+dp[i-1][j-1];
}
}
scanf("%lld",&T);
auto qry=[&](int &rs,int pr){
if(pr>1e14)return false;
fflush(stdout);
char op[20]="";
scanf("%s",op);
if(op[0]=='L'){
rs+=pr;
return true;
}
else{
if(rs<pr)exit(0);
rs-=pr;
return false;
}
};
auto rep=[](int x){
printf("! %lld\n",x);
fflush(stdout);
};
while(T--){
int rs=1;
int l,r,mid;
for(int i=0;i<=50;i++){
if((1ll<<i)>1e14){
r=1e14;
l=(1ll<<i)/2+1;
break;
}
bool v=qry(rs,1ll<<i);
if(!v){
l=(1ll<<i)/2+1;
r=(1ll<<i)-1;
break;
}
}
qry(rs,l-1);
int ttx=0,tty=rs>=r;
while(dp[ttx][tty]<r-l+1)ttx++;
ttx++;
while(l<=r&&ttx){
if(tty==0){
qry(rs,l-1);
tty++;ttx--;
}
else{
int p=l+dp[ttx-1][tty-1];
while(rs<p)qry(rs,l-1);
bool v=qry(rs,p);
if(v){
tty++;ttx--;
l=p+1;
}
else{
tty--;ttx--;
r=p-1;
}
}
}
rep(l-1);
}
return 0;
}
```
:::