题解 CF1028G 【Guess the number】

· · 题解

这么好的题没人写题解？？？

本题让我重新认识了交互题……

好了，进入正题：这道题怎么做?

首先注意题目中的一个限制：

如果 k > x  ，游戏将立刻以失败告终

那么说，如果我们已经确定最终答案所在的区间 l,r ,也就是说最终答案 x 不会小于 l ,我们就只能询问最多 l 个数字。

既然最多询问 l 个数字，那么作为资深的 OI 玩家，肯定会去尽可能多的询问数字。

那么问题就来了，我们怎么最好的利用这 l 次机会。

如果只有一次机会，那么我们连续询问 l 个数字就可以了。

那么如果不止一次机会呢？

（我们rand一下，多交几次说不定就过了）

那么考虑一下，如果我们询问 k 个数字，我们实际上是将答案分成了 k+1 个区间，那么如果还有 q 次机会，我们必须要保证每一个分出来的区间都能在 q-1 次询问中获得答案。

等等，从 q-1 到 q ，这 ™ 不就是个 dp 吗？

我们设 dp(i,j) 表示当前最多可以询问 i 个数字而不至于GG，还有 j 次机会，我们所能确定的区间的最大长度。也就是说，如果这时我们能确定区间 [l,r] 那么这玩意的值就是 r-l+1。

那么怎么转移呢，我们只需用类似模拟的方法：我们对于当前的一个位置 pos，每次选取用从这个位置开始 j-1 次机会无法到达的第一个位置，以此来得到最终答案。

感觉说的有点乱，那么我们看一下这部分的代码：

    for(int j=1;j<=4;j++)
        for(int i=1;i<=10000;i++)
        //原题有要求，单次询问数字个数不能超过10000
        {
            long long now=i;
            dp[i][j]=dp[i][j-1];//现在不用询问的位置
            //我们应当询问数字：i+dp[i][j-1]
            now=min(i+dp[i][j-1]+1,(long long)10000);
            //第一个询问数字的下一个数字。
            //询问数字个数不能超过10000
            for(int k=1;k<=i;k++)
            {
                if(now==10000)
                //小优化，因为超过10000后询问次数不会增加。
                {
                    dp[i][j]+=(dp[now][j-1]+1)*(i-k+1);
                    break;
                }
                dp[i][j]+=dp[now][j-1]+1;//注意加上询问的数字，即那个1
                now=min(now+dp[now][j-1]+1,(long long)10000);
                //下一个起始位置
            }
        }

如果我们求出了 dp 数组，那么询问时就可以模仿求 dp 数组的方式去找出每一个询问的数字，即每次为剩下的询问机会留出尽可能大的区间。

下面是完整代码：

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
const long long M = 10004205361450474;
long long dp[10010][6];
long long t[10010];//存一下询问了那些数
int main()
{
    for(int i=1;i<=10000;i++)
        dp[i][0]=0;//如果没有机会，那么一个数也问不了
    for(int j=1;j<=4;j++)
        for(int i=1;i<=10000;i++)
        {
            long long now=i;
            dp[i][j]=dp[i][j-1];
            now=min(i+dp[i][j-1]+1,(long long)10000);
            for(int k=1;k<=i;k++)
            {
                if(now==10000)
                {
                    dp[i][j]+=(dp[now][j-1]+1)*(i-k+1);
                    break;
                }
                dp[i][j]+=dp[now][j-1]+1;
                now=min(now+dp[now][j-1]+1,(long long)10000);
            }
        }
    long long now=1;
    for(int i=4;i>=0;i--)
    {
        long long num=now;
        t[0]=now-1;//注意修改左端点
        int tot=0;
        for(int j=1;j<=min(now,(long long)10000);j++)
        {
            num+=dp[min(num,(long long)10000)][i];//下一个端点
            if(num>M)break;//我不知道有没有用……
            t[++tot]=num;//询问
            num++;//记得去掉询问点
        }
        printf("%d ",tot);
        for(int j=1;j<=tot;j++)
            printf("%I64d ",t[j]);
        printf("\n");
        fflush(stdout);
        int pos;
        scanf("%d",&pos);
        if(pos<0)return 0;
        now=t[pos]+1;//x比t[pos]大
    }
    return ~~(0-0);//I'm so cute(^_^)
}