在 NOI 竞赛中，一个高质量的测试数据包需要包含：边界情况、特殊构造、以及最大规模的随机数据。

下面是一个完整的数据生成器代码。它不仅包含生成逻辑，还内置了“标程（Standard Solution）”，可以直接一次性生成 1.in 到 10.in 以及对应的 1.out 到 10.out。

数据生成器 (C++14)

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <random>
#include <string>
#include <chrono>

using namespace std;

// --- 标程部分：用于生成 .out 文件 ---
void solve(int m, int n, vector<vector<int>>& a, string out_name) {
    // 使用 i-j 的桶方案，代码更简洁且逻辑一致
    vector<int> bucket[205];
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            bucket[i - j + 100].push_back(a[i][j]);
        }
    }
    for (int k = 0; k < 205; ++k) {
        if (!bucket[k].empty()) sort(bucket[k].begin(), bucket[k].end());
    }
    
    // 回填时需要记录每个桶取到第几个了
    int ptr[205] = {0};
    ofstream fout(out_name);
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            fout << bucket[i - j + 100][ptr[i - j + 100]++] << (j == n - 1 ? "" : " ");
        }
        fout << "\n";
    }
    fout.close();
}

// --- 生成器逻辑 ---
void make_data() {
    // 使用高质量随机数种子
    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

    for (int t = 1; t <= 10; ++t) {
        string in_name = to_string(t) + ".in";
        string out_name = to_string(t) + ".out";
        ofstream fin(in_name);

        int m, n;
        vector<vector<int>> grid;

        // --- 测试点分类构造 ---
        if (t == 1) { // 边界：最小矩阵 1x1
            m = 1; n = 1;
        } else if (t == 2) { // 边界：只有一行
            m = 1; n = 100;
        } else if (t == 3) { // 边界：只有一列
            m = 100; n = 1;
        } else if (t == 4) { // 特殊：所有元素相同
            m = 50; n = 50;
        } else if (t == 5) { // 特殊：已经是升序
            m = 10; n = 10;
        } else if (t == 6) { // 特殊：严格降序
            m = 10; n = 10;
        } else if (t >= 7 && t <= 8) { // 普通规模随机
            m = rng() % 50 + 10;
            n = rng() % 50 + 10;
        } else { // 最大规模随机 (100x100)
            m = 100; n = 100;
        }

        grid.assign(m, vector<int>(n));
        fin << m << " " << n << "\n";

        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (t == 4) grid[i][j] = 66;
                else if (t == 5) grid[i][j] = i + j + 1; // 构造一种对角线近似升序
                else if (t == 6) grid[i][j] = 100 - (i + j);
                else grid[i][j] = rng() % 100 + 1; // 随机 1~100
                
                fin << grid[i][j] << (j == n - 1 ? "" : " ");
            }
            fin << "\n";
        }
        fin.close();

        // 调用标程生成对应的 .out
        solve(m, n, grid, out_name);
        cout << "Generated Case " << t << ": m=" << m << ", n=" << n << endl;
    }
}

int main() {
    make_size_t: // 无实际意义，仅防止部分编译器警告
    make_data();
    cout << "All test cases (1.in~10.out) generated successfully!" << endl;
    return 0;
}

测试点说明（OJ 建设参考）

生成器设计要点总结

1. 非递归与效率：
   • 本题不涉及树或复杂图论，生成器采用双重循环，时间复杂度为 $O(T \times M \times N)$，对于 10 组数据，生成时间几乎是瞬间完成（毫秒级）。
2. 随机数质量：
   • 使用了 C++11 引入的 std::mt19937，相比传统的 rand()，其随机分布更均匀，周期更长，是 NOI 竞赛中推荐的随机数生成方式。
3. 文件流操作：
   • 通过 ofstream 自动创建文件，确保生成的 .in 和 .out 严格匹配，避免了手动复制粘贴产生的人为失误。
4. 数据范围覆盖：
   • 严格遵守题目的 $1 \le A[i][j] \le 100$ 限制，保证了数据的合法性。

教练提示：在建设 OJ 时，记得检查输出文件的行末空格和文末换行。上述代码使用了 (j == n - 1 ? "" : " ") 来处理行末空格，这是最符合规范的写法。

你好！在 NOI 系列竞赛（如 CSP-J/S, NOIP）中，编写代码不仅要求逻辑正确，更要求稳定性和边界处理的严谨性。

以下是针对该题目的标准参赛代码，采用了更符合竞赛习惯的“起始点遍历法”，并附带详细的复杂度分析与优化建议。

一、 题解标准代码 (C++14)

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 考虑到数据范围 M, N <= 100，数组开稍大一点防止越界
int a[105][105];
int m, n;

// 处理一条对角线的函数：传入对角线的起始坐标 (startR, startC)
void sortDiagonal(int startR, int startC) {
    vector<int> temp;
    int r = startR, c = startC;

    // 1. 提取对角线元素
    // 易错点：循环条件必须同时满足行和列都在界内
    while (r < m && c < n) {
        temp.push_back(a[r][c]);
        r++;
        c++;
    }

    // 2. 排序：使用 STL 标准库提供的快排，时间复杂度 O(L log L)
    sort(temp.begin(), temp.end());

    // 3. 回填元素
    r = startR;
    c = startC;
    int idx = 0;
    while (r < m && c < n) {
        a[r][c] = temp[idx++];
        r++;
        c++;
    }
}

int main() {
    // 优化 IO 性能，虽然本题数据量小，但这是 NOI 竞赛的好习惯
    ios::sync_with_stdio(false);
    cin.tie(0);

    // 读取矩阵行列
    if (!(cin >> m >> n)) return 0;

    // 读取矩阵内容
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            cin >> a[i][j];
        }
    }

    /* 
       关键思路：
       每一条“左上到右下”的对角线，其起点必然分布在：
       1. 第一列的所有行 (i, 0)
       2. 第一行的所有列 (0, j)
    */

    // 处理第一列作为起点的所有对角线 (i, 0)
    for (int i = 0; i < m; ++i) {
        sortDiagonal(i, 0);
    }

    // 处理第一行作为起点的所有对角线 (0, j)
    // 注意：(0, 0) 已经在上面处理过了，从 j = 1 开始
    for (int j = 1; j < n; ++j) {
        sortDiagonal(0, j);
    }

    // 输出结果矩阵
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            cout << a[i][j] << (j == n - 1 ? "" : " ");
        }
        cout << "\n";
    }

    return 0;
}

二、 复杂度分析思考过程

1. 时间复杂度

• 提取与回填：矩阵中的每一个元素 $(i, j)$ 恰好被提取一次、回填一次。总次数为 $O(M \times N)$。
• 排序开销：
  • 设某条对角线的长度为 $L$。排序该对角线的复杂度为 $O(L \log L)$。
  • 所有对角线长度之和等于矩阵元素总数 $M \times N$。
  • 在最坏情况下，对角线长度 $L = \min(M, N)$。
  • 总时间复杂度约为 $O(M \times N \cdot \log(\min(M, N)))$。
• 量化估算：本题 $M, N = 100$，则 $10000 \times \log_2(100) \approx 10000 \times 7 = 7 \times 10^4$ 次运算。在 NOI 1秒 规定时间内（通常可处理 $10^8$ 次运算）绰绰有余。

2. 空间复杂度

• 矩阵存储：$O(M \times N)$。
• 辅助容器：每次排序使用的 vector 最大长度为 $\min(M, N)$，即 $O(\min(M, N))$。
• 总空间：$O(M \times N)$，在 128MB 或 256MB 的竞赛限制下非常安全。

三、 算法优化建议

虽然上述代码已足够通过竞赛，但在更高难度的题目中，可以考虑以下优化方向：

1. 计数排序 (Counting Sort)：

   • 观察：题目说明矩阵元素范围是 $1 \le A[i][j] \le 100$。这是一个非常小且固定的范围。
   • 优化：对于每一条对角线，可以使用计数排序代替 std::sort。计数排序的时间复杂度为 $O(L + \text{Range})$。
   • 结果：总时间复杂度将降至绝对的线性 $O(M \times N)$。

2. 利用 $i-j$ 的映射关系：

   • 思路：不需要分两次循环找起点。直接一次双重循环遍历整个矩阵，将元素放入 vector<int> diag[205] 中，其中下标为 i - j + 100。
   • 优点：代码逻辑更简洁，减少了对循环边界的判断。

3. 内存池/静态数组：

   • 在极高性能要求的比赛中，频繁分配 std::vector 可能产生常数开销。可以使用一个足够大的静态数组重复使用，手动维护指针（top）来模拟栈或容器。

四、 易错点总结（填坑指南）

• 边界溢出：在 while 循环里，一定要先检查 r < m 再检查 c < n（虽然顺序不影响，但逻辑要严密）。
• 起点遗漏：第一行和第一列的交点 (0,0) 容易被重复计算或漏掉，建议像我上面代码那样，一个从 0 开始，一个从 1 开始。
• 输出格式：NOI 比赛对行末空格通常不敏感，但对每行末尾的换行符有严格要求。建议习惯性使用 \n 而不是 endl 以提高速度。