CF590E Birthday 题解

作者: xht37 分类: 题解 发布时间: 2020-01-27 18:11

点击数:75

CF590E Birthday

题意

  • 给定 $n$ 个仅包含 a,b 的字符串。
  • 你需要去掉尽可能少的字符串,使得剩下的字符串中不存在某一个串是另一个串的子串。
  • $n \le 750$,$\sum_{i=1}^n |s_i| \le 10^7$。

题解

设 $\sum_{i=1}^n |s_i| = m$。

首先可以 $\mathcal O(m)$ 建 AC 自动机然后求出所有的子串关系。

显然我们不能暴力跳 fail,这样显然会 T 飞。

注意到子串关系是一个偏序关系,因此我们只需要跳到最近的结尾同时路径压缩即可,那么此时可以建出一个 DAG。

接下来就是 P4298 [CTSC2008]祭祀了,不过还是在这儿完整的写一遍。

题目要求的实际上是这个偏序关系的最长反链,通过 Dilworth 定理可以发现就是 DAG 的最小可重复路径点覆盖

最小可重复路径点覆盖又可以通过 $\mathcal O(n^3)$ 的传递闭包转化为最小路径点覆盖

又 DAG 的最小路径点覆盖包含的路径条数 $= n -$ 其拆点二分图的最大匹配数。

使用匈牙利算法即可在 $\mathcal O(n^3)$ 的时间求出答案。

接下来的问题是如何构造方案。

我们先求出传递闭包后的图的最小路径点覆盖包含的路径集合 $path$:

  1. 设在拆点二分图中左部点 $x$ 对应的右部点为 $x^{\prime}$,若 $x,y$ 匹配则有 $f_x = y, f_y = x$。
  2. 依次考虑左部的每一个非匹配点 $x_0$。
  3. 从 $x_0$ 出发,每次从 $x$ 走到 $f_{x^{\prime}}$,直至到达一个左部点 $y_0$,满足 $y_0^{\prime}$ 是非匹配点。
  4. 那么经过的所有点构成一条以 $y_0$ 为起点 $x_0$ 为终点的路径。

接下来我们要从 $path$ 的每条路径上选出一个点构成原图的最长反链:

  1. 将所有的终点 $x_0$ 放到一起构成一个集合 $E$。
  2. 求出从 $E$ 中的所有节点出发,走一条边,到达的所有节点 $next(E)$。
  3. 根据传递闭包的性质,若 $E$ 与 $next(E)$ 没有交,那么 $E$ 即为所求。
  4. 否则考虑 $E \cap next(E)$ 的所有节点 $e$,沿着 $e$ 所在的路径反着走,直到一个节点 $e^{\prime} \notin next(E)$,在 $E$ 中将 $e$ 替换为 $e^{\prime}$。
  5. 回到第 $3$ 步。

总时间复杂度 $\mathcal O(m + n^3)$。

注意本题任何与 AC 自动机相关的递归均会爆栈。

代码

const int N = 757, M = 1e7 + 7;
int n, len[N], ed[N], trie[M][2], fail[M], fa[M], gt[M], tot = 1;
int d[N][N], v[N], f[N];
char s[M];
queue<int> q;

bool dfs(int x) {
    for (int i = 1; i <= n; i++)
        if (d[x][i] && !v[i]) {
            v[i] = 1;
            if (!f[i] || dfs(f[i])) return (f[i] = x);
        }
    return 0;
}

int main() {
    rd(n);
    for (int i = 1; i <= n; i++) {
        rds(s, len[i]);
        int p = 1;
        for (int j = 1; j <= len[i]; j++) {
            int c = s[j] - 'a';
            if (!trie[p][c]) trie[p][c] = ++tot, fa[tot] = p;
            p = trie[p][c];
        }
        ed[i] = p, gt[p] = i;
    }
    for (int i = 0; i < 2; i++)
        if (trie[1][i]) fail[trie[1][i]] = 1, q.push(trie[1][i]);
        else trie[1][i] = 1;
    while (q.size()) {
        int x = q.front();
        q.pop();
        for (int i = 0; i < 2; i++)
            if (trie[x][i])
                fail[trie[x][i]] = trie[fail[x]][i], q.push(trie[x][i]);
            else trie[x][i] = trie[fail[x]][i];
    }
    gt[1] = -1;
    vi o;
    for (int i = 1; i <= n; i++)
        for (int j = ed[i]; j != 1; j = fa[j]) {
            int x = fail[j];
            o.clear();
            while (!gt[x]) o.pb(x), x = fail[x];
            while (o.size()) fail[o.back()] = x, o.pop_back();
            fail[j] = x;
            if (j != ed[i] && gt[j]) x = j;
            if (x != 1) d[i][gt[x]] = 1;
        }
    for (int k = 1; k <= n; k++)
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                d[i][j] |= d[i][k] & d[k][j];
    for (int i = 1; i <= n; i++) d[i][i] = 0;
    int ans = n;
    for (int i = 1; i <= n; i++) ans -= dfs(i), memset(v, 0, sizeof(v));
    print(ans);
    for (int i = 1; i <= n; i++) v[f[i]] = 1;
    vi s;
    for (int i = 1; i <= n; i++) if (!v[i]) s.pb(i);
    memset(v, 0, sizeof(v));
    bool ok = 1;
    while (ok) {
        ok = 0;
        for (int x : s)
            for (int y = 1; y <= n; y++)
                if (d[x][y]) v[y] = 1;
        for (int &x : s)
            if (v[x]) {
                ok = 1;
                while (v[x]) x = f[x];
            }
    }
    for (auto x : s) print(x, ' ');
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注