如果令 a=m,b 和 c 就是“异或值为定值,和最大”的问题,可参照上面的构造,首先若 a<g(m),但因为 X=f(m) 的,所以肯定 b 或 c 其中一个大于等于 g(m) 的,所以我们可以让 b 或 c 与 a 交换,此时 a 还是 大于等于 g(m) 的。
但是为什么 a 一定要取到 m 呢?
因为我们先考虑只有两个数 a 与 b 的情况,此时 X=f(m),所以 b=f(m)\oplus a,但是现在有 3 个数,相当于多了一个数,此时只要 b 有 0 的位,就可以让 b 和 c 的这个位都取 1,这样异或值没变,但是和变大了,所以我们只有两个数时让 b 的 0 位多一点,c 来的时候就能多加一点,又因为 b=f(m)\oplus a,只需要让 a 的 1 位多一点就行,但是又因为 a\ge g(m) 且 a\le m 的,所以就算你想 1 的位最多,a 也最多能取到 m。
证完了,能理解吧?
Case 6
同上,自己写数字。
构造出 X=0,a=b=m,c=0。
!!!是不是很惊讶?这原来真的是对的!
但是感觉这很假啊,为什么 a、b 不舍去最高位让 c 参与进来?这样不会更优吗?
事实上是不会的,数学大犇或许可以自己证明。
首先设这个 m 有 h 位,则 a、b 会大于等于 2^{h-1},即 a+b\ge 2^h,因为 X=0,就算 a、b 舍去最高位让 c 参与进来的和最多也是 2\times\sum^{h-2}_{i} 2^i=2^h-2,因为 2^h>2^h-2,所以 a、b 不舍去最高位让 c 参与进来会更优。
Case 7
显然可以让后面的数两两成对,变成一样的数,这样的异或不会改变,然后再进行以上的构造。
为什么这样会优?
因为上面已经保证了 X 是最优的,两两成对不会改变异或,但可以增加和的值,所以会把 A 变得更大,显然更优。