二进制分组

· · 算法·理论

这玩意来源于玄学

引入

NKOJ9284 奇怪的最短路问题
第一眼看过去……这是可做的？？？既然要求最短路，那至少要有源点和汇点——这个题却让你自己选。首先否定贪心，那么直接确定源点汇点的想法基本就破灭了。我们注意到，其实不需要找到具体的源点和汇点——有个东西叫多源汇最短路。于是有了基本的思路：将点分成两组，以某一组为源点跑最短路算法，求出到其它点距离的最小值即可。这样做刚好可以解决回到起点这种不好处理的情况。问题来了，怎么分组呢？这时候，要请出我们重量级的嘉宾：\color{red}\text{随机化}！直接随机出两组（大小相等），随机到正确的源点和汇点的概率为 25\%，于是假设我们随机 x 次，那么找到答案的概率高达 1-(\frac 34)^x。为保证算法的复杂度，我们可以取 x=15，于是正确率为 1-(\frac 34)^{15}\approx99.7\%，可以通过此题。

本着精益求精的精神，我们开始思考：是否存在一定正确的做法？答案是有的。这便是今天的主题——\color{red}\text{二进制分组}！
分组思路：分别枚举每一个二进制位，将所有当前位相同的分为一组。至于正确性，读者自证不难。

没错，二进制分组就是这么简单粗暴。

分析

二进制分组用来解决上面这类问题：将很多个数分为两组，要求给定的两个数分到不同组，应该怎么分。对于所有不同的两个数，相对应的，他们必然存在某一位不相同。当枚举到这一位时，这两个数自然会分到不同的两组。也就是说，按照每一位进行讨论，最后每两个数都将分到过不同组去。挺巧妙的一个做法，虽然平时没啥用就是了。