【题解】P8491 [IOI2022]囚徒挑战

· · 题解

题目传送门

题意自己看。

考虑最小化 m 的值，如果 m=n 就有很显然的做法，直接随便问一个袋子把那个袋子的数写黑板上就行了，可以获得 5pts。

然后考虑一点比较聪明的策略，比较两个数大小没必要枚举，可以比较每一位的值就行，每次写一个数的最高位，比另一个数的相应位置即可。这样你需要记录黑板上的数是哪一位上的。假如你存的是一个 b 进制数，那当前位取值就是 [0,b)，那这个跟 n \times m 矩阵中的点 (i,j) 一维映射成 (i-1) \times m+j 是一样的。但是考虑最后一位为 0 的情况，你需要跟初始状态为 0 作区分，因此你只需要额外 +1，所以在第 i 位的原数上加个 (i-1) \times b+1 即可。

然后你考虑一共有 \left\lceil\log_b n\right\rceil 位，每一位最大值为 b-1，所以 m 的最大值为 b(\left\lceil\log_b n\right\rceil-1)+1+b-1，即 m=b\left\lceil\log_b n\right\rceil。

当 n=5000 时，取 b=3 得到最优解，此时 m=24。

然后考虑 [1,m] 每个值都对应一次比较，那么减少需要比较的情况就相当于减少 m。发现 A \neq B，所以无论如何它们比较到最后一位时不会相等。而最后一位只有 0,1,2 三种可能性，查询到最大值 2 和最小值 0 时都可以直接看，只有看到 1 时需要再比较一次，那么也就是有两种情况不需要比较，于是可以做到 m=22。

但是会发现 m=22 已经是这个做法瓶颈了，考虑一些新做法。

想象一棵搜索树，可以想到进制位这种做法类似链式结构，宽度不大而深度很深，考虑把这棵树改成类似线段树的形式，以宽度换深度。

那么不难想到类似线段树的结构，判断每个决策点可能属于哪个区间，每次递归下去，最后找到单点。

然后你惊喜地发现这个东西很有优化前途，因为每次递归到一个区间 [l,r]，都可以运用之前的优化去掉最大值最小值，使需要比较的区间变为 [l+1,r-1]，于是每次区间长度 -2。

然后这个东西显然全用 3 进制就不是很优秀了，考虑 2 和 3 混合使用，然后你可以递推一下每一层比较用哪个底数比较好，其中一种比较优秀的方式是 2,3,3,3,3,3,3，然后这样就能做到 m=20。

这个东西实现很麻烦，需要微调底数位置，然后可以通过递归或者倍增实现。以下给出一份递归实现的代码。

代码：

#include<bits/stdc++.h>
#include"prison.h"
#define ll long long
#define back return
#define ri int
using namespace std;
vector<vector<int>> s;
void work(int p,int d,int id,int pl,int pr,int l,int r)
{
    int now=3*(d-1)+id;
    for(ri i=pl;i<=pr;i++)
        s[p][i]=now;
    for(ri i=l;i<=pl;i++)
        s[now][i]=-s[now][0]-1;
    for(ri i=pr;i<=r;i++)
        s[now][i]=s[now][0]-2;
    pl++,pr--;
    if(pl>pr)
        back ;
    if(pr-pl<=1)
    {
        work(now,d+1,1,pl,pr,pl-1,pr+1);
        back ;
    }
    if(pr-pl<=3)
    {
        int mid=(pl+pr)/2;
        work(now,d+1,1,pl,mid,pl-1,pr+1);
        work(now,d+1,2,mid+1,pr,pl-1,pr+1);
        back ;
    }
    int mid1=(pl*2+pr)/3,mid2=(pl+pr*2)/3;
    work(now,d+1,1,pl,mid1,pl-1,pr+1);
    work(now,d+1,2,mid1+1,mid2,pl-1,pr+1);
    work(now,d+1,3,mid2+1,pr,pl-1,pr+1);
}
vector<vector<int>> devise_strategy(int n)
{
    for(ri i=0;i<=20;i++)
        s.push_back(vector<int>(n+1,0));
    s[0][0]=s[4][0]=s[5][0]=s[6][0]=s[10][0]=s[11][0]=s[12][0]=s[16][0]=s[17][0]=s[18][0]=1;
    work(0,0,3,1,n,1,n);
    back s; 
}