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

· · 题解

Preface

如果这题在去年的专题中出现，我就会知道构造题可以打表，我就能做出百万富翁，我就能高一进集训队，我现在就不用努力了。

可是没有如果，不要为过去的事情玉玉了，毕竟还有一次机会。最后 50 天，一定要加油啊。

Solution

很神秘的题目。

按照今天早上上课的说法，这道题让我们构造一个比较 a 和 b 大小的自动机。

有一个非常朴素的想法：从高往低按位比较。

第一个人把 a 的最高位通过某种方式记录到黑板上。第二个人通过黑板上的数据判断出这是 a 的最高位并将其解码，然后读取 b 的最高位。如果能比出大小，就直接返回；否则，将 b 的次高位记到黑板上，留给第三个人解码，依此类推。

思路 1：按照二进制。设 V = \lceil \log_2 N \rceil，则我们容易给出 x=2V 的构造：当黑板上记录了 x_0 的时候，表示的是二进制从高往低第 \lfloor \frac{x_0+1}{2} \rfloor 位，值是 x_0 \bmod 2。如果是奇数位，那么表示的是 a，否则表示的是 b。完成了 x=26。

思路 2：根据经典结论，如果若干个数和为定值，那么将其拆成若干个 3 乘起来最大。也就是说，我们使用三进制，这样完成了 x=24。

这两个看起来都挺人类的。有没有更牛的做法呢？

有的兄弟，有的！

思路 3：我们知道 1 \le n \le 5000。所以一个人读取到 1 或者 5000 了，就可以直接返回。

也就是说！设 f_x 为 x 最大能表示多少数，则有：

f_x = \max_{1 \le y \le x} yf_{x-y}+2

其中 f_0=0。发现 f_{20} 恰好大于等于 5000！

给出构造：3 3 3 3 3 2 2 1，5588 1862 620 206 68 22 10 4。

总结一下，这道题有一点“通信题”的特征（本质还是构造策略）。先设计一个朴素的算法，然后观察有没有可以优化掉的 corner case，就可以带来可观的优化。

代码有一点小细节吧。

#include<bits/stdc++.h>
#define ffor(i,a,b) for(int i=(a);i<=(b);i++)
#define roff(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
vector<int> bs={3,3,3,3,3,2,2,1,0};
vector<int> mul={5588,1862,620,206,68,22,10,4,2};
int calc_rnk(int p,int x) {
    ffor(i,0,p-1) {
        if(x==mul[i]-1||x==0) return 0;
        x--;
        x%=mul[i+1];
    }
    return x;
}
vector<vector<int>> devise_strategy(int N) {
    vector<int> tmp;
    vector<vector<int>> ans;
    tmp.resize(N+1);
    ffor(i,0,20) ans.push_back(tmp);
    ffor(i,0,N-1) {
        if(i==0) ans[0][i+1]=-1;
        else if(i==5587) ans[0][i+1]=-2;
        else ans[0][i+1]=((i-1)/1862)%3+1;
    }
    ffor(i,0,7) {
        int l=1,r=0;
        ffor(j,0,i-1) l+=bs[j];
        r=l+bs[i]-1;
        ffor(t,l,r) {
            ans[t][0]=((i^1)&1);
            ffor(j,0,N-1) {
                int col=calc_rnk(i,j);
                if(col==-1) ans[t][j+1]=-1;
                if(col==0) {
                    if(ans[t][0]==0) ans[t][j+1]=-1;
                    else ans[t][j+1]=-2;    
                }
                else if(col==mul[i]-1) {
                    if(ans[t][0]==0) ans[t][j+1]=-2;
                    else ans[t][j+1]=-1;    
                }
                else {
                    int p=((col-1)/mul[i+1])%bs[i]; 
                    if(p!=t-l) {
                        if(p<t-l) {
                            if(ans[t][0]==0) ans[t][j+1]=-1;
                            else ans[t][j+1]=-2;
                        }
                        else {
                            if(ans[t][0]==0) ans[t][j+1]=-2;
                            else ans[t][j+1]=-1;    
                        }
                    }
                    else {
                        int col=calc_rnk(i+1,j);
                        if(col==0) {
                            if(ans[t][0]==0) ans[t][j+1]=-1;
                            else ans[t][j+1]=-2;
                        }
                        else if(col==mul[i+1]-1) {
                            if(ans[t][0]==0) ans[t][j+1]=-2;
                            else ans[t][j+1]=-1;
                        }
                        else ans[t][j+1]=((col-1)/mul[i+2])%bs[i+1]+r+1;
                    }
                }
            }
        }
    }
    return ans;
}