题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5821
A: 4 6 5 9
B: 5 6 9 4
以上两个数列A和B，问你可以通过交换A中数的位置实现A变成B数列吗？
解决方法：把A中每个值应该放在位置的左边写出,对应如下
A: 4 6 5 9
mov: 4 2 1 3(表示应该放的位置)
然后把（4,2,1,3）排一下序得到1 2 3 4正好与原先遍历A数组的循序1 2 3 4相同（即1=1,2=2,3=3,4=4）所以可以实现
那么本题目则是对于每个query的可交换区间内的坐标进行排序，操作完所有的query，如果mov序列可以为（1,2,3,4）则可以实现，则Yes，否则No
#include <bits/stdc++.h> using namespace std; typedef pair<int, int> P; typedef long long LL; #define INF 0x3f3f3f3f #define PI acos(-1) #define MAX_N 10000 //#define LOCAL int A[1005], B[1005]; int ab[1005]; int vis[1005]; P p[1005]; int main() { #ifdef LOCAL freopen("b:\\data.in.txt", "r", stdin); #endif int T; scanf("%d", &T); while(T--) { memset(vis, 0, sizeof(vis)); memset(ab, 0, sizeof(ab)); int n, q; scanf("%d%d", &n, &q); int cnt = 0; for(int i = 1; i <= n; i++) { scanf("%d", &A[i]); } for(int i = 1; i <= n; i++) { scanf("%d", &B[i]); } for(int i = 1; i <= n; i++) { for(int j = 1; j <= n; j++) { if(vis[j] != 0) continue; if(B[j] == A[i]) { ab[i] = j; vis[j]++; break; } } } for(int i = 0; i < q; i++) { scanf("%d%d", &p[i].first, &p[i].second); sort(ab+p[i].first, ab+p[i].second+1); } // for(int i = 1; i <= n; i++) // cout << ab[i] << " "; // cout << endl; bool ans = 0; for(int i = 1; i <= n; i++) { if(ab[i] != i) { ans = 1; break; } } if(ans) cout << "No" << endl; else cout << "Yes" <<endl; } return 0; }
