vjudge
第一天，相当于构造一个函数 \(f(x, y)\) 表示一个人看到自己的数 \(x\) 和右边的数 \(y\) 写下的数字。
要求 \(f(x, y) \ne f(y, z)(x \ne y, y \ne z)\) 且 \(f(x, y)\) 的值域尽可能小。
考虑一些跟二进制有关的东西。因为 \(f(x, y) \ne f(y, x)\)，即 \(f\) 没有交换律，所以那些对称的运算都被淘汰了。
于是我们可以令 \(f(x, y)\) 为最低的 \(i\) 使得二进制下 \(x\) 的第 \(i\) 位为 \(0\)，\(y\) 的第 \(i\) 位为 \(1\)。这样使得值域降到 \(\log n\) 且显然满足 \(f(x, y) \ne f(y, z)\)。
但是有一个问题就是可能找不到这样的 \(i\)。一个解决的办法是对 \(x\) 进行映射，\(x \rightarrow h(x)\)。
于是问题就转化为如何找到一个映射关系 \(h\)，满足对于任意 \(x \ne y\)，都存在 \(f(x, y)\)。
因为对于一个数 \(u\)，既可能作为 \(x\)，也可能作为 \(y\)，所以 01 的地位是一样的，二进制下 \(u\) 的 01 数量一致。于是可以构造 \(h(x)\) 为一个长度为 \(2k\) 的 01 串，恰好有 \(k\) 个 0、\(k\) 个 \(1\)。
不难这样构造一定是可行的，\(h(x)\) 只需要互不相同即可。
取 \(k = 10\) 即可使 \(f(x, y)\) 压缩到 \(20\)。
第二天可以看到左右两边，相当于可以做两次迭代。
令 \(x, y, z\) 分别代表左边、手上、右边的数，\(g(x, y, z) = f(f(x, y), f(y, z))\) 即可。可以把数字压到 \(4\) 种。
第三天压不动了，但是减少一种就行。把颜色 \(3\) 换成左右两边的 mex 即可。
总结
妥妥的构造题，人类智慧。
要想到太困难了，虽然写了一些思维链，但还是很困难。