题目描述

有\(n\)个串，你要把每个串用它的一个子序列（可以不连续）替换，使得最终不存在两个串相同，求替换后最长串的最小长度，以及替换方案

输入的串可能有相同的

\(n \le 300\)，每个原串长度不超过\(300\)

解析

“最长的长度最小”套路二分

问题变成判断是否存在一种合法方案使得替换后所有串长度不超过\(mid\)

因为是用子序列替换，先建出子序列自动机

然后因为一个新串只能替换一个原串，所以考虑二分图

对每个原串，找出它的长度不超过的\(mid\)的子序列，并将原串同这个子序列代表的点连边

注意到如果长度满足条件的子序列不少于\(n\)个，那么这个原串一定可以匹配上一个新串，所以每个原串最多只需要找\(n\)个合法子序列就可以了

找出的所有新串构成一棵\(trie\)，\(trie\)每个节点都对应了新串，所以点数不超过\(n^2\)，可以用\(trie\)的点编号来表示新串

然后匈牙利或者\(dinic\)判断是否存在完备匹配

复杂度\(O(n^3\log maxlen)\)

代码

警告：代码极度丑陋，我自己都看不下去了，有时间再重构吧

#include 
    
     #include 
     
      #include 
      
       #define MAXN 305typedef long long LL;struct Trie {    int fa[MAXN * MAXN], trans[MAXN * MAXN][MAXN], ch[MAXN * MAXN], idx;    int newnode(int = 0, int = 0);    void init();    int insert(char *);    void print(int);};struct Graph {    struct Edge {        int v, next;        Edge(int _v = 0, int _n = 0):v(_v), next(_n) {}    } edge[MAXN * MAXN];    int head[MAXN], cnt, pre[MAXN], link[MAXN * MAXN];    bool vis[MAXN * MAXN];    void init() { memset(head, -1, sizeof head); memset(link, -1, sizeof link); cnt = 0; }    void add_edge(int u, int v) { edge[cnt] = Edge(v, head[u]); head[u] = cnt++; }    bool match(int);};void prework();bool check(int);void dfs(int, int, int &, int, int, int);int N, next[MAXN][MAXN][26], len[MAXN], maxlen, endp[MAXN * MAXN], tot, top;char name[MAXN][MAXN], str[MAXN];Trie trie;Graph G;int main() {    freopen("diff.in", "r", stdin);    freopen("diff.out", "w", stdout);    scanf("%d", &N);    for (int i = 0; i < N; ++i) {        scanf("%s", name[i] + 1);        len[i] = strlen(name[i] + 1) + 1;        maxlen = std::max(maxlen, len[i]);    }    prework();    int l = 1, r = maxlen;    while (l < r) {        int mid = (l + r) >> 1;        if (check(mid)) r = mid;        else l = mid + 1;    }    if (check(l)) {        printf("%d\n", l);        for (int i = 0; i < N; ++i) trie.print(G.pre[i]), putchar('\n');    } else puts("-1");    return 0;}void Trie::init() { idx = 0; newnode(); }int Trie::newnode(int f, int c) {    ++idx;    for (int i = 0; i < 26; ++i) trans[idx][i] = 0;    fa[idx] = f, ch[idx] = c;    return idx;}void Trie::print(int x) {    if (fa[x] ^ 1) print(fa[x]);    putchar('a' + ch[x]);}void prework() {    for (int i = 0; i < N; ++i) for (int j = len[i] - 1; j >= 0; --j) for (int k = 0; k < 26; ++k)        next[i][j][k] = (name[i][j + 1] - 'a' == k ? j + 1 : next[i][j + 1][k]);}bool check(int m) {    G.init(); trie.init();    tot = N - 1;    for (int i = 0; i < N; ++i) {        int rest = N;        dfs(i, 0, rest, m, 0, 1);    }    for (int i = 0; i < N; ++i) {        memset(G.vis, 0, sizeof G.vis);        if (!G.match(i)) return 0;    }    return 1;}void dfs(int id, int p, int &rest, int m, int dep, int cur) {    if (!rest) return;    if (dep == m) return;    for (int i = 0; i < 26; ++i)        if (next[id][p][i]) {            if (!rest) break;            --rest;            if (!trie.trans[cur][i]) trie.trans[cur][i] = trie.newnode(cur, i);            G.add_edge(id, trie.trans[cur][i]);            dfs(id, next[id][p][i], rest, m, dep + 1, trie.trans[cur][i]);        }}bool Graph::match(int x) {    for (int i = head[x]; ~i; i = edge[i].next)        if (!vis[edge[i].v]) {            vis[edge[i].v] = 1;            if (!(~link[edge[i].v]) || match(link[edge[i].v])) {                link[edge[i].v] = x; pre[x] = edge[i].v;                return 1;            }        }    return 0;}//Rhein_E 100pts