【纪中集训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
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];
vectorg[N];
void print(int x){
if(fa[x])print(fa[x]);
putchar(fm[x]+&＃39;a&＃39;);
}
bool match(int u){
for(int i=0;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]-&＃39;a&＃39;]=j+1;
}
mx=max(mx,l[i]);
}
int L=0,R=mx;
while(L 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(&＃39;\n&＃39;);
return 0;
}