题解：P8491 [IOI 2022] 囚徒挑战

· · 题解

更好的阅读体验

由于所有人都不知道自己是谁，他的决策只能依据黑板上的数字，因此有 500 个人这个条件实际上是没用的，真正有用的实际只有 x 个人。

省略一些写的数字大小是 O(n) 的做法。

本题解中，一个数在某个进制下的第 k 位，指从低位往高位数的第 k 位。

\boldsymbol {x = 52}

52 = 2 \times 2 \times \lceil \log_2 5000 \rceil

由于每个人可以获得的信息非常少，我们考虑按位比较，找到第一个不同的位，然后报告答案。

我们可以在黑板上记录这三样信息：

一个人进入房间后，先观察上一个人看的是 A 还是 B。如果是 A 就继续翻看 B 的同一位，并进行比较；如果是 B 那么就翻看 A 的下一位。

那么状态数就是 52。

\boldsymbol{x = 39}

39 = 3 \times \lceil \log_2 5000 \rceil

发现上面有状态浪费。(1,x, 0/1) 这样的一个状态是没用的，也就是说，我们读取 A 的当前位时，并不关心 B 的上一位是多少。

我们可以在黑板上记录这两样信息：

在此基础上，我们套用 x = 52 的构造策略，即可做到 x = 39。

\boldsymbol{x = 26}

26 = 2 \times \lceil \log_2 5000 \rceil

发现上面的那个构造是将 A，B 放在不平等的位置，而 (x, 2) 这样的一个状态看起来还是很浪费。

我们发现，上面那个做法，我们在查看 B 的时候，不仅可以看到 B 的当前位并和 A 的当前位比较，还能同时记录下 B 的下一位。然后下一个人在查看 A 之后，不仅可以将 A 的下一位和 B 的下一位比较，还能接着记录 A 的下两位……这样交替的状态，可以将形如 (x, 2) 这类空状态省去。

这样我们只需要记录：

由于是奇偶交替的，上一个人看的具体是哪个盒子，可以通过当前是第几位算出来。

由此做到 26。

\boldsymbol{x = 24}

24 = 3 \times \lceil \log_{\color{red} 3} 5000 \rceil

我们试图不再使用二进制，假设用 B 进制，那么需要的状态数就是 B \lceil \log_B 5000 \rceil。经验证，B = 3 的时候比较优秀。

然后我们沿用 x = 26 的做法，即可做到 x = 24。

\boldsymbol{x = 22}

22 = 3 \times \lceil \log_3 5000 \rceil - 2

我们发现，到了最后一位，假如我们看到了 0/2，那么我们就不需要检查另一个盒子了，因为题目保证了两个盒子的球数不相同。

那么我们可以省略掉 (0, 0) 和 (0, 2) 两个状态，可以做到 22。

\boldsymbol{x = 21 / 20}

这个时候要动大手术了，发现上面那个做法已经卡得很满了。但是 x = 22 的做法启发我们，在某些触碰到边界的地方，不需要新开一个状态记录，而是可以直接返回。

用进制表示有它的局限性。我们可以用一个类似线段树的结构来理解它。对于三进制的情形，那我们刚才的做法，就是将每个区间分成三块，如果目前 A，B 不在同一块，则可以比出大小；否则如果在同一块，就进入这个小块重复这个过程。

而回顾线段树干的事情：每个节点代表一个区间。这是否意味着，对于线段树上每个节点，如果我们进入这个节点的时候踩着左端点或者右端点，这个时候就可以直接比出大小，而不需要再进行递归计算了！

我们将三叉线段树调整成如下图的结构。

我们把每个区间的左端点和右端点抠掉（图中红色和蓝色的部分），这些位置是可以直接比出大小的，不需要再继续进行分段。

在去掉每个区间的端点之后再进行刚才那个交替的过程，可以做到 21。

优化到 20 也不难，完全不需要 dp。

经过肉眼观察，我们发现有一步要把一个长度为 6 的区间分三段。但是实际上分两段会更优，如图所示。

我们在最后一层换成一个二叉的结构，其余层沿用三叉的结构，可以做到 20。

那么这道题就做完了。在代码实现中，我先把这颗树建出来，处理出每个点在每一层属于那个区间。然后对每个节点分别考虑它会到达下一层的那个节点即可。

实现细节和题解代码都不太一样。

#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
constexpr int all=5102;
int tot,id[10][4],d[all+10],col[all+10],bel[10][all+10];
//-1: minimum; -2: maximum
void init(int l,int r,int dep)
{
    bel[dep][l]=-1,bel[dep][r]=-2;
    if(r-l<=1)return;
    if(r-l==5)
    {
        if(!id[dep][0])
            id[dep][0]=++tot,d[tot]=dep,col[tot]=0;
        if(!id[dep][1])
            id[dep][1]=++tot,d[tot]=dep,col[tot]=1;
        int mid=l+r>>1;
        for(int i=l+1;i<=mid;i++)bel[dep][i]=id[dep][0];
        for(int i=mid+1;i<r;i++)bel[dep][i]=id[dep][1];
        init(l+1,mid,dep+1);
        init(mid+1,r-1,dep+1);
        return;
    }
    int len=r-l-1,mid1=l+len/3,mid2=mid1+len/3;
    if(!id[dep][0])
        id[dep][0]=++tot,d[tot]=dep,col[tot]=0;
    if(!id[dep][1])
        id[dep][1]=++tot,d[tot]=dep,col[tot]=1;
    if(!id[dep][2])
        id[dep][2]=++tot,d[tot]=dep,col[tot]=2;
    for(int i=l+1;i<=mid1;i++)bel[dep][i]=id[dep][0];
    for(int i=mid1+1;i<=mid2;i++)bel[dep][i]=id[dep][1];
    for(int i=mid2+1;i<r;i++)bel[dep][i]=id[dep][2];
    init(l+1,mid1,dep+1);
    init(mid1+1,mid2,dep+1);
    init(mid2+1,r-1,dep+1);
}
vector<vector<int> > devise_strategy(int n)
{
    init(1,all,0);
    vector<vector<int> > s;
    for(int i=0;i<=20;i++)
    {
        s.push_back(vector<int> (n+1,0));
        if(i==0)
        {
            s[i][0]=0;
            for(int j=1;j<=n;j++)s[i][j]=bel[0][j];
        } else {
            int now_d=d[i];
            s[i][0]=(now_d&1)^1;
            for(int j=1;j<=n;j++)
            {
                if(bel[now_d][j]==-1)s[i][j]=-1-s[i][0];
                else if(bel[now_d][j]==-2)s[i][j]=-2+s[i][0];
                else if(col[bel[now_d][j]]!=col[i]) {
                    if(col[bel[now_d][j]]<col[i])s[i][j]=-1-s[i][0];
                    else s[i][j]=-2+s[i][0];
                } else {
                    int nxt_d=now_d+1;
                    if(bel[nxt_d][j]==-1)s[i][j]=-1-s[i][0];
                    else if(bel[nxt_d][j]==-2)s[i][j]=-2+s[i][0];
                    else s[i][j]=bel[nxt_d][j];
                }
            }
        }
    }
    return s;
}