[P8234 [AGM 2022 资格赛] 拼图] 题解

· · 题解

前言

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

题目分析

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

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

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

角块

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

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

想更改一个角块的方向，只能让它绕这个拼图一圈。但如果 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;
}