题目解析

问题描述

我们有一个 $n \times n$ 的网格，从 $(1,1)$ 走到 $(n,n)$，只能向右或向下。当踏入格子 $(i,j)$ 且 $i \neq j$ 时，交换 $a_i$ 和 $a_j$。目标是使用最多 $2n+4$ 条路径将数组 $a$ 排序为非递减序列。

核心观察

当位于 $(x,x)$ 时，有两种基本移动：

移动 $1$：$(x,x) \rightarrow (x,x+1) \rightarrow (x+1,x+1)$

• 效果：$[\dots, a_x, a_{x+1}, \dots] \rightarrow [\dots, a_{x+1}, a_x, \dots]$
• 即交换相邻两个数

移动 $2$：$(x,x) \rightarrow (x,x+1) \rightarrow (x,x+2) \rightarrow (x+1,x+2) \rightarrow (x+2,x+2)$

• 效果：$[\dots, a_x, a_{x+1}, a_{x+2}, \dots] \rightarrow [\dots, a_{x+2}, a_{x+1}, a_x, \dots]$
• 即交换 $a_x$ 和 $a_{x+2}$

重要性质

设路径前的数组为 $a$，路径后的数组为 $a'$，则：

• $a'_n = a_1$（最后一个元素变成原来的第一个元素）
• $[a'_1, a'_2, \dots, a'_{n-1}]$ 可以通过对 $[a_2, a_3, \dots, a_n]$ 做相邻交换得到，每个数最多交换一次

解题思路

$Step 1$：将最小值放到 $a_1$

如果 $a_1 \neq mn$（$mn$ 是数组最小值），使用路径： $(1,1) \rightarrow (1,p_1) \rightarrow (p_1,p_1) \rightarrow (p_1,n) \rightarrow (n,n)$

其中 $p_1$ 是最小值的位置。这条路径确保 $a_1 = mn$。

$Step 2$：奇偶排序

对子数组 $[a_2, a_3, \dots, a_n]$ 执行奇偶排序：

• 奇数轮：比较 $(a_2,a_3), (a_4,a_5), \dots$
• 偶数轮：比较 $(a_3,a_4), (a_5,a_6), \dots$

每个比较使用移动 $1$ 或移动 $2$ 实现。

$Step 3$：循环移位

执行路径 $(1,1) \rightarrow (1,n) \rightarrow (n,n)$，效果： $[a_1, a_2, \dots, a_n] \rightarrow [a_n, a_{n-1}, a_1, a_2, \dots, a_{n-2}]$

这保证了：

• $mn$ 回到数组头部
• 子数组 $[a_1, \dots, a_{n-1}]$ 循环右移一位

$Step 4$：处理奇偶性

• 若 $n-1$ 是偶数：循环移位不影响奇偶排序
• 若 $n-1$ 是奇数：需要调整比较起点，下一轮从 $(a_3,a_4)$ 开始

完整代码

#include <bits/stdc++.h>
using namespace std;

const int N = 2010;
int T, n, mn, tot;
int a[N];
vector<int> X[N], Y[N];

// 路径1: (1,1)->(1,2)->(2,2)->(2,3)->(3,3)->...
void path1(int num) {
    for (int i = 1; i <= n; i++) {
        X[num].push_back(i), Y[num].push_back(i);
        if (i != n) {
            X[num].push_back(i), Y[num].push_back(i + 1);
            swap(a[i], a[i + 1]);
        }
    }
}

// 路径2: (1,1)->(1,n)->(n,n)
void path2(int num) {
    for (int i = 1; i <= n; i++) {
        X[num].push_back(1), Y[num].push_back(i);
        swap(a[1], a[i]);
    }
    for (int i = 2; i <= n; i++) {
        X[num].push_back(i), Y[num].push_back(n);
        swap(a[i], a[n]);
    }
}

// 行走1: 交换 a[j-1] 和 a[j+1]
void walk1(int j) {
    X[tot].push_back(j - 1), Y[tot].push_back(j);
    X[tot].push_back(j - 1), Y[tot].push_back(j + 1);
    X[tot].push_back(j), Y[tot].push_back(j + 1);
    X[tot].push_back(j + 1), Y[tot].push_back(j + 1);
    swap(a[j - 1], a[j + 1]);
}

// 行走2: 交换 a[j-1] 和 a[j]，再交换 a[j] 和 a[j+1]
void walk2(int j) {
    X[tot].push_back(j - 1), Y[tot].push_back(j);
    X[tot].push_back(j), Y[tot].push_back(j);
    X[tot].push_back(j), Y[tot].push_back(j + 1);
    X[tot].push_back(j + 1), Y[tot].push_back(j + 1);
    swap(a[j - 1], a[j]);
    swap(a[j], a[j + 1]);
}

int main() {
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) 
            scanf("%d", &a[i]);
        
        mn = n;
        tot = 0;
        for (int i = 1; i <= n; i++) 
            mn = min(mn, a[i]);
        
        for (int i = 1; i <= 3 * n; i++) 
            X[i].clear(), Y[i].clear();
        
        // Step 1: 将最小值移到 a[1]
        int p1;
        for (int i = 1; i <= n; i++) 
            if (a[i] == mn) p1 = i;
        
        if (p1 != 1) {
            tot++;
            // (1,1) -> (1,p1)
            for (int i = 1; i <= p1; i++) 
                X[tot].push_back(1), Y[tot].push_back(i), swap(a[1], a[i]);
            // (1,p1) -> (p1,p1)
            for (int i = 2; i <= p1; i++) 
                X[tot].push_back(i), Y[tot].push_back(p1), swap(a[i], a[p1]);
            // (p1,p1) -> (p1,n)
            for (int i = p1 + 1; i <= n; i++) 
                X[tot].push_back(p1), Y[tot].push_back(i), swap(a[p1], a[i]);
            // (p1,n) -> (n,n)
            for (int i = p1 + 1; i <= n; i++) 
                X[tot].push_back(i), Y[tot].push_back(n), swap(a[i], a[n]);
        }
        
        // Step 2 & 3: 奇偶排序 + 循环移位
        for (int i = 2; i <= n; i++) {
            tot++;
            X[tot].push_back(1), Y[tot].push_back(1);
            
            if (n & 1) {  // n 为奇数
                if (i & 1) {  // i 为奇数
                    for (int j = 2; j <= n; j += 2) {
                        if (j + 1 == i) 
                            walk2(j);
                        else if (a[j] > a[j + 1]) 
                            walk1(j);
                        else 
                            walk2(j);
                    }
                } else {  // i 为偶数
                    for (int j = 2; j <= n; j += 2) {
                        if (a[j] > a[j + 1]) 
                            walk1(j);
                        else 
                            walk2(j);
                    }
                }
            } else {  // n 为偶数
                if (i & 1) {  // i 为奇数
                    for (int j = 2; j <= n; j += 2) {
                        if (j == i - 1) {
                            X[tot].push_back(j - 1), Y[tot].push_back(j);
                            X[tot].push_back(j), Y[tot].push_back(j);
                            swap(a[j - 1], a[j]);
                            j--;
                        } else if (a[j] > a[j + 1]) 
                            walk1(j);
                        else 
                            walk2(j);
                    }
                } else {  // i 为偶数
                    for (int j = 2; j <= n; j += 2) {
                        if (j == i) {
                            X[tot].push_back(j - 1), Y[tot].push_back(j);
                            X[tot].push_back(j), Y[tot].push_back(j);
                            swap(a[j - 1], a[j]);
                            j--;
                        } else if (a[j] > a[j + 1]) 
                            walk1(j);
                        else 
                            walk2(j);
                    }
                }
            }
            
            // Step 3: 循环移位路径
            path2(++tot);
        }
        
        // 输出结果
        printf("%d\n", tot);
        for (int i = 1; i <= tot; i++) {
            for (int j = 1; j < 2 * n - 1; j++) {
                if (X[i][j] == X[i][j - 1]) 
                    printf("R");
                else 
                    printf("D");
            }
            printf("\n");
        }
    }
    return 0;
}

算法复杂度

• 时间复杂度：$O(n^2)$，因为每条路径长度 $O(n)$，总路径数 $O(n)$
• 空间复杂度：$O(n^2)$，用于存储所有路径的坐标

正确性证明

$1$. 奇偶排序的正确性：经过 $n-1$ 轮奇偶排序，数组 $[a_2, \dots, a_n]$ 会完全有序 $2$. 循环移位的处理：每次循环移位后，最小值始终在 $a_1$ 位置 $3$. 操作次数：初始移动最多 $1$ 次，之后每轮需要 $O(n)$ 次操作，总操作次数 $\le 2n+4$

该算法保证了在限制操作次数内完成排序，并通过了题目给定的测试用例。