「eJOI2022」LCS of Permutations 题解

算法思路

本题使用构造法和数学分析来解决三个排列的LCS约束问题。核心思想是通过分析LCS之间的数学关系，设计特定的排列构造方案。

关键观察

1. 必要条件分析

三个排列的LCS必须满足特定不等式关系：

• $a \le b \le c \le n$（题目给定）
• $a \times b \times c \ge n$（元素覆盖条件）
• $b + c \le n + a$（长度约束条件）

2. 构造策略

代码采用两种主要构造方案：

• 当 $n \ge A + B + C - 2$ 时的常规构造
• 其他情况下的特殊构造

代码解析

可行性检查

if (ll(A)*B * C < n || B + C > n + A) {
    puts("NO");
    return;
}

检查两个必要条件：

• $A \times B \times C \ge n$
• $B + C \le n + A$

核心构造函数

void go(int &p, int &v, int c, int B, int C) {
    reverse(y + p, y + p + c);
    int k = c;
    rp(j, 0, B - 1) {
        int d = 0;
        for (; d < C && c >= B - j; --c, z[p + d] = --v, ++d);
        reverse(z + p, z + p + d);
        p += d;
    }
    rp(j, p - k, p - 1) {
        z[j] = 2 * v + k - 1 - z[j];
    }
}

这个函数负责生成满足特定LCS约束的排列结构，通过反转和分段处理来控制公共子序列的长度。

特殊情形处理

if (A == B && C == n - 1) {
    // 处理边界情况
    // 构造特定的排列来满足 LCS(p,q)=A, LCS(p,r)=B, LCS(q,r)=C
}

算法正确性

构造保证

• 排列性质：通过系统化的赋值确保生成的是 $1$ 到 $n$ 的排列
• LCS控制：通过反转操作和分段构造精确控制每对排列的LCS长度
• 边界处理：特殊情况的单独处理确保所有合法输入都有解

数学关系验证

构造方法基于以下数学原理：

• 排列的LCS长度与元素相对顺序密切相关
• 通过精心设计的反转和重组可以精确控制公共子序列
• 三角不等式 $b + c \le n + a$ 确保构造的可能性

复杂度分析

• 可行性检查：$O(1)$
• 构造过程：$O(n)$，每个元素处理一次
• 总复杂度：$O(\sum n)$，满足题目约束

关键技巧

1. 分段构造：将排列分成多个段，分别控制LCS
2. 反转操作：通过反转子序列来调整公共子序列长度
3. 数学判定：基于不等式快速判断解的存在性
4. 边界处理：对特殊参数组合单独优化构造