1 条题解

  • 0
    @ 2026-11-12 21:45:53

    [F] LCS(dp_f)题解

    题意简述

    给定两个串 s,ts, t,求一个最长的公共子序列(输出任意一个即可)。

    思路

    第一步:求长度

    设 fi,jf_{i,j} = ss 的前 ii 个字符与 tt 的前 jj 个字符的 LCS 长度:

    $$f_{i,j} = \begin{cases} f_{i-1,j-1} + 1, & s_i = t_j,\\[2pt] \max(f_{i-1,j},\; f_{i,j-1}), & s_i \ne t_j. \end{cases}$$

    f∣s∣,∣t∣f_{|s|,|t|} 即 LCS 长度 LL。

    第二步:还原方案

    开一个等大的方向数组 dir[i][j],记录转移来自哪里:

    • 来自左上(s_i == t_j):dir = 2;
    • 来自上方 fi−1,jf_{i-1,j}:dir = 0;
    • 来自左侧 fi,j−1f_{i,j-1}:dir = 1。

    从 (∣s∣,∣t∣)(|s|, |t|) 往回走:遇到 dir == 2 就把 sis_i 记入答案并往左上走,否则按方向回退。最后把记录到的字符反转输出。

    为什么答案不唯一

    LCS 可能有多个。例如 s=s=axyb、t=t=abyxb,axb 与 ayb 都是长度 33 的 LCS。因此本题是 Special Judge:只要输出字符串是 ss 与 tt 的公共子序列且长度等于 LL 即判对。

    复杂度

    时间 O(∣s∣∣t∣)≤9×106O(|s||t|) \le 9\times10^6,空间 O(∣s∣∣t∣)O(|s||t|)(方向数组用 unsigned char,约 9MB)。

    参考代码

    #include <cstdio>
    #include <string>
    #include <vector>
    using namespace std;
    
    int main() {
        static char bs[3005], bt[3005];
        scanf("%s %s", bs, bt);
        string s = bs, t = bt;
        int n = s.size(), m = t.size();
        vector<vector<unsigned char>> dir(n + 1, vector<unsigned char>(m + 1, 0));
        vector<int> prev(m + 1, 0), cur(m + 1, 0);
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (s[i - 1] == t[j - 1]) { cur[j] = prev[j - 1] + 1; dir[i][j] = 2; }
                else if (prev[j] >= cur[j - 1]) { cur[j] = prev[j]; dir[i][j] = 0; }
                else { cur[j] = cur[j - 1]; dir[i][j] = 1; }
            }
            swap(prev, cur);
            fill(cur.begin(), cur.end(), 0);
        }
        string ans;
        int i = n, j = m;
        while (i > 0 && j > 0) {
            if (dir[i][j] == 2) { ans += s[i - 1]; i--; j--; }
            else if (dir[i][j] == 0) i--;
            else j--;
        }
        reverse(ans.begin(), ans.end());
        printf("%s\n", ans.c_str());
        return 0;
    }
    

    易错点

    1. LCS 可能为空串(如 s=s=a、t=t=z),此时要输出一个空行,不能什么都不输出或输出乱码。
    2. 重建时字符是逆序收集的,必须反转。
    3. 方向数组用 int 会占 36MB(3000×3000×43000\times3000\times4),用 unsigned char 更稳。
    4. 别只输出长度;本题要求输出具体字符串。

    数据说明

    共 16 组:4 组官方样例(含空串答案的 a/z);s=ts=t、ss 是 tt 的子串、完全无公共字符、ss 与 tt 互为逆序;∣s∣=∣t∣=3000|s|=|t|=3000 的随机(字符集大小 3 与 26 各一组)、全 a、互为反转等大规模组。全部用 SPJ 校验(公共子序列 + 长度等于独立算出的 LCS 长度)。

    • 1

    信息

    ID
    15
    时间
    2000ms
    内存
    256MiB
    难度
    5
    标签
    递交数
    3
    已通过
    1
    上传者