P6892 [ICPC2014 WF]Baggage 做题记录

有一无穷长的流水线 $a$，初始时 $\forall i\le0\text{ 和 } i>2n ,a_i=0$。否则，若 $i$ 为奇数，则 $a_i=2$；若 $i$ 为偶数，则 $a_i=1$。也就是说，$a_i=2$ 和 $a_i=1$ 是交替出现的。

现需要进行若干次 如下 操作，使得 $a$ 中的所有 非零元素 为 连续 的一段且所有的 $1$ 均在 $2$ 前面。

选择两个位置 $p$ 和 $q$，满足 $a_p\ne0,a_{p+1}\ne0$ 且 $a_q=a_{q+1}=0$，将 $a_q$ 设为 $a_p$，$a_{q+1}$ 设为 $a_{p+1}$，并且将 $a_p$ 和 $a_{p+1}$ 均设为 $0$。输出时将此操作表示为 p to q（$p$ 和 $q$ 是具体的值）。

最小化操作步数，并输出操作序列，出题人将用 $\text{Special Judge}$ 来评判您的答案的正确性。

$3\le n\le 100$。

容易证明操作次数下界是 $n$，因为设相邻两个类型相同的包裹有 $t$ 组，初始 $t=0$，最终要令 $t=2n-2$。每次操作取出包裹时 $t$ 不会增加，而放回则最多增加 $2$，并且第一次操作只能令 $t$ 增加 $1$，所以操作次数下界为 $1+\lceil \frac{2n-3}{2}\rceil=n$。

手模一下 $3\le n\le 7$ 的情况：

OOOOOOBABABA
OOOOABBOOABA
OOOOABBBAAOO
OOAAABBBOOOO

OOOOOOOOBABABABA
OOOOOOABBABABOOA
OOOOOOABBAOOBBAA
OOOOOOAOOABBBBOO
OOOOOOAAAABBBBOO

OOOOOOOOOOBABABABABA
OOOOOOOOABBABABABOOA
OOOOOOOOABBAOOBABBAA
OOOOOOOOABBAABBOOBAA
OOOOOOOOAAAAABBBBBOO

OOOOOOOOOOOOBABABABABABA
OOOOOOOOOOABBABABABABOOA
OOOOOOOOOOABBABABAOOBBAA
OOOOOOOOOOABBOOABAABBBAA
OOOOOOOOOOABBAAABOOBBBAA
OOOOOOOOOOAOOAAABBBBBBAA
OOOOOOOOOOAAAAAABBBBBBOO

OOOOOOOOOOOOOOBABABABABABABA
OOOOOOOOOOOOABBABABABOOABABA
OOOOOOOOOOOOABBABAOOBBAABABA
OOOOOOOOOOOOABBABAABBBAABOOA
OOOOOOOOOOOOABBAOOABBBAABBAA
OOOOOOOOOOOOABBAAAABBBOOBBAA
OOOOOOOOOOOOAOOAAAABBBBBBBAA
OOOOOOOOOOOOAAAAAAABBBBBBBOO

不难发现，$n>3$ 时，第一步总是 2n-2 to -1，并且最后包裹总是停留在 $[-1,2n-2]$。那么考虑构造 $n\ge 8$ 的操作序列：

OOO...OOOBA[BABABA...BABA]BABA
OOO...OABBA[BABABA...BABA]BOOA
OOO...OABBA[OOBABA...BABA]BBAA

此时若我们递归构造，将中括号内变成 AAA...AB...BBBOO，那么可以这样构造接下来的操作序列：

OOO...OABBA[AAA...AB...BBBOO]BBAA
OOO...OAOOA[AAA...AB...BBBBB]BBAA
OOO...OAAAA[AAA...AB...BBBBB]BBOO

不难发现，这样在递归下去之前用了两次操作，递归完之后又用了两次操作，递归到到子问题 $n$ 减少了 $4$，所以总共恰好使用了 $n$ 次操作。

边界条件显然是 $3\le n\le 7$，因为此时递归到到子问题 $n$ 就会 $\le 3$，不满足最后包裹停留在 $[-1,2n-2]$。

代码如下：

#include <iostream>
#include <cstdio>

using namespace std;

inline void mov(int x,int y)
{
	printf("%d to %d\n",x,y);
}

void inline run3(int l)
{
	mov(l+1,l-2);
	mov(l+4,l+1);
	mov(l+2,l-4);
}

void inline run4(int l)
{
	mov(l+5,l-2);
	mov(l+2,l+5);
	mov(l-1,l+2);
	mov(l+6,l-1);
}

void inline run5(int l)
{
	mov(l+7,l-2);
	mov(l+2,l+7);
	mov(l+5,l+2);
	mov(l-1,l+5);
	mov(l+8,l-1);
}

void inline run6(int l)
{
	mov(l+9,l-2);
	mov(l+6,l+9);
	mov(l+1,l+6);
	mov(l+5,l+1);
	mov(l-1,l+5);
	mov(l+10,l-1);
}

void inline run7(int l)
{
	mov(l+7,l-2);
	mov(l+4,l+7);
	mov(l+11,l+4);
	mov(l+2,l+11);
	mov(l+8,l+2);
	mov(l-1,l+8);
	mov(l+12,l-1);
}

inline void slove(int l,int r)
{
	if((r-l+1)/2==3)
	{
		run3(l);
		return;
	}
	if((r-l+1)/2==4)
	{
		run4(l);
		return;
	}
	if((r-l+1)/2==5)
	{
		run5(l);
		return;
	}
	if((r-l+1)/2==6)
	{
		run6(l);
		return;
	}
	if((r-l+1)/2==7)
	{
		run7(l);
		return;
	}
	mov(r-2,l-2);
	mov(l+2,r-2);
	slove(l+4,r-4);
	mov(l-1,r-5);
	mov(r-1,l-1);
}

int main()
{
	int n;
	scanf("%d",&n);
	slove(1,n*2);
	return 0;
}