题解：P12773 [POI 2018/2019 R1] 马虎 Nonchalance

· · 题解

论文题，同时是构造好题，放模拟赛被大神们秒掉了，我已吓哭。

题目的限制为公共子序列的每个空隙里两个串不能有公共字符，为方便简称这个子序列为 MCS，MCS 的每个位置选择为匹配。

但是并不能根据这个直接进行判定 MCS 和构造，最大的问题在于匹配位置可能不唯一。考虑从左到右贪心匹配，当前字符可以匹配就匹配上，否则就返回。这个做法就会错掉，一个 hack：CAGA CGA。如果直接贪心匹配，那么会匹配成 CA。

陷入僵局，先思考判定：判定的关键在于空隙中不能有公共字符，贪心的想，为达成这个限制，对于每组空隙，一定会选择使这组空隙最大的匹配方案来判定。

受到判定的启发，我们考虑魔改我们的贪心匹配做法，对于剩余没有匹配的情况，选择当前字符一定是优的，但是选择的位置不一定优。我们将当前字符加入答案，并删去距离当前结尾最近的同字符位置即可（只有最后面位置与结尾还存在匹配的情况该字符才不优，但是如果出现这种情况，贪心判定一定可以继续，矛盾）。

这样就可以编出做法了，保留贪心匹配的过程，用一个栈维护匹配，如果已经到达匹配极限就删点更新边界并加入答案，预处理一下 pre_{x,i} 表示位置 i 前第一个字符 x 的位置和 nxt_{x,i} 表示位置 i 后第一个字符 x 的位置即可快速匹配，复杂度 O(n)。

判定是好判的，处理满足当前匹配方案的最小前缀和最大后缀，然后枚举中间的空隙，判定最小前缀和最大后缀之间是否有公共字符即可，与字符集大小无关，均为 O(n)。

原论文中处理了字符集可能很大的问题，可以做到 O(n\log \log n) 复杂度，其实就是用 y-fast trie 维护寻找前驱后继的过程，地址

:::info[code]

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10, M = 4;
int n, m, pres[M][N], nxts[M][N], pret[M][N], nxtt[M][N], top = 0;
char s[N], t[N];
struct GG
{
    int x, y, c;
};
vector<GG> stk;
vector<int> ans;
int get(char a)
{
    if (a == 'A')
        return 0;
    else if (a == 'C')
        return 1;
    else if (a == 'G')
        return 2;
    return 3;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> (s + 1) >> (t + 1);
    n = strlen(s + 1), m = strlen(t + 1);
    for (int i = 2; i <= n + 1; i++)
    {
        for (int j = 0; j < 4; j++)
            pres[j][i] = pres[j][i - 1];
        pres[get(s[i - 1])][i] = i - 1;
    }
    for (int i = 2; i <= m + 1; i++)
    {
        for (int j = 0; j < 4; j++)
            pret[j][i] = pret[j][i - 1];
        pret[get(t[i - 1])][i] = i - 1;
    }
    for (int i = n - 1; i >= 0; i--)
    {
        for (int j = 0; j < 4; j++)
            nxts[j][i] = nxts[j][i + 1];
        nxts[get(s[i + 1])][i] = i + 1;
    }
    for (int i = m - 1; i >= 0; i--)
    {
        for (int j = 0; j < 4; j++)
            nxtt[j][i] = nxtt[j][i + 1];
        nxtt[get(t[i + 1])][i] = i + 1;
    }
    int id1 = 0, id2 = 0;
    n++, m++;
    while (1)
    {
        while (1)
        {
            int id = 0, mx = 1e9;
            for (int j = 0; j < 4; j++)
            {
                if (nxts[j][id1] && nxtt[j][id2] && nxts[j][id1] < n && nxtt[j][id2] < m)
                {
                    if (nxts[j][id1] < mx)
                    {
                        mx = nxts[j][id1];
                        id = j;
                    }
                }
            }
            if (mx == 1e9)
                break;
            id1 = nxts[id][id1], id2 = nxtt[id][id2];
            stk.push_back({id1, id2, id});
        }
        if (stk.size())
        {
            auto t = stk.back();
            stk.pop_back();
            n = pres[t.c][n], m = pret[t.c][m];
            ans.push_back(t.c);
            if (stk.size())
                id1 = stk.back().x, id2 = stk.back().y;
            else
                id1 = 0, id2 = 0;
        }
        else
            break;
    }
    reverse(ans.begin(), ans.end());
    for (auto t : ans)
    {
        if (t == 0)
            cout << "A";
        else if (t == 1)
            cout << "C";
        else if (t == 2)
            cout << "G";
        else
            cout << "T";
    }
}

:::