[DP]Codeforces1028G【Guess the number】题解

Author Avatar
ZigZagK 2018年9月4日 20:59
remove_red_eye 18

题目概述

交互题,现在有一个数 $x(1\le x\le 10004205361450474)$ ,每次可以询问 $k(k\le x\land k<10000)$ 个数,将会回答 $a_{pos-1}<x<a_{pos}$ 或者 $x=a_{pos}$ ,此时胜利。在 $5$ 次询问内胜利。

解题报告

神仙题,由于并不知道 $x$ ,所以不敢询问太大的 $k$ 。考虑这样的策略:目前还有 $t$ 次询问,已经知道 $x\ge L$ ,那么我求出在 $L$ 花 $t-1$ 次能够到达的最远位置 $R$ ,然后从 $R+1$ 开始,求出花 $t-1$ 次能够到达的最远位置 $R'$ ,做 $min\{L,10000\}+1$ 次(询问 $k$ 有 $k+1$ 个区域)之后的 $R$ 就是 $t$ 次询问能到达的最远位置,这样能保证所有区域内都可以回答。

这其实就是个DP,定义 $f_{t,L}$ ,然后转移一下。

ps:你会发现 $f_{5,1}=10004205361450474$ ,只能呵呵。

示例程序

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxq=5,maxk=10000;const LL M=1e18;

LL a[maxk+5],f[maxq+5][maxk+5],pos=1;

LL DP(int t,LL L){
    if (!t) return L;if (L>maxk) return min(M,DP(t,maxk)-maxk+L);if (f[t][L]) return f[t][L];
    f[t][L]=L;for (int i=1;i<=L;i++) f[t][L]=DP(t-1,f[t][L])+1;f[t][L]=DP(t-1,f[t][L]);return f[t][L];
}
int main(){
    printf("%lld\n",DP(2,1));return 0;
    for (int t=5;t;t--){
        int K=min(pos,(LL)maxk);LL R=pos;printf("%d",K);a[0]=pos-1;
        for (int i=1;i<=K;i++) pos=DP(t-1,R),R=pos+1,printf(" %lld",pos),a[i]=pos;puts("");
        fflush(stdout);int now;scanf("%d",&now);if (now<0) return 0;pos=a[now]+1;
    }return 0;
}

本文链接:https://zigzagk.top/2018/09/04/CF1028G
本博客所有文章除特别声明外,均采用CC BY-NC-SA 4.0 CN 许可协议。转载请注明作者和出处QwQ。