[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.
是不是看上去有点奇怪……其实有一种非常简单的写法，其主要代码是这样的：
void DFS(int x){
	vis[x]=true;
	if(!vis[(x*2)%N]) DFS((x*2)%N);
	if(!vis[(x*2+1)%N]) DFS((x*2+1)%N);
	ans.push_front(x);//在实际代码中其实是push_back，最后倒序输出
}

其原理是这样的：假如在成功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}。

代码：

#include
#include
#include
#include
#include
#include
using namespace std;
const int SIZEN=100010;
vector ans;
int N;
bool vis[SIZEN]={0};
void DFS(int x){
	vis[x]=true;
	if(!vis[(x*2)%N]) DFS((x*2)%N);
	if(!vis[(x*2+1)%N]) DFS((x*2+1)%N);
	ans.push_back(x);
}
int main(){
	freopen("theredbutton.in","r",stdin);
	freopen("theredbutton.out","w",stdout);
	scanf("%d",&N);
	if(N&1){
		printf("-1\n");
	}
	else{
		DFS(0);
		reverse(ans.begin(),ans.end());
		ans.push_back(0);
		for(int i=0;i

发表回复

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