浅谈异或构造——异或类构造题的小技巧

· · 算法·理论

前言

(我们讨论的数字均为非负整数的二进制)

最近机房的小伙伴一遇到构造题就头疼(包括我),于是就写一写我在异或构造方面的感想,大犇们不喜勿喷。

可能这些结论大家都听说过,但是大家能真正知道结论是怎么推导的吗?

正文

众所周知异或在计算机中是很常用的

这道题就是很好的异或构造题

Case 0

a\oplus b\le a+b

上来先给个小结论,这个结论大家肯定都听说过,证明也很简单。

对于每一位,若 ab 同时取 1,则加法会产生进位,而异或不会,异或只会直接变成 0,所以就算没有位 ab 同时取 1,也只是 a\oplus b=a+b,但一旦有了进位,会有 a\oplus b<a+b

接下来的证明也会像这样,我不会非常非常像数学一样严谨的证明因为我不会,但是大家应该也能理解为什么会有结论。

真正的正文……

先来看看几个小的结论。

以下令 g(x)x 的首位 1 的值(比如 g(5)=4g(11)=8),f(x)=2\times g(x)-1,即 f(x) 就是让 x 的 0 位变为 1(不包括前导零)。

Case 1

第一眼看到是不是炸了?别怕,还有更难的

通过上面的结论,有 a\oplus b\le a+b,所以我们只需要令 a\oplus b=a+b=A 就行了,显而易见,只要让 aAb0 就行了。

是不是非常简单?

Case 2

我们想让和最大,只需要在 X 的 1 位上让 ab 任意一个取 1,0 位上让 ab 都取 1 就行。

给出构造:a=f(X)\oplus Xb=f(X)

这样能保证 a\oplus b=f(X)\oplus X\oplus f(X)=X,也能通过贪心证明这样的和是最优的。

Case 3

第一眼看上去是不是很不对劲? a\oplus b 最小?

我们先假设 A 是个偶数吧,这样我们很快就想到——两个相同的数异或起来等于 0,所以我们可以让 ab 都取 \frac{A}{2},这样 a\oplus b 就等于 0 了。

但是 A 不是一个偶数呢?还是平分 A 一个数向上取整一个数向下取整吗?如果这样的话 A 是 15 之类的数上面的方法异或值不就很大了吗?

我的回答是:是的。

因为 \lfloor\frac{A}{2}\rfloor 相当于二进制中 A 右移一位,\lceil\frac{A}{2}\rceil 就相当于二进制中 A 右移一位再加 1,所以这两个数的前面有些位的数字是一样的,这样那些位的异或值就是 0。

那如果不一样的位呢?

我们让 a=\lfloor\frac{A}{2}\rfloorb=\lceil\frac{A}{2}\rceil,设从前往后第 i 位数 ab 不一样,可以证明 b 的第 i+1 位到最后一位都是 0,所以我们不管后面怎么微调 a\oplus b 的值都是这个定值,我太菜了不会证

综上所述,我们可以让 a=\lfloor\frac{A}{2}\rfloorb=\lceil\frac{A}{2}\rceil,这样为最优。

Case 4

到这才讲这个确实有点唐了

因为 a\oplus b\le a+b,所以我们可以让 a+b=a\oplus b,即让 a=Xb=0

做个小结,以上四个小结论我命名为定值取值问题,是不是肥肠简单?

下面来讲一下给出三个数的范围 m,求三个数的异或最值情况下和最值的构造方法(两个数的读者自己推),可能需要读者的纸笔。

接下来直接令 a,b,c\in[0,m]X=a\oplus b\oplus cA=a+b+cf(x)g(x) 同上。

Case 5

一上来就就来了一个一眼题吗?

显然,如果 m 满足 m=f(m) 显然让 a=b=c=m 就行了。

读者可以自己写下一个二进制的 m 然后跟着下面给出的构造写出 Xabc,需要按最后一位对齐。

我们有 X=f(m)a=mb=m\oplus g(m)c=f(m)\oplus g(m)

是不是很神奇?我们来看看为什么这样取值是最优的。

首先要满足 X 最大,所以直接让 X=f(m)

如果令 a=mbc 就是“异或值为定值,和最大”的问题,可参照上面的构造,首先若 a<g(m),但因为 X=f(m) 的,所以肯定 bc 其中一个大于等于 g(m) 的,所以我们可以让 bca 交换,此时 a 还是 大于等于 g(m) 的。

但是为什么 a 一定要取到 m 呢?

因为我们先考虑只有两个数 ab 的情况,此时 X=f(m),所以 b=f(m)\oplus a,但是现在有 3 个数,相当于多了一个数,此时只要 b0 的位,就可以让 bc 的这个位都取 1,这样异或值没变,但是和变大了,所以我们只有两个数时让 b 的 0 位多一点,c 来的时候就能多加一点,又因为 b=f(m)\oplus a,只需要让 a 的 1 位多一点就行,但是又因为 a\ge g(m)a\le m 的,所以就算你想 1 的位最多,a 也最多能取到 m

证完了,能理解吧?

Case 6

同上,自己写数字。

构造出 X=0a=b=mc=0

!!!是不是很惊讶?这原来真的是对的!

但是感觉这很假啊,为什么 ab 不舍去最高位让 c 参与进来?这样不会更优吗?

事实上是不会的,数学大犇或许可以自己证明

首先设这个 mh 位,则 ab 会大于等于 2^{h-1},即 a+b\ge 2^h,因为 X=0,就算 ab 舍去最高位让 c 参与进来的和最多也是 2\times\sum^{h-2}_{i} 2^i=2^h-2,因为 2^h>2^h-2,所以 ab 不舍去最高位让 c 参与进来会更优。

Case 7

显然可以让后面的数两两成对,变成一样的数,这样的异或不会改变,然后再进行以上的构造。

为什么这样会优?

因为上面已经保证了 X 是最优的,两两成对不会改变异或,但可以增加和的值,所以会把 A 变得更大,显然更优。

后记

非常推荐这道题,运用了上面说的构造方法。

现在先讲到这里了,我现在也不知道要写什么,可能未来还要补充。

谢谢各位大犇的阅读,给个赞吧,毕竟写了两个半小时。