自动搬运

查看原文

来自洛谷，原作者为

	smarthehe sbarthehe

搬运于2025-08-24 22:15:37，当前版本为作者最后更新于2021-02-15 21:27:57，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

本人菜，没做出来，搜题解了……这里记述的是网上大神的题解思路。

首先我们声明一个结论：答案长度 $\geq n+1$。这个结论我不会证，但可以暴力小数据验证其正确性。

接下来给出一个答案长度严格为 $n+1$ 的构造。思想为利用一些手段缩小问题规模，并在回溯时调整。

在 $n>6$ 的时候，我们控制其状态形如 11111...00000...__00，也即 【$n$ 个 1】+【$n-2$ 个 0】+【$2$ 个空格】+【$2$ 个 0】。

对于这样一种状态进行如下调整：

1__11...00000...1100（第 2,3 位填补空缺）

1001[11...00000...__00]1100（除去首末 4 位，倒数 3,4 位填补空缺）

可以看到这两步过后两侧的 4 位中共有 4 个 0 和 4 个 1，同时中间的倒数 3,4 位空缺，所以中间是一个大小为 $n-4$ 的子问题。

递归处理该问题，我们希望在回退时状态形如 1010...10__1010...，也即由完整的 10 循环构成，中间挖去一个 10。

如果我们能使子问题达成该状态，则作如下处理：

当前状态为 1001[1010...10__1010...]1100。

1001[1010...]1__0（倒数 2,3 位填补空缺）

10__[1010...]1010（第 3,4 位填补空缺）

可以发现处理完以后我们使得原问题也成为了形如 1010...10__1010... 的状态。

现在已经解决了递归求解过程中的调整问题，只需要说明边界。

如果问题已经被缩小到 $n \leq 6$ 的规模，我们希望在达到时的状态如下：

$n=3$：11100__0

$n=4$：1111000__0

$n=5$：1111100__000

$n=6$：111111000__000

对于这个需求，可以在到达 $n \leq 6$ 前的最后一步调整进行特判加以解决。

然后给出这些边界情况对应的调整方法：

$n=3$：

11100__0 $\rightarrow$ 1__00110 $\rightarrow$ 1010__10

$n=4$：

1111000__0 $\rightarrow$ __11000110 $\rightarrow$ 101__00110 $\rightarrow$ 101010__10

$n=5$：

1111100__000 $\rightarrow$ 11__10011000 $\rightarrow$ 1100100110__ $\rightarrow$ 1__010011010 $\rightarrow$ 101010__1010

$n=6$：

111111000__000 $\rightarrow$ 1__11100011000 $\rightarrow$ 10011100011__0 $\rightarrow$ 10011100__1010 $\rightarrow$ 10011__0101010 $\rightarrow$ 10__1010101010

可以看到，这些调整方法都能够用恰好 $n-1$ 步调整到需要的状态。

应用递归求解前，需要先通过一步交换形成倒数 3,4 位为空位的初始状态，求解后得到的情形会是 10__1010... 这样一个第 3,4 位为空位的亚终止状态，需要再做一步交换得到终止状态。

在递归求解过程中，每次花费 4 步使得问题规模减小 4，在边界处花费的步数是 $n-1$，还有 2 步额外步数，因此总步数为 $n+1$。

另外，对于初始 $n\leq 6$ 如上做法不成立，需要特判。可以实现一个暴力或手玩出结果，此处按下不表，只给出最终的步骤：

$n=3$：2 6 4 7

$n=4$：样例

$n=5$：2 7 11 3 8 11

$n=6$：1 6 12 9 3 10 13

于是我们得到了完整的解法。

代码：

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
void solve(int st,int len)
{
	if(len<=6)
	{
		if(len==3) printf("%d %d ",st+1,st+4);
		if(len==4) printf("%d %d %d ",st,st+3,st+6);
		if(len==5) printf("%d %d %d %d ",st+2,st+10,st+1,st+6);
		if(len==6) printf("%d %d %d %d %d ",st+1,st+11,st+8,st+5,st+2);
		return;
	}
	if(len-4>6) printf("%d %d ",st+1,st+len*2-6);
	else
	{
		if(len==7||len==8) printf("%d %d ",st+1,st+len*2-5);
		else printf("%d %d ",st+1,st+len*2-7);
	}
	solve(st+4,len-4);
	printf("%d %d ",st+len*2-1,st+2);
}
int main()
{
	int n;
    scanf("%d",&n);
    printf("%d\n",n+1);
    if(n==3) printf("2 6 4 7");
    else if(n==4) printf("1 4 8 6 9");
    else if(n==5) printf("2 7 11 3 8 11");
    else if(n==6) printf("1 6 12 9 3 10 13");
    else printf("%d ",n*2-1),solve(1,n),printf("%d ",n*2+1);
    return 0;
}

另外这是一份输出步骤详细信息的代码，可能会对读者有帮助：

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int N=2e5+5;
char s[N];
int n,stp,blk;
void mov(int x)
{
	printf("step %d:%s\n",stp,s+1);
	swap(s[x],s[blk]),swap(s[x+1],s[blk+1]);
	blk=x;stp++;
}
void solve(int st,int len)
{
	if(len<=6)
	{
		if(len==3) mov(st+1),mov(st+4);
		if(len==4) mov(st),mov(st+3),mov(st+6);
		if(len==5) mov(st+2),mov(st+10),mov(st+1),mov(st+6);
		if(len==6) mov(st+1),mov(st+11),mov(st+8),mov(st+5),mov(st+2);
		return;
	}
	if(len-4>6) mov(st+1),mov(st+len*2-6);
	else
	{
		if(len==7||len==8) mov(st+1),mov(st+len*2-5);
		else mov(st+1),mov(st+len*2-7);
	}
	solve(st+4,len-4);
	mov(st+len*2-1),mov(st+2);
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++) s[i]='1';
    for(int i=n+1;i<=n*2;i++) s[i]='0';
    s[n*2+1]=s[n*2+2]='_';
    blk=n*2+1;
    if(n==3) mov(2),mov(6),mov(4),mov(7);
    else if(n==4) mov(1),mov(4),mov(8),mov(6),mov(9);
    else if(n==5) mov(2),mov(7),mov(11),mov(3),mov(8),mov(11);
    else if(n==6) mov(1),mov(6),mov(12),mov(9),mov(3),mov(10),mov(13);
    else mov(n*2-1),solve(1,n),mov(n*2+1);
    printf("step %d:%s\n",stp,s+1);
    return 0;
}