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

· · 题解

这题是神秘提交答案题。其函数格式创到我了，说是返回 int[][]，其实要返回 vector<vector<int>>。

首先可知，第一个人知道自己是第一个进入房间的人，因为他和他后面的人都一定不会把 0 写在白板上。定义 A 袋子中数字为 a，B 袋子中数字为 b。

先尝试打表，发现如果可传递的数字值域是 0，则可以比较的数字大小是 1\sim2。如果可传递是数字值域是 0\sim1，则可比较的数字值域是 1\sim 4，考虑如下策略：

  1. 第一个人进入房间看到数字 0 打开袋子 A，如果a = 1 或者 a = 4，则 a 一定是最大值或最小值，否则在白板上写下数字 1，表示他已经看过了袋子 A 且里面放的数字是 2 或 3。
  2. 第二个人进入房间看到数字 1，他知道 a \in \{2,3\}，他查看 b，b 是 1\sim 4 中的任意一个第二个人都能比较出 a 和 b 的大小关系。

可以发现，如果某一个袋子中的数字值域已经确定为 [x,x+1]，另一个袋子中的值域确定为 [x-1,x+2]，则只需要打开值域大的那个袋子即可确定两个袋子数字的大小关系。

考虑白板数字值域为 0 \sim 3 的情况，可比较的数字大小是 1 \sim 10，考虑如下策略：

  1. 第一个人进入房间打开袋子 A，如果 a=1 或 a=10，则直接报告。否则如果 a \in [2,5]，则在白板上写数字 1，是 [6,9] 则写数字 2。
  2. 第二个人看到 1 或 2 查看 b。考虑白板上原先是数字 1，如果 b \in [1,2]\cup[5,10] 则可以直接报告，否则在黑板上写数字 3。考虑白板上原先是数字 2，如果 b \in [1,6]\cup[9,10] 则可以直接报告，否则在黑板上写数字 3。
  3. 第三个人进入房间看到数字 3，检查 a，如果发现 a \in [2,5] 则他会知道知道 b \in [3,4]，可以比较 a,b 的大小；如果发现 a \in [6,9] 则他会知道知道 b \in [7,8]，也可以比较 a,b 的大小。

这么做其实相当于花费了 2 个数字的代价把白板上数字值域为 0\sim 3 的问题转化成了两种不同情况下白板上数字值域为 0\sim 1 的问题。受此启发，假设白板上可写的最大数字是 x，可以比较的 a,b 值域为 [1,f(x)]，则 f(x) 和 x 满足如下关系：

f(x) = \max_{i=1}^{x-1} (i \times f(x-i))+2

可以打出如下的表：

::::info[点我查看 x 和 f(x) 在 0 \le x \le 20 的关系] x f(x)
0 2
1 4
2 6
3 10
4 14
5 22
6 32
7 44
8 68
9 98
10 134
11 206
12 294
13 404
14 620
15 884
16 1214
17 1862
18 2654
19 3644
20 5588

::::

这个表中最重要的是如下算式：

\begin{align} f(20) &= 3 \times f(17) + 2 \\ &= 3 \times (3 \times f(14) + 2) + 2 \\ &= 3 \times (3 \times (3 \times f(11) + 2) + 2) + 2 \\ &= 3 \times (3 \times (3 \times (3 \times f(8) + 2) + 2) + 2) + 2 \\ &= 3 \times (3 \times (3 \times (3 \times (3 \times f(5) + 2) + 2) + 2) + 2) + 2 \\ &= 3 \times (3 \times (3 \times (3 \times (3 \times (2 \times f(3) + 2) + 2) + 2) + 2) + 2) + 2 \\ &= 3 \times (3 \times (3 \times (3 \times (3 \times (2 \times (2 \times f(1) + 2) + 2) + 2) + 2) + 2) + 2) + 2 \\ &= 5588 \end{align}

也就是说，对于 x = 20 的问题，只需要将其一级一级向下转化为 x = 17,14,11,8,5,3,1 的问题即可。具体地，钦定 a 和 b 中的一个为主数，值域为 [l_q,r_q]，另一个为副数，值域为 [l_x,r_x]，每次花费 k 个数字的代价将主数是值域先除去两端极值再分割成 k 份，然后主副区间互换向下递归。

::::info[点我查看代码]

#include<bits/stdc++.h>
//#define N 5590
using namespace std;
int maxn = 5588;
int g[] = {2,4,6,10,14,22,32,44,68,98,134,206,294,404,620,1190,1214,1862,3572,3644,5588};
int f[] = {0,1,1,2 ,2 ,2 ,2 ,2 ,3 ,3 ,3  ,3  ,3  ,3  ,3  ,3   ,3   ,3   ,3   ,3   ,3   };
int s[] = {1,4,4,4,7,7,7,10,10,10,13,13,13,16,16,16,18,18,20,20,20};
vector<vector<int> > ans;
// 已经确定另一个东西的值域是 lq~rq，我的值域是 lx~rx 
void solve(int x,int lq,int rq,int lx,int rx,int idx){
    int op_idx = !idx;
    ans[x][0] = idx;
    // 赋值判断大小
    for(int i = lx;i <= lq;++i)ans[x][i] = -1 - idx;
    for(int i = rq;i <= rx;++i)ans[x][i] = -1 - op_idx;
    for(int b = 1;b <= f[20-x];++b){
        int d = s[x] + b - 1;// 我要填入的数字 
        int nlx = lq + 1 + (b-1) * g[20-f[20-x]+1-s[x]],nrx = lq + b * g[20-f[20-x]+1-s[x]];
        for(int i = nlx;i <= nrx;++i)ans[x][i] = d;
        solve(d,nlx,nrx,lq,rq,!idx);
    }
}

vector<vector<int> > devise_strategy(int N){
    ans.resize(21);
    for(int i = 0;i <= 20;++i)ans[i].resize(5590);
    solve(0,1,5588,1,5588,0);
    for(int i = 0;i <= 20;++i){
        while(ans[i].size() != N+1)ans[i].pop_back();
    }
    return ans;
}

::::