针对 P1439 【模板】最长公共子序列，我们需要生成符合“$1 \sim n$ 的排列”这一特殊性质的数据。为了有效区分 $O(n^2)$ 和 $O(n \log n)$ 算法，我们将重点构造大规模的随机数据以及一些特殊的边界情况（如完全相同、完全逆序）。

该生成器采用 $O(n \log n)$ 算法来生成标准输出，确保在大规模数据下生成过程不会超时。

数据生成器 C++14 代码

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <random>
#include <numeric>
#include <string>
#include <ctime>

using namespace std;

/**
 * 核心算法：O(n log n) LCS 转化为 LIS
 * 用于快速生成 .out 答案文件
 */
int solve_lcs_fast(int n, const vector<int>& p1, const vector<int>& p2) {
    if (n == 0) return 0;
    vector<int> pos(n + 1);
    for (int i = 0; i < n; i++) pos[p1[i]] = i + 1;

    vector<int> a(n);
    for (int i = 0; i < n; i++) a[i] = pos[p2[i]];

    vector<int> low;
    for (int x : a) {
        if (low.empty() || x > low.back()) {
            low.push_back(x);
        } else {
            auto it = lower_bound(low.begin(), low.end(), x);
            *it = x;
        }
    }
    return (int)low.size();
}

/**
 * 生成测试点
 * @param id 测试点编号
 * @param n 数据规模
 * @param type 数据类型: 0-随机, 1-完全相同, 2-完全逆序, 3-部分有序
 */
void generate_test(int id, int n, int type) {
    mt19937 rng(time(0) + id);
    vector<int> p1(n), p2(n);

    // 初始化为 1~n
    iota(p1.begin(), p1.end(), 1);
    
    if (type == 1) { // 完全相同
        shuffle(p1.begin(), p1.end(), rng);
        p2 = p1;
    } else if (type == 2) { // 完全逆序
        shuffle(p1.begin(), p1.end(), rng);
        p2 = p1;
        reverse(p2.begin(), p2.end());
    } else { // 随机或部分随机
        shuffle(p1.begin(), p1.end(), rng);
        p2 = p1;
        shuffle(p2.begin(), p2.end(), rng);
        
        if (type == 3) { // 强行构造一段公共子序列（增加答案长度）
            int len = n / 2;
            uniform_int_distribution<int> dist(0, n - len);
            int start1 = dist(rng), start2 = dist(rng);
            for(int i = 0; i < len; ++i) swap(p2[start2 + i], p2[find(p2.begin(), p2.end(), p1[start1 + i]) - p2.begin()]);
        }
    }

    // 写入输入文件
    string in_name = to_string(id) + ".in";
    ofstream fin(in_name);
    fin << n << "\n";
    for (int i = 0; i < n; i++) fin << p1[i] << (i == n - 1 ? "" : " ");
    fin << "\n";
    for (int i = 0; i < n; i++) fin << p2[i] << (i == n - 1 ? "" : " ");
    fin << endl;
    fin.close();

    // 写入输出文件
    string out_name = to_string(id) + ".out";
    ofstream fout(out_name);
    fout << solve_lcs_fast(n, p1, p2) << endl;
    fout.close();

    cout << "Test Case " << id << " created. (n=" << n << ")" << endl;
}

int main() {
    // 1-2: 极小数据 (边界测试)
    generate_test(1, 5, 0);
    generate_test(2, 10, 1);

    // 3-4: 中等规模 (区分 O(n^2) 和优化算法)
    generate_test(3, 1000, 0);
    generate_test(4, 3000, 2);

    // 5-6: 特殊构造 (LIS 极端情况)
    generate_test(5, 50000, 1); // 完全相同, LCS = n
    generate_test(6, 50000, 2); // 完全逆序, LCS = 1

    // 7-10: 极限规模 (10^5)
    generate_test(7, 80000, 0); // 纯随机
    generate_test(8, 100000, 3); // 部分有序
    generate_test(9, 100000, 0); // 极限随机
    generate_test(10, 100000, 0); // 极限随机

    return 0;
}

数据设计与优化说明

1. 数据规模控制与文件大小

• $n=10^5$ 的文件大小：一行 $10^5$ 个整数（平均每个数 5 位 + 1 空格），约占 0.6MB。
• 两个序列加起来，一个 .in 文件约为 1.2MB。
• 为了将 10 个测试点的总大小控制在合理范围内，我将前几个测试点设置得较小，最后 4 个测试点达到 $10^5$。总数据量约在 6MB - 8MB。
  • 注：若需严格控制在 2MB 内，建议减少 $10^5$ 测试点的数量，或将 $n$ 降至 $3 \times 10^4$。但在 NOI 级别 OJ 中，$10^5$ 是必须测试的门槛。

2. 覆盖情况方案

• Case 1, 2：基础逻辑与最小 $n$ 测试。
• Case 3, 4：$n$ 在 $1000 \sim 3000$。这些测试点是用来给写了 $O(n^2)$ 算法但带了优化的选手部分分数的。
• Case 5 (完全相同)：LCS 结果应等于 $n$。这是测试“相等时转移”逻辑最直接的办法。
• Case 6 (完全逆序)：LCS 结果应等于 $1$。
• Case 8 (部分有序)：通过将 $n/2$ 长度的子序列强行对齐，测试算法在存在较长公共路径时的效率。

3. 生成效率与安全性

• 避免爆栈：solve_lcs_fast 使用 std::vector 和迭代写法，完全没有递归。
• 时间效率：生成 $10^5$ 数据时，主要的耗时在于 std::shuffle 和文件 I/O。由于使用了 $O(n \log n)$ 计算答案，整个生成器在几秒内即可跑完所有测试点。
• 除零与溢出：逻辑中仅涉及加减法、交换和二分查找，不存在除法操作，数据类型使用 int 即可满足 $n=10^5$ 的需求。

4. OJ 部署建议

• 在创建 OJ 题目时，请设置 时间限制 1.0s。
• 这组数据能完美卡掉 $O(n^2)$ 算法（第 7-10 个点会 TLE），也能卡掉没有空间优化的 $O(n^2)$ 算法（第 5-10 个点会 MLE）。

你好！我是教练。在NOI竞赛中，面对一个经典问题，学会 “保分（暴力）” 与 “冲满分（优化）” 同样重要。

针对 P1439 最长公共子序列，我为你整理了从最基础到最顶尖的三个版本。请注意，这题的特殊性在于“排列”二字，它让我们能完成从 $O(N^2)$ 到 $O(N \log N)$ 的跨越。

版本一：基础二维 DP 版本（$O(N^2)$）

——适用场景：$N \le 5000$，不仅限于排列，任何序列均可。

思路思考过程： 这是最原始的动态规划。我们在纸上画表，如果 $A[i]$ 和 $B[j]$ 相同，就说明找到了一个公共元素，长度在“去掉这两个元素”的结果上 $+1$。

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

using namespace std;

// 全局数组在静态区，NOI竞赛中建议稍微开大一点防止溢出
// 注意：10^5 数据下此版本会 MLE (内存超出)
int dp[5005][5005]; 

int main() {
    int n;
    if (!(cin >> n)) return 0;
    vector<int> a(n + 1), b(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) cin >> b[i];

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (a[i] == b[j]) {
                // 【关键点】字符相等，来源一定是左上角 + 1
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                // 【关键点】不等，则继承上方或左方的最大值
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    cout << dp[n][n] << endl;
    return 0;
}

• 时间复杂度：$O(N^2)$。
• 空间复杂度：$O(N^2)$。在 $N=10^5$ 时完全不可行。

版本二：空间优化版本（滚动数组 $O(N^2)$）

——适用场景：$N \le 10000$，内存受限，但时间允许。

思路思考过程： 观察版本一，计算 dp[i] 行时，只用到了 dp[i-1] 行的数据。我们可以只开两行数组，用 i % 2 轮流切换“当前行”和“上一行”。

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

using namespace std;

// 只开两行，空间复杂度从 O(N^2) 降至 O(N)
int dp[2][100005];

int main() {
    ios::sync_with_stdio(false); // 优化大数据读入
    cin.tie(0);

    int n;
    cin >> n;
    vector<int> a(n + 1), b(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) cin >> b[i];

    for (int i = 1; i <= n; i++) {
        int cur = i % 2;
        int prev = (i - 1) % 2;
        for (int j = 1; j <= n; j++) {
            if (a[i] == b[j]) {
                dp[cur][j] = dp[prev][j - 1] + 1;
            } else {
                dp[cur][j] = max(dp[prev][j], dp[cur][j - 1]);
            }
        }
    }
    cout << dp[n % 2][n] << endl;
    return 0;
}

• 时间复杂度：$O(N^2)$（对于 $10^5$ 依然会 TLE）。
• 空间复杂度：$O(N)$。

版本三：模型转化最优解（$O(N \log N)$）

——适用场景：$N \le 10^5$，且题目明确指出是“1~n 的排列”。

思路思考过程（重点）：

1. 重新定义顺序：既然第一个序列 $P_1$ 是个排列，我们可以认为 $P_1$ 出现的顺序就是“从小到大”的新标准。
2. 映射：记录 $P_1$ 中每个数字出现的位置。
3. 转化：把 $P_2$ 中的每个数字替换成它在 $P_1$ 中的位置。
4. 结论：求两者的 LCS，等价于求转化后 $P_2$ 的 LIS（最长递增子序列）。

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

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin >> n;

    // pos[x] 存储数字 x 在第一个排列中出现的位置
    vector<int> pos(n + 1);
    for (int i = 1; i <= n; i++) {
        int val;
        cin >> val;
        pos[val] = i; 
    }

    // data[i] 存储第二个排列的元素在第一个排列中的“排位”
    vector<int> data(n + 1);
    for (int i = 1; i <= n; i++) {
        int val;
        cin >> val;
        data[i] = pos[val];
    }

    // 针对 data 序列求 LIS (最长递增子序列)
    // low[len] 表示长度为 len 的递增子序列，末尾元素的最小值
    vector<int> low;
    if (n > 0) low.push_back(data[1]);

    for (int i = 2; i <= n; i++) {
        if (data[i] > low.back()) {
            // 如果比当前最长的末尾还大，直接接在后面
            low.push_back(data[i]);
        } else {
            // 【关键点】二分查找第一个大于等于 data[i] 的位置并替换
            // 这样能让后续更有可能形成更长的序列（贪心优化）
            auto it = lower_bound(low.begin(), low.end(), data[i]);
            *it = data[i];
        }
    }

    cout << low.size() << endl;

    return 0;
}

• 时间复杂度：$O(N \log N)$。$10^5$ 规模下计算次数约 $1.6 \times 10^6$，远快于 $1.0\text{s}$ 的要求。
• 空间复杂度：$O(N)$。

复杂度分析与建议总结

1. 时间复杂度优化建议：

   • 在 LCS 变 LIS 的版本中，lower_bound 是核心。如果手动写遍历去查位置，复杂度会退化到 $O(N^2)$。
   • NOI 技巧：遇到 $10^5$ 的数据，尽量使用 scanf 或 ios::sync_with_stdio(false)。

2. 空间复杂度优化建议：

   • 如果题目不是排列，又必须做 $10^5$ 的数据，可以研究 Bitset 优化 LCS（能将复杂度降至 $O(N^2/w)$，其中 $w=64$），这属于省选级别的技巧。

3. 读题关键词（题意理解的关键）：

   • “1, 2, ..., n 的排列”：这是此题最重要的信息。看到它，就要立刻想到“每个数唯一” $\to$ “位置映射” $\to$ “转化为 LIS”。
   • “$N \le 10^5$”：这是死命令。它告诉你 $O(N^2)$ 的基础 DP 哪怕空间优化了，时间也过不去。

教练寄语： 同学，你之前错在“字符相等时如何转移”，这反映出你对“状态如何推进”的理解还在二维表层面。通过这道题，你要学会升维思考：当表的维度太大填不动时，能不能通过某种映射，把表格降维成线性的搜索？这就是竞赛选手的核心竞争力！加油！