题目传送门:https://ac.nowcoder.com/acm/contest/551/H
题目描述
输入描述:
第一行有一个整数 n,表示拼图的维数。
第二行有 n 个整数 d1,d2,…,dnd1,d2,…,dn,分别表示每一维的大小。
n∏i=1di≤106∏i=1ndi≤106
1≤ai,j,bi,j≤dj1≤ai,j,bi,j≤dj
0≤t≤2⋅1060≤t≤2⋅106
输出描述:
如果 CSL 可以用恰好 t 步复原,在一行输出 "YES",否则输出 "NO"。
输入
复制1 1 1 1 1
输出
复制NO
输入
复制2 2 2 1 2 2 1 1 1 2 2 2 1 1 2 2 2 1 1 2
输出
复制YES
解题思路:
类似于前面的那道一维的交换题目 CSL的魔法
不过这里是多维的,怎样形成映射呢?
用 string !
AC code:
1 #include <bits/stdc++.h> 2 #define INF 0x3f3f3f3f 3 #define LL long long 4 #define inc(i, j, k) for(int i = j; i <= k; i++) 5 #define rep(i, j, k) for(int i = j; i < k; i++) 6 #define mem(i, j) memset(i, j, sizeof(i)) 7 #define gcd(i, j) __gcd(i, j) 8 #define pb push_back 9 using namespace std; 10 const int MAXN = 2e5+10; 11 12 string st[MAXN], ed[MAXN], str; 13 map<string, int>vis; 14 int N, t; 15 int main() 16 { 17 int num; 18 scanf("%d", &N); 19 int len = 1; 20 inc(i, 1, N){ 21 scanf("%d", &num); 22 len*=num; 23 } 24 // printf("len %d\n", len); 25 26 getchar(); 27 // /* 28 inc(i, 1, len){ 29 getline(cin, str); 30 st[i] = str; 31 vis[str] = i; 32 getline(cin, str); 33 ed[i] = str; 34 } 35 scanf("%d", &t); 36 LL ans = 0; 37 inc(i, 1, len){ 38 if(st[i] != ed[i]){ 39 ans++; 40 int tp = vis[ed[i]]; 41 swap(st[i], st[tp]); 42 vis[st[i]] = i; 43 vis[st[tp]] = tp; 44 } 45 if(ans > t) break; 46 } 47 if(ans > t) puts("NO"); 48 else if((t-ans)%2 == 0) puts("YES"); 49 else puts("NO"); 50 // */ 51 return 0; 52 }