AcWing 奇数码问题

太过爱你忘了你带给我的痛 2021-11-10 02:30 294阅读 0赞

## AcWing 奇数码问题 ##

### Description ###

*  你一定玩过八数码游戏，它实际上是在一个3×3的网格中进行的,1个空格和1~8这8个数字恰好不重不漏地分布在这3×3的网格中。
    
    例如：
    
        5 2 8
        1 3 _
        4 6 7
    
    在游戏过程中，可以把空格与其上、下、左、右四个方向之一的数字交换（如果存在）。
    
    例如在上例中，空格可与左、上、下面的数字交换，分别变成：
    
        5 2 8       5 2 _      5 2 8
        1 _ 3       1 3 8      1 3 7
        4 6 7       4 6 7      4 6 _
    
    奇数码游戏是它的一个扩展，在一个n×n的网格中进行，其中n为奇数，1个空格和1~\\(n^2\\)−1
    
    这\\(n^2\\)−1个数恰好不重不漏地分布在n×n的网格中。空格移动的规则与八数码游戏相同，实际上，八数码就是一个n=3的奇数码游戏。
    
    现在给定两个奇数码游戏的局面，请判断是否存在一种移动空格的方式，使得其中一个局面可以变化到另一个局面。

### Input ###

*  多组数据，对于每组数据：
    
    第1行输入一个整数n，n为奇数。接下来n行每行n个整数，表示第一个局面。再接下来n行每行n
    
    个整数，表示第二个局面。局面中每个整数都是0~\\(n^2\\)−1之一，其中用0代表空格，其余数值与奇数码游戏中的意义相同，保证这些整数的分布不重不漏。

### Output ###

*  对于每组数据，若两个局面可达，输出TAK，否则输出NIE。

### Data Size ###

*  1≤n<500

### Sample Input ###

>     3
>     1 2 3
>     0 4 6
>     7 5 8
>     1 2 3
>     4 5 6
>     7 8 0
>     1
>     0
>     0

### Sample Output ###

>     TAK
>     TAK

### 题解： ###

*  晃眼一看仿佛是道搜索题，但其实是找规律题。
 *  为了方便描述，我们把这个二维图形拉成一维的图形叫做序列
 *  当你左右移动空格时，显然序列不变
 *  当你上下移动空格时，相当于某个数于它前/后边的n-1个数交换了位置
 *  **发现结论：若两序列相等，逆序对奇偶性一定相同。**
 *  上述结论的证明是一大版数学证明，要说我也不会=.=
 *  对于此题，n为奇数，那么n-1就为偶数。**因为变化前的逆序对在变化后肯定不是逆序对**，所以假设变化前逆序对个数是偶数，那么变化后逆序对的个数是(偶数 - 偶数 = 偶数)偶数，假设变化前逆序对个数是奇数，那么变化后逆序对的个数是(偶数 - 奇数 = 奇数)奇数。所以对于此题，一个序列不管怎么变化，它的奇偶性是不会变的。所以不用实际操作去变化它，只需要判断两初始序列的奇偶性即可。

#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #define lowbit(x) (x & (-x)) #define N 505 * 505 using namespace std; int n, cnt, ans1, ans2; int a[N], b[N], c[N], d[N]; int read() { int x = 0; char c = getchar(); while(c < '0' || c > '9') c = getchar(); while(c >= '0' && c <= '9') {x = x * 10 + c - '0'; c = getchar();} return x; } int find(int x) { return lower_bound(c + 1, c + 1 + cnt, x) - c; } int ask(int pos) { int r = 0; while(pos >= 1) { r += d[pos]; pos -= lowbit(pos); } return r; } void update(int pos, int val) { while(pos <= n * n - 1) { d[pos] += val; pos += lowbit(pos); } } int main() { while(scanf("%d", &n) == 1) { cnt = 0; for(int i = 1; i <= n * n; i++) { int t = read(); if(t) a[++cnt] = t; } cnt = 0; for(int i = 1; i <= n * n; i++) { int t = read(); if(t) b[++cnt] = t; } memset(d, 0, sizeof(d)); cnt = 0; for(int i = 1; i < n * n; i++) c[++cnt] = a[i]; sort(c + 1, c + 1 + cnt); cnt = unique(c + 1, c + 1 + cnt) - c - 1; ans1 = 0; for(int i = 1; i < n * n; i++) { int t = find(a[i]); update(t, 1); ans1 += i - ask(t); } memset(d, 0, sizeof(d)); cnt = 0; for(int i = 1; i < n * n; i++) c[++cnt] = b[i]; sort(c + 1, c + 1 + cnt); cnt = unique(c + 1, c + 1 + cnt) - c - 1; ans2 = 0; for(int i = 1; i < n * n; i++) { int t = find(b[i]); update(t, 1); ans2 += i - ask(t); } if((ans1 % 2 == 0 && ans2 % 2 == 0) || (ans1 % 2 != 0 && ans2 % 2 != 0)) printf("TAK\n"); else printf("NIE\n"); } return 0; }

转载于:https://www.cnblogs.com/BigYellowDog/p/11274240.html