2023-10-16

洛谷 P8491 [IOI2022] 囚徒挑战题解

IOI 特有的乱搞题。

Step 1（ $m=52$ ）

首先有一个朴素的按位比较的做法，每一个人留下自己当前查看的是 A 还是 B，
查看到第 $x$ 位的值是多少。如果上一个人查看的是 A，则查看 B 的对应位并比较；否则查看 A 的下一位。

使用二进制，需要 $m=13\times 2\times 2 = 52$ 。

Step 2（ $m=39$ ）

注意到查看 B 的人并不需要留下这一位 B 的值，只需要告诉下一个人自己查看了 B 的某一位并让下一个人去查看 A 的下一位即可。

需要的 $m$ 下降到 $13\times (2+1)=39$ 。

Step 3（ $m=32$ ）

并不一定要是二进制。

改成三进制， $m$ 下降到 $8\times (3+1)=32$ 。

Step 4（ $m=24$ ）

注意到一个人查看到的是整个数值而不是这个数值的某一位，于是可以交错进行比较：第一个人先查看 A 的第 $8$ 位，并留下「自己看了第 $8$ 位」和「第 $8$ 位 A 的值」两个信息；第二个人看到上述信息后查看 B，如果第 $8$ 位不一样则直接完成比较；否则留下「自己看了第 $7$ 位」和「第 $7$ 位 B 的值」两个信息；第三个人看到上述信息后查看 A，如果第 $7$ 位不一样则直接完成比较；否则留下「自己看了第 $6$ 位」和「第 $6$ 位 A 的值」两个信息，以此类推。

这样的话，直接从位数就能够推断出值是哪个袋子的对应位的值，于是需要的信息量就只有位数 $\times $ 值的种类数。于是我们得到 $m=8\times 3=24$ 。

Step 5（ $m=22$ ）

观察一下样例，可以发现：由于保证两个数不同，当我们比较到最后一位的时候，最后一位是 $0$ 或 $2$ 的情况都不需要传回去继续比较。

于是我们需要传出去的情况就减少了两种，得到 $m=7\times 3+1=22$ 。

Step 6（ $m=20$ ）

考虑充分利用这个顶到两头可以结束比较的性质。

经过一些尝试，可以发现 $3\times 3\times 3\times 3\times 62=5022>5000$ 。

于是我们定义一个数 $x$ 的第 $1,2,3,4,5$ 位分别是 $x\bmod 62,\lfloor\frac{x}{62}\rfloor\bmod 3,\lfloor\frac{x}{62\times 3}\rfloor\bmod 3,\lfloor\frac{x}{62\times 3^2}\rfloor\bmod 3,\lfloor\frac{x}{62\times 3^3}\rfloor\bmod 3$ 。

比较第 $5,4,3,2$ 位的时候和 Step 4 是一样的。我们需要 $12$ 个状态，分别代表：

A 的第 $5$ 位是 $0/1/2$ ；
B 的第 $4$ 位是 $0/1/2$ ；
A 的第 $3$ 位是 $0/1/2$ ；
B 的第 $2$ 位是 $0/1/2$ 。

我们最终会查到 A 的第 $2$ 位与 B 的第 $2$ 位相同，并同时获知 A 的第 $1$ 位（记作 $A_1$ ，B 同理记作 $B_1$ ）。

此时我们可以利用顶到两头就结束的性质，如下：

若 $A_1=0$ 或 $A_1=61$ ，则结束比较。
否则按 $A_1\in [1,20],A_1\in [21,40],A_1\in [41,60]$ 分为 $3$ 个状态传给下一个人。

下一个人接收这个状态后查询 $B_1$ ：

若 $B_1=0$ 或 $B_1=61$ ，则结束比较。
若 $B_1$ 与 $A_1$ 不处于同一个长度为 $20$ 的段里面，则结束比较。
若 $(B_1-1)\bmod 20=0$ 或 $=19$ ，则结束比较。
否则按 $(B_1-1)\bmod 20\in [1,6],(B_1-1)\bmod 20\in [7,12],(B_1-1)\bmod 20\in [13,18]$ 分为 $3$ 个状态传给下一个人。

再下一个人接收这个状态后类似地迭代一遍。具体来说，查询 $A_1$ ：

若 $(A_1-1)\bmod 20=0$ 或 $=19$ ，则结束比较。
若 $(A_1-1)\bmod 20$ 与 $(B_1-1)\bmod 20$ 不处于同一个长度为 $6$ 的段里面，则结束比较。
若 $((A_1-1)\bmod 20-1)\bmod 6=0$ 或 $=5$ ，则结束比较。
否则按 $((A_1-1)\bmod 20-1)\bmod 6\in [1,2],((A_1-1)\bmod 20-1)\bmod 6\in [3,4]$ 分为 $2$ 个状态传给下一个人。

再下一个人接收这个状态后查询 $B_1$ ，由于此时段长为 $2$ ，所以一定能够讨论出大小关系。

这样我们就得到了 $m=3\times 4+3+3+2=20$ ，可以通过本题。

inline vector <int> Construct(int idx, const int &N) {
	vector <int> res;
	if (idx == 0) {
		// Initial
		// Check A, return A/62/3/3/3 + 1
		res.push_back(0);
		for (int i = 1;i <= N;i++) res.push_back(i / 62 / 3 / 3 / 3 + 1);
	} else if (idx >= 1 && idx <= 3) {
		// A/62/3/3/3 == idx - 1
		// Check B, return result if different, otherwise return B/62/3/3 %3 + 4
		res.push_back(1);
		for (int i = 1;i <= N;i++) {
			if (i / 62 / 3 / 3 / 3 > idx - 1) res.push_back(-1);
			else if (i / 62 / 3 / 3 / 3 < idx - 1) res.push_back(-2);
			else res.push_back(i / 62 / 3 / 3 % 3 + 4);
		}
	} else if (idx >= 4 && idx <= 6) {
		// B/62/3/3 %3 == idx - 4
		// Check A, same as above, return A/62/3 %3 + 7
		res.push_back(0);
		for (int i = 1;i <= N;i++) {
			if (i / 62 / 3 / 3 % 3 > idx - 4) res.push_back(-2);
			else if (i / 62 / 3 / 3 % 3 < idx - 4) res.push_back(-1);
			else res.push_back(i / 62 / 3 % 3 + 7);
		}
	} else if (idx >= 7 && idx <= 9) {
		// A/62/3%3 == idx - 7
		// Check B, same as above, return B/62 % 3 + 10
		res.push_back(1);
		for (int i = 1;i <= N;i++) {
			if (i / 62 / 3 % 3 > idx - 7) res.push_back(-1);
			else if (i / 62 / 3 % 3 < idx - 7) res.push_back(-2);
			else res.push_back(i / 62 % 3 + 10);
		}
	} else if (idx >= 10 && idx <= 12) {
		// B/62%3 == idx - 10
		// Check A, return result if different
		// if same, return result if A % 62 == 0 or A % 62 == 61
		// otherwise return (A % 62 - 1) / 20 + 13
		res.push_back(0);
		for (int i = 1;i <= N;i++) {
			if (i / 62 % 3 > idx - 10) res.push_back(-2);
			else if (i / 62 % 3 < idx - 10) res.push_back(-1);
			else {
				if (i % 62 == 0) res.push_back(-1);
				else if (i % 62 == 61) res.push_back(-2);
				else res.push_back((i % 62 - 1) / 20 + 13);
			}
		}
	} else if (idx >= 13 && idx <= 15) {
		// (A % 62 - 1) / 20 == idx - 13
		// Check B, return result if B % 62 == 0 or B % 62 == 61
		// otherwise return result if (B % 62 - 1) / 20 != idx - 13
		// otherwise return result if (B % 62 - 1) % 20 == 0 / 19
		// otherwise return ((B % 62 - 1) % 20 - 1) / 6 + 16
		res.push_back(1);
		for (int i = 1;i <= N;i++) {
			if (i % 62 == 0) res.push_back(-2);
			else if (i % 62 == 61) res.push_back(-1);
			else {
				if ((i % 62 - 1) / 20 < idx - 13) res.push_back(-2);
				else if ((i % 62 - 1) / 20 > idx - 13) res.push_back(-1);
				else {
					if ((i % 62 - 1) % 20 == 0) res.push_back(-2);
					else if ((i % 62 - 1) % 20 == 19) res.push_back(-1);
					else res.push_back(((i % 62 - 1) % 20 - 1) / 6 + 16);
				}
			}
		}
	} else if (idx >= 16 && idx <= 18) {
		// ((B % 62 - 1) % 20 - 1) / 6 == idx - 16
		// Check A, return result if (A % 62 - 1) % 20 == 0 / 19 
		// otherwise return result if ((A % 62 - 1) % 20 - 1) / 6 != idx - 16
		// otherwise return result if ((A % 62 - 1) % 20 - 1) % 6 == 0 / 5
		// otherwise return (((A % 62 - 1) % 20 - 1) % 6 - 1) / 2 + 19
		res.push_back(0);
		for (int i = 1;i <= N;i++) {
			if ((i % 62 - 1) % 20 == 0) res.push_back(-1);
			else if ((i % 62 - 1) % 20 == 19) res.push_back(-2);
			else {
				if (((i % 62 - 1) % 20 - 1) / 6 < idx - 16) res.push_back(-1);
				else if (((i % 62 - 1) % 20 - 1) / 6 > idx - 16) res.push_back(-2);
				else {
					if (((i % 62 - 1) % 20 - 1) % 6 == 0) res.push_back(-1);
					else if (((i % 62 - 1) % 20 - 1) % 6 == 5) res.push_back(-2);
					else res.push_back((((i % 62 - 1) % 20 - 1) % 6 - 1) / 2 + 19);
				}
			}
		}
	} else if (idx >= 19 && idx <= 20) {
		res.push_back(1);
		for (int i = 1;i <= N;i++) {
			if (((i % 62 - 1) % 20 - 1) % 6 == 0) res.push_back(-2);
			else if (((i % 62 - 1) % 20 - 1) % 6 == 5) res.push_back(-1);
			else {
				if ((((i % 62 - 1) % 20 - 1) % 6 - 1) / 2 > idx - 19) res.push_back(-1);
				else if ((((i % 62 - 1) % 20 - 1) % 6 - 1) / 2 < idx - 19) res.push_back(-2);
				else {
					if ((((i % 62 - 1) % 20 - 1) % 6 - 1) % 2 == 0) res.push_back(-2);
					else res.push_back(-1);
				}
			}
		}
	}
	return res;
}

std::vector<std::vector<int> > devise_strategy(int N) {
	vector <vector <int> > ans;
	for (int i = 0;i <= 20;i++) ans.push_back(Construct(i, N));
	return ans;
}

Step 1（m=52m=52m=52）

Step 2（m=39m=39m=39）

Step 3（m=32m=32m=32）

Step 4（m=24m=24m=24）

Step 5（m=22m=22m=22）

Step 6（m=20m=20m=20）