题解：P11635 [CTS2025] 通信

· · 题解

本文将介绍 k=6,7 时做到 n 比满分限制 21,25 各多 1 的方法。并且我们将能在 26ms 内将解搜出来。此外我们可以用这个方法搜出 k=8,n=35 的解。

首先感谢 Milmon 老师提出的天才优化方法。

这个题有点阴间。

首先你要明确如果一个点不用前面的通信中获得的信息，只用自己的信息，这个题是违背信息论的。

然后你不断地手玩 n=4,k=2，最终得到了一个策略。并发现一次通信传多个位置的方案就是将这些位置的值二进制编码。

你猜测所有点的方案都是对称的，因为这样好构造，通过一些构造可以构造出来 2,4,6,9,12,16,20。

然后你发现做不下去了。

于是你开始爆搜每一轮新知道的位置的集合，你发现 k=4 时还是搜不出来 n=11。

所以说其实每个点的策略并不对称。

但是你猜测每个点在每一轮获得的位置数量是一定的，这是因为第一轮只能获得 1 个位置的信息，而 n=11 时每轮通信最多传 3 个二进制位，且 10=1+3+3+3。相仿的你可以构造出来 k \in [1,7] 时每一轮每个点获得的位置信息集合大小，注意到 k=6,7 时存在一个位置的冗余，由于前面的通信进行时已知的信息量更少，所以你把他减到第二轮通信上。

于是你去爆搜每个点每轮新获得位置的集合，check 就是判断这个集合能否在重排为序列后，找到对应数量的对应点，且对应点之间不同并在之前知道了需要传递的点的信息，这是一个匹配问题，拆点后跑 Hall 定理比网络流快，因为拆出来的点在枚举中肯定会放在一起。当然网络流需要最后用来构造方案。

你发现还是搜不出答案，所以我们来剪枝。

首先每个点的决策在一轮通信中独立，但是因为决策可能很多我们要放在一起搜，所以可以考虑对每个点的决策记忆化一下是否可行。

然后假若在一轮通信中，一个点怎么也搜不出合法解，那说明上一轮通信错完了，这个时候我们直接回到上一轮通信重新搜。

猜测解的密度很大，于是随机打乱决策顺序去搜。

这个时候如果你没有写挂，你就会发现多换几个随机种子的话，存在一些可以搜出来的随机种子，已经可以通过原题了。

但是我们能做到更好，考虑为啥存在一些种子搜不出来。

通过一些思考你发现寄掉是因为前面的决策不是很好时，后面就会搜完所有决策。

于是你考虑每次只搜索有限次，多去搜索几轮直到搜到答案。就可以随便一个种子都搜出来了。

不过这个没啥用，我们看点有用的优化。

还记得之前给 k=6,7 时第二轮减去的一个位置信息吗，我们尝试把他加回来，但是这样你发现就搜不出来了。

这个时候 Milmon 老师提出了一个很天才的想法，他给每个位置随机赋权为 2^k 后用带权随机决定一个点知道的位置的方法处理第一轮通信就把方案给搜出来了。

这为什么对呢。

因为你考虑最苛刻的第二轮，需要每个点都知道足够的信息以保证可以将一个位置重复 4 次以传递 4 个二进制位，那如何做到这点呢？

你发现给一些点赋上 2^k 且总和接近 n 的权值后，每个点期望出现次数与我们要求的就大差不差了，这个时候你发现选取合适的种子就可以搜出解了，但是这样太慢了，怎么办？

我们考虑搜出一组合适的随机权值，这里我用的是 8,8,2,2,2,1，固定这个权值去带权随机决定每个点知道的位置，再加上前面提到的每次只搜有限次多搜几次的优化，此时已经可以在给定的程序运行时间限制内搜出方案，无需将方案打表。并且我们做到了 k=6,n=22 和 k=7,n=26。也就是 1,4,4,4,4,4,4。

我的实现

如果你不想爆标，单纯想过题，那么我们在种子合适的情况下可以以非常快的速度搜出解。

具体可以看我的另一份实现

你发现 k=6,n=22 搜的太慢了，还能不能更牛？

答案是可以。

你考虑所有的问题让第二轮有解，通过一些观察可以发现第二轮有解的充要条件是知道某个位置信息的位置数量前 5 多的位置，知道其信息的位置数量分别大于等于 8,8,4,2,1，除去自己知道自己的信息，也就是我们每个位置，假若将其在第一轮通信后获得的信息所代表的位置写成一个序列，出现次数前 4 多的数出现次数分别大于等于 7,7,3,1，考虑先随机出这四个数，然后分别安排好位置，给其他位置随机一个数后再打乱序列看看是不是符合一个点知道的不是自己的信息，不符合就重新随直到符合，按这样的方式生成第一轮的策略，可以在无视随机种子优劣的情况下比较稳定的在 1s 内跑出 k=6,n=22 以及 k=7,n=26 的解，如果挑选一下种子，则可以在 26ms 内跑出解。

我的实现

同时在 k=8 时，可以在 1min 内跑出 n=35 的解，也就是 1,4,4,5,5,5,5,5，这里再次感谢 Milmon 老师搭建了一个可以测试 n=35 的平台。

我的实现，hydro 比较慢跑了比较久，我本地只用了 1min 就跑出了解

但是我这个做法一个比较大的问题是前面的搜索其实不是很优，不太能搜出 k=8,n=36，但是 Milmon 老师前面的搜索实现的很优秀，可以搜出 k=8,n=36 以及 k=9,n=41。

还遗留了一个问题：k=9,n=42 能搜出来吗？