[CF 325E]The Red Button解题报告

题意:

给一个0~N-1的图,点i向点(2*i)%N和点(2*i+1)%N连有向边。求从0到0的哈密尔顿回路。

(怎么又是一道哈密尔顿回路)


做法:

首先明确一点:如果N是奇数那么无解。
为什么无解呢?原因很简单:0的唯一入边是int(N/2),但N-1的唯一入边也是int(N/2)。例如,当N=5时,0的唯一入边是2(0->0的自环不算),而4的唯一入边也是2(4->4的自环不算)。那么问题来了,哈密尔顿回路里时2->0还是2->4呢……显然都不行,所以无解。

然后看N是偶数的情况。
下面为了方便起见,一律省略%N。例如,当我说点X+1的时候,我其实想说的是(X+1)%N。
这时候有一个性质:X和X+N/2连的两条出边都是一样的。为什么呢?这是显然的……都是2X和2X+1.
那么我们先做一个简单的DFS:不走访问过的的点,尽量沿着2X这条边走,不行就沿着2X+1走。
例如当N=8的时候:
从0开始:0->1->2->4->0
从3开始:3->6->5->3
从7开始:7->7
形成了三个环。那么问题来了:一定成若干个环吗?
官方题解中不加证明地使用了“一定成环”的条件。我们在这里证明一下:

假设当前有若干个环和一条链(当前DFS的链)。链是从h开始走到x,我们现在在x。
如果x的某条出边能走,那当然很好,我们接着走就行了。
但是问题来了——如果duang的一声,我们突然发现,x的两条出边指向的点都被访问过了,怎么办?
x的两条出边分别指向2x和2x+1.而除了x,还有什么点能指向这两个点呢?x+N/2.
x+N/2在上面所说的,“若干个环和一条链”中显然只能出现一次,假设它的后继是2x。
那么2x+1是怎么被访问的呢?作为x的后继吗?这不科学,因为x之前未出现过。
所以真相只有一个——2x+1=h。即,它不是被访问,而是被作为DFS的起点遍历到的。
那么x->h,就形成了一个环。然后我们愉快地再找下一个未被访问过的点,就找到了一个新的h,算法继续。
综上,最终的结果一定是若干个环。

如果只有一个环,那当然很好,这就是我们要找的哈密尔顿回路了。
如果有不止一个环呢?官方题解中说,必然有某个数x,使得x和x+N/2在不同的环上。
官方题解把这个结论的证明作为练习留给了读者……_(:з」∠)_我们在此来证明一下。

反设结论不成立,即所有的x和x+N/2所在环都相同。
我们从某个x开始。假如x和x+N/2在同一个环A上。
由于它们的出边都是2x和2x+1,于是2x和2x+1都在环A上。
同理,4x和4x+1和4x+2和4x+3都在环A上。
同理,8x~8x+7都在环A上。
……
这样的“连续段”的长度最终会不小于N,这时我们就得到,0~N-1全部在环A上。
也就是说A是唯一的环,和环数>=2矛盾。
所以必然有某个x和x+N/2在不同的环上。

现在我们得到了若干个环,还有某个x使得x和x+N/2在不同的环上。接下来怎么办呢?
假设x的后继是2x,那么x+N/2的后继必然是2x+1.
我们只需要简单地将x的后继改成2x+1,x+N/2的后继改成2x,就能将这两个环合并起来。
以上面的N=8为例:1在第一个环上,而5在第二个环上。1的后继是2,而5的后继是3.
我们将1的后继改成3,同时5的后继改成2,就变成了:
0->1->3->6->5->2->4->0
这样环的个数就减一了。
如此往复持续下去,直到只剩下一个环,就形成了我们想要的哈密尔顿回路。

那么问题来了:怎么写这个算法呢?
官方题解中给的算法是DFS:如果在x处走了2x,DFS后发现x+N/2没有被访问,就把x的后继改成2x+1.
是不是看上去有点奇怪……其实有一种非常简单的写法,其主要代码是这样的:
其原理是这样的:假如在成功DFS(2x)之后,发现2x+1仍然没有被访问,那么显然x+N/2在另外一个环中。设2x在环A中,2x+1在环B中。我们直接沿着2x+1走,其效果就是沿着B走了一圈,由于我们从x+N/2的后继开始走,所以最终一定以x+N/2结束。走完之后,ans数组中存放的就是:先沿着B走一圈,再接着在A上走。这时将x放在ans的开头,就起到了前面所说的,切换x的后继以减少圈数的目的。
以N=8为例:
三个环如下图:

DFS的过程如下图:

虚线代表“被替换的部分”。最开始0->1->2->4走了一圈,走完ans={4},回溯到2时发现5能接着走,于是就走了5->3->6,走完ans={6,4},回溯到3时发现7能接着走,于是走了7,走完ans={7,6,4},然后回溯到3,ans={3,7,6,4},回溯到5,ans={5,3,7,6,4},回溯到2,ans={2,5,3,7,6,4},回溯到1,ans={1,2,5,3,7,6,4},回溯到0,ans={0,1,2,5,3,7,6,4}。

代码:

发表评论

电子邮件地址不会被公开。 必填项已用*标注