CSL 的拼图

第一行有一个整数 n，表示拼图的维数。

第二行有 n 个整数 $d_1, d_2, \ldots, d_n$ ，分别表示每一维的大小。

下面 $2 \times \prod_{i = 1}^n d_i$ 行，每行有 n 个整数：第 $2\cdot i - 1$ 行表示第 i 块拼图的初始位置 $(a_{i,1}, a_{i,2}, \ldots, a_{i, n})$ ，第 $2\cdot i$ 行表示第 i 块拼图的目标位置 $(b_{i,1}, b_{i,2}, \ldots, b_{i, n})$ ，保证不会有多个拼图在同一初始位置或目标位置。

最后一行有一个整数 t，表示 CSL 要求的步数。

$1 \leq n \leq 10$
$\prod\limits_{i = 1}^n d_i \leq 10 ^ 6$
$1 \leq a_{i, j}, b_{i, j} \leq d_j$
$0 \leq t \leq 2 \cdot 10 ^ 6$

C++14(g++5.4) 解法, 执行用时: 7ms, 内存消耗: 504K, 提交时间: 2019-04-03 19:42:32

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int a[1000005],b[1000005],m[1000005],d[15]={1},t,c,n,len=1;
bool mark[1000005];
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&d[i]);
		len*=d[i];
	}
	for(int i=0;i<len;i++){
		for(int j=1;j<=n;j++){
			scanf("%d",&t);
			a[i]=a[i]*d[j]+t-1;
		}
		for(int j=1;j<=n;j++){
			scanf("%d",&t);
			b[i]=b[i]*d[j]+t-1;
		}
	}
	for(int i=0;i<len;i++)m[a[i]]=i;
	int loop=0;
	for(int i=0;i<len;i++)
	if(!mark[i]){
		int j=i;
		while(!mark[j]){
			mark[j]=1;
			j=m[b[j]];
		}
		loop++;
	}
	scanf("%d",&t);
	t=len-loop-t;
	if(t>0||t&1)puts("NO");
	else puts("YES");
    return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 7ms, 内存消耗: 752K, 提交时间: 2020-04-18 00:12:23

#include<bits/stdc++.h>
using namespace std;
map<string, int> mp;

int main()
{
    int n, i, j, m=1, t, num=0;
    cin>>n;
    int d[n];
    for(i=0; i<n; i++)
    {cin>>d[i];m*=d[i];}
    getchar();
    string a[m], b[m];
    for(i=0; i<m; i++)
    {
        getline(cin, a[i]);
        mp[a[i]]=i;
        getline(cin, b[i]);
    }
    cin>>t;
    for(i=0; i<m; i++)
    {
        if(mp[a[i]]==mp[b[i]]) continue;
        n=mp[b[i]];
        swap(a[i], a[n]);
        swap(mp[a[i]], mp[a[n]]);
        num++;
    }
    if(num==t||(t>num&&(t-num)%2==0)) cout<<"YES";
    else cout<<"NO";
    return 0;
}

详情