我怎么天天颓废

• CF1483E Vabank

感谢神仙 _MoonPie_ 给的这个题 ，终于会这题做法了。

首先我们有 1 块，可以询问 1 ，如果失败就知道了答案；否则继续询问 2,4,8\dots 直到一次失败，确定答案区间为 [2^i,2^{i+1}) 。这部分有 \log (10^{14}) 次询问（约 47 次）

然后还要在剩下的 50+ 次询问中找出正确答案。

如果现在不确定区间为 [L,R] ，手中的钱有 \ge R-L+L\times y ，

那么询问一次 X ：

• 询问成功：区间变为 [X+1,R] ，手中的钱变为 R-L+L\times y+X ，此时做调整使钱数 \ge R-(X+1)+(y+1)(X+1)
• 询问失败：区间变为 [L,X-1] ，手中的钱变为 \ge R-L+L\times y -X\ge (X-1)-L+L\times (y+1) 。

这样的话：

• 询问成功：钱变为 \ge R-L+L(y+1)
• 询问失败：钱变为 \ge R-L+L(y-1) （ L,R 指新的区间）

可以使用上面那个 高楼扔鸡蛋 问题的第二个 dp 做法来找答案。

这个 y 可以看做鸡蛋数，询问成功多一个鸡蛋，询问失败少一个鸡蛋。

设 f(x,y) 为还剩 x 次询问机会，钱数为 R-L+L\times y ，最多能确定多长的区间。

设分界点 p=f(x-1,y+1)+1 ，询问一下 p 。那么 f(x,y)=f(x-1,y+1)+1+f(x-1,y-1) （上面能确定的个数+下面能确定的个数+1 ）。

（如果不懂这个转移，可以看上面那个知乎链接）

于是每次询问点在 dp 中也就确定了。可以在 \le 50 次询问内搞定答案。

最后还有那个前面提到的“调整钱数”，官方题解说调整的询问次数 \le 3 但我不会证...

#include<bits/stdc++.h>
#define For(i,a,b) for(register int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(register int i=(a);i>=(b);--i)
#define int long long
using namespace std;
inline int read()
{
    char c=getchar();int x=0;bool f=0;
    for(;!isdigit(c);c=getchar())f^=!(c^45);
    for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
    if(f)x=-x;return x;
}

int askcnt,now,qaq,MX=1e14;
inline int ask(int x){
    if(x>MX){
        return 0;
    }
    askcnt++;
    if(qaq){
        if(x<=qaq)return now+=x,1;
        else return now-=x,0;
    }
    cout<<"? "<<x<<endl;
    string s;cin>>s;
    if(s=="Lucky!")return now+=x,1;
    return now-=x,0;
}

bool vis[105][105];
int dp[105][105]; 
void work()
{
    int l=1,r=1e14;
    now=1,askcnt=0;
    if(!ask(1)){
        cout<<"! 0"<<endl;
        return;
    }
    while(1){
        int k=now;
        if(ask(k))l=k;
        else{r=k-1;break;}
    }
    now=0;
    ask(l);
    int x=1,y=(now>=r);
    while(dp[x][y]<=r-l) x++;

    while(l<=r)
    {
        while(r-l>dp[x][y])
            ask(l-1),++y;
        int mid=l+dp[x-1][y-1];
        while(now<mid) ask(l-1);
        if(ask(mid)) ++y,--x,l=mid+1;
        else --x,--y,r=mid-1;
    }
    cout<<"! "<<l-1<<endl;
    if(qaq)printf("x=%lld cnt=%lld\n",qaq,askcnt);
}

int F(int x,int y)
{
    if(vis[x][y])return dp[x][y];
    vis[x][y]=1;
    if(x==0)return 0;
    if(y==0)return dp[x][y]=dp[x-1][1];
    return dp[x][y]=F(x-1,y+1)+1+F(x-1,y-1);
}

signed main()
{
    // x=0 dp(0,y)=0
    // y=0 dp(x,0)=dp(x-1,1)
    For(x,0,50)
        For(y,0,x)
            F(x,y);
//  qaq=99999999999808;
    int T=read();
    while(T--)work();
    return 0;
}