自动搬运

查看原文

来自洛谷，原作者为

	larsr loser

搬运于2025-08-24 22:37:09，当前版本为作者最后更新于2024-05-14 12:44:14，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

前言

当时随机跳了一道题就找到了这道题，发现只有一个通过并且没有题解，就想做一下然后再写个题解。

题目分析

这道题其实就是拼魔方……。

首先注意到每个边缘块的侧面和中心块的上下面都不相同，那么角块最终的位置是固定的。

我们除了要让角块弄到对应的位置，还要让边缘块和角块的方向正确（简单说就是上下面和中心块的上下面对应）。角块的位置的方向都要正确，而边缘块只需要方向正确即可。那么我们可以先把角块的位置和方向弄正确（不用管边缘块），再把边缘块的方向弄正确（此时不能弄乱角块），因为这样弄方便一些。

角块

首先把角块放入正确的位置，瞎搞就行。

下面考虑如何把角块方向弄正确。每一个操作会更改两个角块的方向，如果方向不正确的角块数量为奇数，那肯定无解。

想更改一个角块的方向，只能让它绕这个拼图一圈。但如果 $n$ 为偶数，那么就无法更改一个角块的方向（因为要操作偶数次所以方向不变）。

可以选择两个角块，一块把它们的方向弄正确。假设这两个角块的编号为 $i,j(i < j)$。初始时它们之间的角块为 $i,i+1,i+2,\ldots,j-2,j-1,j$，然后将 $i$ 移到最右边，那么就变成了 $i+1,i+2,\ldots,j-2,j-1,j,i$，再将 $j$ 移到右边，变成 $j,i+1,i+2,\ldots,j-2,j-1,i$。除了 $i,j$ 其他的角块都经过了两次操作，那么它们的方向不变。接着从 $i,j$ 的另外一个方向做同样的操作，此时它们都绕拼图转了一圈，方向也变了。

最大操作次数为 $2n^2$。

边缘块

对于两条相邻的边 $i$ 和 $i+1$，可以重复三次操作边 $i$ 和边 $i+1$，此时它们旁边的三个角块被操作次数都是四次，而边缘块被操作了三次。此时角块不变，两个边缘块方向变了。

通过这个操作可以把边缘块方向弄正确，但边缘块方向不正确的数量为奇数时，不可能弄正确。

证明：每次操作会更改边缘块方向不正确的数量的奇偶性，也会更改角块的排列的逆序对的奇偶性。所以它们中肯定有一个是奇数，那么就无解。

Code

#include<cstdio>
#include<algorithm>
#define N 110
#define M 100010
using namespace std;
int n;
void exx()
{
	printf("-1\n");
	exit(0);
}
struct PT
{
	//init
	int coltp, colbt, ct[N], cl[N], cr[N], cb[N], et[N], es[N], eb[N];
	//new
	int cz[N], cc[N], ez[N];
	//ls
	int g[N], cp[N][2];
	int tot = 0, ans[M];
	void read()
	{
		scanf("%d%d", &coltp, &colbt);
		for(int i = 1; i <= n; i++)scanf("%d%d%d%d", ct + i, cl + i, cr + i, cb + i);
		for(int i = 1; i <= n; i++)scanf("%d%d%d", et + i, es + i, eb + i);
		for(int i = 1; i <= n; i++)
		{
			if(et[i] == coltp && eb[i] == colbt)ez[i] = 1;
			else if(et[i] != colbt || eb[i] != coltp)exx();
			g[es[i]] = i;
			if(ct[i] == coltp && cb[i] == colbt)cz[i] = 1;
			else if(ct[i] != colbt || cb[i] != coltp)exx();
			cp[i][0] = cl[i];
			cp[i][1] = cr[i];
		}
		for(int i = 1; i <= n; i++)
		{
			cp[i][0] = g[cp[i][0]];
			cp[i][1] = g[cp[i][1]];
			if(!cz[i])swap(cp[i][0], cp[i][1]);
			cc[i] = cp[i][1];
			if(cp[i][1] - cp[i][0] != 1 && cp[i][0] - cp[i][1] != n - 1)exx();
		}
	}
	void mov(int x)
	{
		ez[x] ^= 1;
		if(x < n)
		{
			swap(cz[x], cz[x + 1]);
			swap(cc[x], cc[x + 1]);
			cz[x] ^= 1;
			cz[x + 1] ^= 1;
		}
		else
		{
			swap(cz[x], cz[1]);
			swap(cc[x], cc[1]);
			cz[x] ^= 1;
			cz[1] ^= 1;
		}
		ans[++tot] = x;
	}
	void print()
	{
		printf("%d\n", tot);
		for(int i = 1; i <= tot; i++)printf("%d ", ans[i]);
		printf("\n");
	}
}pt;
int main()
{
	scanf("%d", &n);
	pt.read();
	for(int i = 1; i <= n; i++)
	{
		int now = 0;
		for(int j = 1; j <= n; j++)
			if(pt.cc[j] == i)
			{
				now = j;
				break;
			}
		for(int j = now - 1; j >= i; j--)
			pt.mov(j);
	}
	if(n % 2 == 0)
	{
		for(int i = 1; i <= n; i++)
			if(!pt.cz[i])exx();
	}
	else
	{
		int sum = 0;
		for(int i = 1; i <= n; i++)
			if(!pt.cz[i])sum++;
		if(sum % 2 == 1)exx();
		for(int i = 1; i <= n; i++)
			if(!pt.cz[i])
			{
				int j = i + 1;
				while(pt.cz[j])j++;
				for(int k = i; k < j; k++)
					pt.mov(k);
				for(int k = j - 2; k >= i; k--)
					pt.mov(k);
				for(int k = i - 1; k; k--)
					pt.mov(k);
				for(int k = n; k >= j; k--)
					pt.mov(k);
				for(int k = j + 1; k <= n; k++)
					pt.mov(k);
				for(int k = 1; k < i; k++)
					pt.mov(k);
			}
	}
	for(int i = 1; i < n; i++)
		if(!pt.ez[i])
		{
			pt.mov(i);
			pt.mov(i + 1);
			pt.mov(i);
			pt.mov(i + 1);
			pt.mov(i);
			pt.mov(i + 1);
		}
	if(!pt.ez[n])exx();
	pt.print();
	return 0;
}