拿到这种题，首先不要慌张 。
这道题有 很明显 的规律性 ： BABABABA …
那么这道题 再难也不难 。
手玩。手玩的时候要有清晰的目标，因为手玩的目的是让我们直观地感受规律，发现规律。毫无目的的手玩只是在浪费时间。
尤其是这种规律性强的题目，手玩的结果往往具有普遍性，可以推而广之。
当题目比较复杂时，手玩很有可能出错 。 这个时候要结合暴力程序进行验证。
当然这都不是最核心的。本题最核心的是 递归构造 。
而且这个构造 比较复杂，不那么明显 ，特别是这种带有 最小步数 限制的构造题目，往往考验创造性思维。
以这道题为例，操作顺序是很重要的，我们要先把中间的还原，才能把两边的也还原。
最后优美的结论是，操作次数恰好为 n n n 次。
如果你执着于先将两边的复原的话，复原左右 4 4 4 个 则需要 5 5 5 步。
失之毫厘，差之千里 啊 ！
#include<bits/stdc++.h>
using namespace std;
int n;
void p(int x,int y) {
printf("%d to %d\n",x,y);
}
void solve(int l,int n) {
if(n==4) {
p(l+7,l),p(l+4,l+7),p(l+1,l+4),p(l+8,l+1);
return;
}
if(n==5) {
p(l+9,l),p(l+4,l+9),p(l+7,l+4),p(l+1,l+7),p(l+10,l+1);
return;
}
if(n==6) {
p(l+11,l),p(l+8,l+11),p(l+3,l+8),p(l+7,l+3),p(l+1,l+7),p(l+12,l+1);
return;
}
if(n==7) {
p(l+9,l),p(l+6,l+9),p(l+13,l+6),p(l+4,l+13),p(l+10,l+4),p(l+1,l+10),p(l+14,l+1);
return;
}
int r=l+2*(n+1)-1;
p(r-2,l),p(l+4,r-2);
solve(l+4,n-4);
p(l+1,r-5),p(r-1,l+1);
}
int main() {
while(scanf("%d",&n)!=-1) {
if(n==3) {
p(2,-1),p(5,2),p(3,-3);
}
else {
solve(-1,n);
}
printf("\n");
}
}
暴力代码 （用于 n=3,4,5,6,7） 时的特殊构造 。
#include<bits/stdc++.h>
using namespace std;
int s[15]={0,0,2,1,2,1,2,1,2,1,2,1},t[15]={1,1,1,1,1,2,2,2,2,2};
int tx[15],ty[15];
void dfs(int x) {
if(x>5) {
int flg=1; for(int i=0;i<10;i++) if(s[i]!=t[i]) flg=0;
if(flg) {
int r[15]={0,0,2,1,2,1,2,1,2,1,2,1};
for(int i=1;i<=5;i++) {
swap(r[tx[i]],r[ty[i]]);
swap(r[tx[i]+1],r[ty[i]+1]);
for(int j=0;j<12;j++) {
if(r[j]==1) printf("%c",'A');
else if(r[j]==2) printf("%c",'B');
else printf(" ");
}
printf("\n");
}
exit(0);
}
return;
}
for(int i=0;i<12;i++) {
for(int j=i+2;j<12;j++) {
if(s[i]&&s[i+1]&&!s[j]&&!s[j+1] || !s[i]&&!s[i+1]&&s[j]&&s[j+1]) {
tx[x]=i,ty[x]=j;
swap(s[i],s[j]),swap(s[i+1],s[j+1]);
dfs(x+1);
swap(s[i],s[j]),swap(s[i+1],s[j+1]);
}
}
}
}
int main() {
dfs(1);
}
嗯，我们最后还需要补上一个 不重要的 最小步数的证明
有
2
(
n
?
1
)
2(n-1)
2(n?1) 对相邻的类型相同的包裹，而我们插入一对最多增加 2 对相邻的包裹，同时因为第一次操作只能插在左右两端，所以只会增加一对，因此步数下界为
?
2
n
?
3
2
?
+
1
=
n
\lceil\frac{2n-3}{2}\rceil +1=n
?22n?3??+1=n 。
