题解 P5918 【[FJOI2015]金币换位问题】
smarthehe
·
·
题解
本人菜，没做出来，搜题解了……这里记述的是网上大神的题解思路。
首先我们声明一个结论：答案长度 \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=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`
于是我们得到了完整的解法。
代码：
```c++
#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;
}
```
另外这是一份输出步骤详细信息的代码，可能会对读者有帮助：
```c++
#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;
}
```