M30178: 数字华容道（Easy Version）

merge sort, binary indexed tree, http://cs101.openjudge.cn/practice/30178/

总时间限制：2000ms，单个样例点时间限制：1000ms，内存限制：262144kB

数字华容道的游戏玩法：在一个 $n\times n$ 的方格中放置 $1$ 到 $n^2-1$ 的所有数字（每个数字占据一空间），剩下一个空格（输入中用 $0$ 表示）。每次可以将与空格相邻的几个数字平移到空格处。游戏目标是尽可能快的将给定盘面还原到初始状态。（初始状态就是 $1$ 到 $n^2-1$ 按顺序填充每一行，空格在右下角的盘面） 例如一个可能的初始盘面是：

1 2 3 4
5 6 7 8
9 10 11 12
15 13 14 0

你的目标是通过平移数字，将盘面变成

1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 0

的样子。 一天，小K正准备玩数字华容道，但是他不小心把盘面中的数字小方格都打翻在地了。虽然他将所有的数字都乱序排入了盘面中，但是这样的盘面是不一定有解的，所以他想请你判断一下这个盘面是否有解。

输入

第 $1$ 行：一个整数 $n$ ，$(2\le n\le 1000)$ 。（你就不要问小K是怎么把一百万个小方格捡起来的了） 第 $2$ 行到第 $n+1$ 行： $n$ 个整数，表示盘面。

输出

如果盘面有解，输出yes，否则输出no

样例输入

4
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 0

样例输出

yes

（注：此题与Hard Version唯一的不同之处在于Easy Version的每一个输入文件都只有一个样例，而Hard Version有多个。）

这是一个经典的数字华容道（N-Puzzle）的可解性判定问题。

核心思路

判断盘面是否有解，依赖于逆序对（Inversions）的数量和空格（0）的位置。

1. 将盘面展开为一维数组：忽略空格（0），将剩下的 $N^2-1$ 个数字按顺序排成一列。
2. 计算逆序对 ($I$)：在展开的数组中，如果前面的数字大于后面的数字，则称为一个逆序对。计算总数 $I$。
3. 判定规则：
   • 情况 1：$N$ 是奇数
     • 如果逆序对数量 $I$ 是偶数，则有解。
     • 否则无解。
   • 情况 2：$N$ 是偶数
     • 计算空格（0）所在的行号（从上往下数，0-indexed），设为 $r$。
     • 计算空格距离底部的行数：$dist=(N-1)-r$。
     • 如果 $(I+dist)$ 是偶数，则有解。
     • 否则无解。

算法复杂度

由于 $N$ 最大为 1000，直接双重循环计算逆序对的时间复杂度为 $O(N^4)$，计算量达到 ${10}^{12}$，会超时。我们需要使用 树状数组 (Binary Indexed Tree / Fenwick Tree) 或 归并排序 将计算逆序对的时间复杂度降低到 $O(N^2\log (N^2))$。

Python 代码实现

def merge_count(arr):
    if len(arr) <= 1:
        return arr, 0
    mid = len(arr) // 2
    left, a = merge_count(arr[:mid])
    right, b = merge_count(arr[mid:])
    merged = []
    i = j = 0
    inv = a + b
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            merged.append(left[i])
            i += 1
        else:
            merged.append(right[j])
            j += 1
            inv += len(left) - i
    merged += left[i:]
    merged += right[j:]
    return merged, inv

def main():
    import sys
    data = sys.stdin.read().split()
    if not data:
        return
    n = int(data[0])
    grid = []
    index = 1
    blank_row = -1
    for i in range(n):
        row = list(map(int, data[index:index+n]))
        index += n
        grid.append(row)
        if 0 in row:
            blank_row = i

    flat = []
    for row in grid:
        for x in row:
            if x != 0:
                flat.append(x)

    _, inv = merge_count(flat)

    if n % 2 == 1:
        ans = "yes" if inv % 2 == 0 else "no"
    else:
        ans = "yes" if (inv + blank_row) % 2 == 1 else "no"
    print(ans)

if __name__ == "__main__":
    main()

import sys

# 定义树状数组类，用于快速计算逆序对
class FenwickTree:
    def __init__(self, size):
        self.tree = [0] * (size + 1)

    def update(self, i, delta):
        while i < len(self.tree):
            self.tree[i] += delta
            i += i & (-i)

    def query(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & (-i)
        return s

def solve():
    # 使用 sys.stdin.read 读取所有输入，处理多行和空格
    input_data = sys.stdin.read().split()
    
    if not input_data:
        return

    iterator = iter(input_data)
    try:
        n = int(next(iterator))
    except StopIteration:
        return

    flat_list = []
    zero_row = -1

    # 读取盘面数据
    # 同时记录 0 所在的行，并构建去除 0 后的扁平数组
    for r in range(n):
        for c in range(n):
            val = int(next(iterator))
            if val == 0:
                zero_row = r  # 记录 0 所在的行号（0-indexed）
            else:
                flat_list.append(val)

    # 计算逆序对
    # 数字范围是 1 到 n*n-1
    max_val = n * n
    bit = FenwickTree(max_val)
    inversions = 0
    
    for i, x in enumerate(flat_list):
        # i 是当前已经遍历过的数字个数
        # bit.query(x) 是当前遍历过的数字中 <= x 的个数
        # i - bit.query(x) 就是当前遍历过的数字中 > x 的个数（即逆序对）
        inversions += (i - bit.query(x))
        bit.update(x, 1)

    # 根据 N 的奇偶性进行判定
    if n % 2 == 1:
        # N 是奇数：逆序对必须是偶数
        if inversions % 2 == 0:
            print("yes")
        else:
            print("no")
    else:
        # N 是偶数：(逆序对 + 0距离底部的行数) 必须是偶数
        dist_from_bottom = (n - 1) - zero_row
        if (inversions + dist_from_bottom) % 2 == 0:
            print("yes")
        else:
            print("no")

if __name__ == "__main__":
    solve()

代码解析

1. 输入处理：使用 sys.stdin.read().split() 一次性读取所有数据，这比 input() 快且能自动处理换行符和空格。
2. 树状数组 (BIT)：
   • update(x, 1)：将数字 x 出现次数加 1。
   • query(x)：查询小于等于 x 的数字出现过多少次。
   • i - query(x)：利用前缀和思想，计算出比当前数字 x 大的已出现数字个数，这正是逆序对的定义。
3. 逻辑判定：
   • 奇数阶：左右移动不改变逆序对，上下移动空格跨越 $N-1$ (偶数) 个数字，逆序对奇偶性不变。目标状态逆序对为 0 (偶数)，所以当前逆序对必须为偶数。
   • 偶数阶：上下移动空格跨越 $N-1$ (奇数) 个数字，逆序对奇偶性改变。每向下移动一行，逆序对奇偶性反转一次。我们需要保证：(当前逆序对 + 将空格移到底部所需的步数) 的奇偶性 == 目标状态(0)的奇偶性。