【纪中集训2019.3.19】不同的缩写

题意：

描述

考虑用\(n\)个字符串\(t_{i}\)去代替\(n\)个字符串\(s_{i}\)，满足\(t_{i}是s_{i}\)的子序列且\(t_{i}\)互不相同；

给出\(s_{i}\),最小化\(max \{ |t_{i}|\}\);

范围

\(n,|s_{i}| \ \le \ 300\);

题解：

• 随机的情况下答案一般都是1，2；

• 所以暴力找出所有长度为1和2的子序列进行匹配可以得到一部分分；

• 二分答案\(mid\)；

• \(dfs\)找到所有长度小于等于\(mid\)的子序列连边，做二分图匹配；

• 当一个点找到的不相同的子序列超过\(n\)个时一定有匹配，就不需要再继续\(dfs\)了；

• 所以最多一共\(n^2\)个点，\(n^2\)条边；

• 期望复杂度：\(O(log \ n \ n^2\sqrt{n^2}) = O(n^3 \ log \ n)\);

• 常数较小；

  #include<bits/stdc++.h>
  using namespace std;
  const int N=310,M=1000010;
  int n,sz,l[N],nxt[N][N][26],mid,cur,cnt,T,vis[M],p[M],q[N];
  int ch[M][26],fa[M],fm[M];
  char s[N][N];
  vector<int>g[N];
  void print(int x){
    if(fa[x])print(fa[x]);
    putchar(fm[x]+'a');
  }
  bool match(int u){
    for(int i=0;i<g[u].size();++i){
        int v=g[u][i];
        if(vis[v]==T)continue;
        vis[v]=T;
        if(!p[v]||match(p[v])){
            p[v]=u;q[u]=v;
            return true;
        }
    }
    return false;
  }
  int CH(int x,int y){
    if(ch[x][y])return ch[x][y];
    ch[x][y]=++sz;
    memset(ch[sz],0,sizeof(ch[sz]));
    fm[sz]=y;fa[sz]=x;p[sz]=0;
    return sz;
  }
  void dfs(int t,int x,int y){
    if(cnt==n)return;
    if(y)g[t].push_back(cur),++cnt;
    if(y==mid)return;
    for(int i=0;i<26;++i)if(nxt[t][x][i]<=l[t]){
        cur=CH(cur,i);
        dfs(t,nxt[t][x][i],y+1);
        cur=fa[cur];
        if(cnt==n)break;
    }
  }
  bool check(){
    sz=0;
    memset(ch[0],0,sizeof(ch[0]));
    for(int i=1;i<=n;++i){
        g[i].clear();
        cur=cnt=0;
        dfs(i,0,0);
    }
    ++T;for(int i=1;i<=n;++i,++T)
    if(!match(i))return false;
    return true;
  }
  int main(){
    freopen("diff.in","r",stdin);
    freopen("diff.out","w",stdout);
    scanf("%d",&n);
    int mx=0;
    for(int i=1;i<=n;++i){
        scanf("%s",s[i]+1);
        l[i]=strlen(s[i]+1);
        for(int j=0;j<26;++j)nxt[i][l[i]][j]=l[i]+1;
        for(int j=l[i]-1;~j;--j){
            memcpy(nxt[i][j],nxt[i][j+1],sizeof(nxt[i][j]));
            nxt[i][j][s[i][j+1]-'a']=j+1;
        }
        mx=max(mx,l[i]);
    }
    int L=0,R=mx;
    while(L<R){
        mid=L+R>>1;
        if(check())R=mid;
        else L=mid+1;
    }
    mid=L;
    if(!check())puts("-1"),exit(0);else printf("%d\n",L);
    for(int i=1;i<=n;++i)print(q[i]),putchar('\n');
    return 0;
  }

【纪中集训2019.3.19】不同的缩写

原文：https://www.cnblogs.com/Paul-Guderian/p/10560554.html