N数码问题
简介
我们先引入一个简单的问题.
首先，这里的拼图游戏是滑块拼图，类似于华容道，游戏者通过移动拼图块将拼图还原为初始形状。关于拼图，常见的有3x3，4x4，多的以至于有16x16不等。一般块数越多拼图越复杂。
如图所示,我们可以用空格与其上下左右相邻的位置的方块进行交换.给你两个局面,问这两个局面能不能互相转化.
分析
这个就是著名的N数码问题,我们为了严谨,在之后的讨论中都是N*M的矩阵.
先上结论:
(状态A忽略空格时求出的逆序对数量+状态A将空格移动到状态B所需的行数*(A的列数%2+1))%2 == (状态B忽略空格时求出的逆序对的数量)%2 如果成立,那么就可以转化.
看着有些复杂
-
如果列是奇数
(状态A忽略空格时求出的逆序对数量)%2 == (状态B忽略空格时求出的逆序对的数量)%2 -
如果列是偶数
(状态A忽略空格时求出的逆序对数量+状态A将空格移动到状态B所需的行数)%2 == (状态B忽略空格时求出的逆序对的数量)%2
简单证明
注:下文提到的”逆序对”无特殊说明都是指不算入空格在内的.
我们发现,在一行内部,无论怎样左右交换,都不会影响整个数组的逆序对数量.
所以我们就只用关心竖直交换给逆序对带来的影响.我们将空格上下移动一行,除了交换的数外,会影响M-1个其他的数的逆序对.
我们假设M-1个其他数中,有p个比当前数(我们称之为cur)小,有q个比cur大.
假设交换之前的逆序对数量是num,假设交换是cur向下交换.
对于M是奇数,M-1是偶数的情况来说
p和q要么都是奇数,要么都是偶数.cur与空格交换之后,cur的逆序对会增加q;然后对于q个数来说,逆序对数不变;对于p个数来说,逆序对数共减少了p;
则总共的变化是 q-p,根据上文的讨论,这是个偶数,所以挪动一次不影响整体逆序对的的奇偶性.
对于M是偶数,M-1是奇数的来说
p和q中有一个是奇数,一个是偶数,则q-p一定是奇数,则一次上下的挪动一定会改变奇偶性,然而我们可以这样想:我们一上来就将A的空格挪至和B相同的位置,然后无论怎么挪动,如果A能挪动到和B局面完全一样的话,这个空格一定会再次回到这个位置,也就是从这个位置出发,再回到这个位置就一定需要经历偶数次挪动(水平也是偶数,竖直也是偶数),所以从奇偶性角度来看,竖直方向的挪动就是A直接挪到B的空格的位置所需的操作
综上所述,仅M是偶数时,才需要考虑竖直方向的挪动 .
HDU 6620
AC代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include<bits/stdc++.h>
#define sc scanf
#define pr printf
#define pb push_back
#define ll long long
#define fi first
#define se second
#define pii pair<long long ,long long >
using namespace std;
#define MAXN 600000+100
int c[MAXN];
int n = 15;
int lowbit(int x) {
return x & (-x);
}
void add(int x, int y) {
while (x <= n) {
c[x] += y;
x += lowbit(x);
}
}
ll sum(int x) {
ll ans = 0;
while (x > 0) {
ans += c[x];
x -= lowbit(x);
}
return ans;
}
int a[20];
int main() {
int T;
scanf("%d", &T);
while (T--) {
for (int i = 0; i <= 16; ++i) {
c[i] = 0;
}
int x;
int pos = 1;
int ans = 0;
for (int i = 1; i <= 16; ++i) { // 注意这个循环,0不能算入在内
scanf("%d", &a[i]);
if (a[i]) {
add(a[i], 1);
ans += pos - 1 - sum(a[i] - 1);
++pos;
} else {
x = (i - 1) / 4;
}
}
int step = 3 - x; // 这就是算竖直方向的挪动次数
// printf("%d %d\n", step, ans);
if ((step + ans) % 2) {
printf("No\n");
} else {
printf("Yes\n");
}
}
return 0;
}
