题解

题面描述

给定一个 $N \times N$ 的二维矩阵，其中包含 $[1,\,N^2]$ 的互不相同正整数。允许的操作为：
每次选择矩阵中的一个元素，将其与其在顺时针螺旋顺序中的下一个元素交换。
目标是通过若干次操作，使矩阵变为“顺时针螺旋递增”顺序，即按照螺旋遍历时，元素依次为 $1,2,3,\dots,N^2$。要求求出最小操作次数，并对 $1000000007$ 取模。

思路

1. 将矩阵按照顺时针螺旋顺序遍历，转化为长度为 $N^2$ 的一维数组 $\text{spiral}$。
2. 最终目标数组为 $[1,2,3,\dots,N^2]$。
3. 每次操作相当于交换数组中相邻的两个元素，而最少操作次数等于数组排列的逆序数数量。
4. 采用树状数组（Binary Indexed Tree）方法可以在 $O(N^2 \log (N^2))$ 的时间内统计逆序数。
   • 对于数组中每个元素 $x$（取值范围为 $[1,\,N^2$），遍历时利用树状数组查询在其前面已经出现的数中，大于 $x$ 的个数，即 $inversions$ += (当前已处理个数 - $query(x)$)。
   • 同时更新树状数组中 $x$ 的计数值。
5. 最终对逆序数结果取模 $1000000007$ 得到答案。

C++

#include <iostream>
#include <vector>
using namespace std;
 
const int MOD = 1000000007;
 
// 树状数组类，用于统计前缀和
struct BIT {
    vector<int> tree;
    int n;
    BIT(int n): n(n), tree(n+1, 0) {}
    
    // 更新树状数组，在位置 idx 加上 val
    void update(int idx, int val) {
        for(; idx <= n; idx += idx & -idx)
            tree[idx] += val;
    }
    
    // 查询前缀和，从 1 查询到 idx
    int query(int idx) {
        int sum = 0;
        for(; idx > 0; idx -= idx & -idx)
            sum += tree[idx];
        return sum;
    }
};
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int N;
    cin >> N;
    vector<vector<int>> matrix(N, vector<int>(N));
    for (int i = 0; i < N; i++){
        for (int j = 0; j < N; j++){
            cin >> matrix[i][j];
        }
    }
    
    // 螺旋遍历提取矩阵中的元素
    vector<int> spiral;
    int top = 0, bottom = N - 1;
    int left = 0, right = N - 1;
    while(top <= bottom && left <= right) {
        // 从左到右
        for(int j = left; j <= right; j++){
            spiral.push_back(matrix[top][j]);
        }
        top++;
        if(top > bottom) break;
        // 从上到下
        for(int i = top; i <= bottom; i++){
            spiral.push_back(matrix[i][right]);
        }
        right--;
        if(left > right) break;
        // 从右到左
        for(int j = right; j >= left; j--){
            spiral.push_back(matrix[bottom][j]);
        }
        bottom--;
        if(top > bottom) break;
        // 从下到上
        for(int i = bottom; i >= top; i--){
            spiral.push_back(matrix[i][left]);
        }
        left++;
    }
    
    // 使用树状数组统计逆序数（最少交换次数）
    int size = spiral.size();
    // 元素取值范围为 [1, N*N]
    BIT bit(N * N);
    long long inversions = 0;
    
    // 从左到右遍历，每个元素统计在其之前已插入的个数中大于它的个数
    for (int i = 0; i < size; i++){
        int x = spiral[i];
        // query(x) 得到前面已经插入的 ≤ x 的数量，因此 (i - query(x)) 即为大于 x 的数量
        inversions = (inversions + (i - bit.query(x))) % MOD;
        bit.update(x, 1);
    }
    
    cout << inversions % MOD << "\n";
    return 0;
}

Python

# 树状数组类，用于统计前缀和
class BIT:
    def __init__(self, n):
        self.n = n
        self.tree = [0] * (n + 1)
    
    # 更新树状数组，在位置 idx 加上 val
    def update(self, idx, val):
        while idx <= self.n:
            self.tree[idx] += val
            idx += idx & -idx
            
    # 查询前缀和，从 1 查询到 idx
    def query(self, idx):
        s = 0
        while idx:
            s += self.tree[idx]
            idx -= idx & -idx
        return s

MOD = 1000000007

def main():
    import sys
    data = sys.stdin.read().strip().split()
    if not data:
        return
    N = int(data[0])
    matrix = []
    index = 1
    for i in range(N):
        row = []
        for j in range(N):
            row.append(int(data[index]))
            index += 1
        matrix.append(row)
    
    # 螺旋遍历提取矩阵中的元素
    spiral = []
    top, bottom = 0, N - 1
    left, right = 0, N - 1
    while top <= bottom and left <= right:
        # 从左到右
        for j in range(left, right + 1):
            spiral.append(matrix[top][j])
        top += 1
        if top > bottom:
            break
        # 从上到下
        for i in range(top, bottom + 1):
            spiral.append(matrix[i][right])
        right -= 1
        if left > right:
            break
        # 从右到左
        for j in range(right, left - 1, -1):
            spiral.append(matrix[bottom][j])
        bottom -= 1
        if top > bottom:
            break
        # 从下到上
        for i in range(bottom, top - 1, -1):
            spiral.append(matrix[i][left])
        left += 1
    
    size = len(spiral)
    bit = BIT(N * N)
    inversions = 0
    # 从左到右遍历，统计当前元素前面大于它的个数
    for i in range(size):
        x = spiral[i]
        inversions = (inversions + (i - bit.query(x))) % MOD
        bit.update(x, 1)
    
    print(inversions % MOD)

if __name__ == "__main__":
    main()

Java

import java.util.*;
import java.io.*;

public class Main {
    static final int MOD = 1000000007;
    
    // 树状数组类，用于统计前缀和
    static class BIT {
        int[] tree;
        int n;
        
        public BIT(int n) {
            this.n = n;
            tree = new int[n + 1];
        }
        
        // 更新树状数组，在位置 idx 加上 val
        public void update(int idx, int val) {
            while(idx <= n) {
                tree[idx] += val;
                idx += idx & -idx;
            }
        }
        
        // 查询前缀和，从 1 到 idx
        public int query(int idx) {
            int sum = 0;
            while(idx > 0) {
                sum += tree[idx];
                idx -= idx & -idx;
            }
            return sum;
        }
    }
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine().trim());
        int[][] matrix = new int[N][N];
        for(int i = 0; i < N; i++){
            String[] parts = br.readLine().trim().split("\\s+");
            for(int j = 0; j < N; j++){
                matrix[i][j] = Integer.parseInt(parts[j]);
            }
        }
        
        // 螺旋遍历提取矩阵中的元素
        ArrayList<Integer> spiralList = new ArrayList<>();
        int top = 0, bottom = N - 1;
        int left = 0, right = N - 1;
        while(top <= bottom && left <= right) {
            // 从左到右
            for(int j = left; j <= right; j++){
                spiralList.add(matrix[top][j]);
            }
            top++;
            if(top > bottom) break;
            // 从上到下
            for(int i = top; i <= bottom; i++){
                spiralList.add(matrix[i][right]);
            }
            right--;
            if(left > right) break;
            // 从右到左
            for(int j = right; j >= left; j--){
                spiralList.add(matrix[bottom][j]);
            }
            bottom--;
            if(top > bottom) break;
            // 从下到上
            for(int i = bottom; i >= top; i--){
                spiralList.add(matrix[i][left]);
            }
            left++;
        }
        
        int size = spiralList.size();
        int[] spiral = new int[size];
        for (int i = 0; i < size; i++){
            spiral[i] = spiralList.get(i);
        }
        
        // 使用树状数组统计逆序数（最少操作次数）
        BIT bit = new BIT(N * N);
        long inversions = 0;
        // 从左到右遍历，对于每个元素统计前面大于它的元素个数
        for (int i = 0; i < size; i++){
            int x = spiral[i];
            inversions = (inversions + (i - bit.query(x))) % MOD;
            bit.update(x, 1);
        }
        
        System.out.println(inversions % MOD);
    }
}

题目内容

给定一个$N*N$的二维矩阵，其中包含$[1，N^2]$的互不相同的正整数。

定义一种操作:

每次可以选择矩阵中的一个元素，将其与其在顺时针螺旋顺序中的下一个元素交换位置

例如: 在$3*3$的矩阵中,

螺旋顺序为从左上角$[0,0]$开始，向右到$[0,2]$，向下到$[2,2]$，向左到$[2,0]$，再向上到$[1,0]$，最 后到中心$[1,1]$。

目标是通过若干次操作，将矩阵变为“顺时针螺旋递增”顺序，即螺旋遍历时元素依次为 $1,2,3,...,N^2$。

求将给定矩阵转换为顺时针螺旋递增顺序所需的最小操作次数。

输入描述

第一行为整数$N$;

接下来$N$行，每行$N$个整数,表示矩阵。

参数范围:

矩阵的N取值范围为$[1,10^3]$；

矩阵中元素的取值范围$[1,N^2]$；

输出描述

一个整数; 表示最小操作次数。

特别注意:

结果可能过大，因此结果需要取模$1000000007$。

例如，计算初始结果为:$1000000008$，请返回$1$。

样例1

输入

2
3 1
2 4

输出

3

说明

根据要求，通过若干次操作得到的目标矩阵为：

$1\ 2$

$4\ 3$

第一次交换,选择$(0,0)$的$3$与螺旋顺序上相邻的$(0,1)$的$1$交换，矩阵为:

$1\ 3$

$2\ 4$

第二次交换,选择$(1,1)$的$4$与螺旋顺序上相邻的$(1,0)$的$2$交换，矩阵为:

$1\ 3$

$4\ 2$

第三次交换，选择$(0,1)$的$3$与螺旋顺序上相邻的$(1,1)$的$2$交换，矩阵为：

$1\ 2$

$4\ 3$

目标达成;

操作次数$3$;

样例2

输入

3
3 2 1
6 5 4
9 8 7

输出

10

说明

解释:根据要求，通过若干次操作得到的目标矩阵为:

$1\ 2\ 3$

$8\ 9\ 4$

$7\ 6\ 5$

开始交换(注意选择螺旋顺序上相邻的交换);

第$1$次交换:

$3\ 2\ 1$

$5\ 6\ 4$

$9\ 8\ 7$

第$2$次交换: $3\ 2\ 1$

$9\ 6\ 4$

$5\ 8\ 7$

第$3$次交换: $3\ 2\ 1$

$6\ 9\ 4$

$5\ 8\ 7$

第$4$次交换:

$3\ 2\ 1$

$6\ 9\ 4$

$8\ 5\ 7$

第$5$次交换:

$3\ 2\ 1$

$8\ 9\ 4$

$6\ 5\ 7$

第$6$次交换:

$3\ 2\ 1$

$8\ 9\ 4$

$6\ 7\ 5$

第$7$次交换:

$3\ 2\ 1$

$8\ 9\ 4$

$7\ 6\ 5$

第$8$次交换:

$3\ 1\ 2$

$8\ 9\ 4$

$7\ 6\ 5$

第$9$次交换:

$1\ 3\ 2$

$8\ 9\ 4$

$7\ 6\ 5$

第$10$次交换:

$1\ 2\ 3$

$8\ 9\ 4$

$7\ 6\ 5$

目标达成;

操作次数$10$;