题目描述
Alice 和 Bob 玩游戏。
Alice 有一个 \(1~n\) 中的正整数 \(y\)。Bob 不知道这个数。
游戏中的每一轮，Bob 选一个正整数 \(x\)，并提问 Alice：\(y\) 是否大于等于 \(x\)？然后 Alice 需要回答是或否。
Alice 可以说至多一次谎。Bob 想要用尽量少的轮数确定 \(y\)，Alice 希望 Bob 用的次数尽量多。
假设双方除第一轮外均采用最优策略。
作为一只 Goodeat，你既不是 Alice，也不是 Bob。
但你需要求出，对每个 \(x=1,2,...,n\)，当 Bob 第一轮问 \(y\) 是否大于等于 \(x\) 且 Alice 第一轮回答了 是 的情况下，Bob 还需要多少轮能确定 \(y\)。
（Alice 第一轮有可能说谎。）
思路
算法一
由于加入了说谎的机制，我们不能像原来的猜数游戏一样二分求解。
我们可以把每次询问看成一次覆盖，把“否”的一端覆盖掉，那么当一个区间被覆盖了两次，这个区间便不可能成为答案。
暴力搜索期望得分 \(20\) 分。
算法二
容易发现，去掉覆盖两次的区间之后，最后一定是形如 \(x\) 个 \(0\)，\(y\) 个 \(1\)，再 \(z\) 个 \(0\)。
设 \(dp_{x,y,z}\) 表示出现上面的序列时，还需要猜多少次。转移可以枚举 Bob 第一轮的分界位置。
时间复杂度 \(O(n^4)\)，期望得分 \(40\) 分。
算法三
考虑优化算法二。
我们注意到，在某个位置之前 Alice 回答大于更优，这个位置之后 Alice 回答小于更优。\(x,y\) 确定之后，对于不同 \(z\)，这一位置一定是单调的，于是我们可以线性算出这个位置并记录。
时间复杂度变为 \(O(n^3)\)，期望得分 \(70\) 分。
算法四
考虑 \(dp\) 的值域只有 \(O(\log n)\)，且关于 \(z\) 单调，于是我们改写状态，定义 \(f_{x,y,w}\) 表示最大的 \(w\) 满足 \(dp_{x,y,z}\le k\)。
这样一来 \(f\) 的状态只有 \(O(n^2 \log n)\) 种，而且转移方法类似。
期望得分 \(100\) 分。
代码
// ubsan: undefined
// accoders
/*
* Title: D. 猜数游戏
* Source: accoders NOI-2022NOIP A层联测20
* URL: http://47.92.197.167:5283/contest/275/problem/4
* Author: Steven_lzx
* Command: -std=c++23 -Wall -fno-ms-extensions
* Date: 2022.11.4
*/
#include <bits/stdc++.h>
using namespace std;
const int MAXN=2001,MOD=998244353,INF=0x3f3f3f3f;
int n,dp[20][MAXN][MAXN],res,i,j,k;
int main()
{
freopen("guess.in","r",stdin);
freopen("guess.out","w",stdout);
scanf("%d",&n);
for(i=0;i<20;i++)
for(j=0;j<=2000;j++)
for(k=0;k<=2000;k++)
dp[i][j][k]=-INF;
dp[0][0][1]=dp[0][1][0]=0;
dp[0][0][0]=1;
for(res=1;res<20;res++)
{
for(k=0;k<=n;k++)//k:mid
{
for(i=0;i<=n-k;i++)
{
j=dp[res-1][k][i]+dp[res-1][0][k];
if(j>=0)
{
j=min(j,n-k);
dp[res][k][i]=max(dp[res][k][i],j);
dp[res][k][j]=max(dp[res][k][j],i);
}
}
for(i=0;i<=k;i++)
{
j=k-i;
if(dp[res-1][i][j]>=0&&dp[res-1][j][i]>=0)
dp[res][k][min(dp[res-1][i][j],n-k)]=max(dp[res][k][min(dp[res-1][i][j],n-k)],min(dp[res-1][j][i],n-k));
}
for(i=n-k+1;i>=0;i--)
dp[res][k][i]=max(dp[res][k][i],dp[res][k][i+1]);
}
}
for(i=1;i<=n;i++)
{
j=0;
while(dp[j][n-i+1][i-1]<0)
j++;
printf("%d ",j);
}
putchar('\n');
fclose(stdin);
fclose(stdout);
return 0;
}