ABC343G 题解

Gaode_Sean · 2024-03-10 21:30:04 · 题解

原本是围观大佬打 ABC，没想到顺便把 G 题想出来了，可惜没调完

考虑先消去一些被其它字符串严格包含的字符串串，注意一些相同的字符串的处理，正确性显然。

由于 n \le 20，所以我们考虑状压 dp。

因为剩下的字符串不存在完全包含的情况，所以我们可以直接将一个字符串接到所求字符串的结尾，同时要减去前一个字符串的后缀和当前字符串前缀的最长匹配。

设 a_{i,j} 表示字符串 i 的后缀 和 j 的前缀的最长匹配，这一部分可以用 hash 来完成。

设 f_{i,j} 表示已经被选择的字符串状态为 i，结尾的字符串为 j。有转移方程：f_{i,j}=\min(f_{i,j},f_{i-2^j,k}+len_j-a_{k,j})。

时间复杂度 \mathcal{O}(2^nn^2)。

AC Code

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;
const int N=2e5+5;
int n,ta;
int len[22],f[(1<<20)-1][22],a[22],lcp[22][22],b[N];
ll hsh[22][N],val[N];
char ch[22][N];
map<ll,int> cnt;
bool check(int x,int y)
{
    if(len[x]>len[y]) return false;
    for(int i=1;i<=len[y]-len[x]+1;i++) if(hsh[y][i+len[x]-1]-hsh[y][i-1]*val[len[x]]==hsh[x][len[x]]) return true;
    return false;
}
bool work(int x)
{
    for(int i=1;i<=n;i++) if(x!=i&&check(x,i)) return false;
    return true;
}
bool judge(int x)
{
    for(int i=1;i<=n;i++) if(hsh[i][len[i]]!=hsh[x][len[x]]&&check(x,i)) return false;
    return true;
}
int main()
{
    scanf("%d",&n); val[0]=1;
    for(int i=1;i<N;i++) val[i]=val[i-1]*131;
    for(int i=1;i<=n;i++)
    {
        scanf("%s",ch[i]+1);
        len[i]=strlen(ch[i]+1); 
        for(int j=1;j<=len[i];j++) hsh[i][j]=hsh[i][j-1]*131+(ll)(ch[i][j]-'a'); 
        b[i]=++cnt[hsh[i][len[i]]];
    }
    for(int i=1;i<=n;i++) if(work(i)) a[++ta]=i;
    for(int i=1;i<=n;i++) if(b[i]==2&&judge(i)) a[++ta]=i;
    for(int i=1;i<=ta;i++)
    {
        for(int j=1;j<=ta;j++)
        {
            if(i==j) continue;
            int x=a[i],y=a[j];
            for(int l=1;l<=min(len[x],len[y]);l++) if(hsh[y][l]==hsh[x][len[x]]-hsh[x][len[x]-l]*val[l]) lcp[i][j]=l;
        }
    }
    for(int i=1;i<(1<<ta);i++)
    {
        for(int j=0;j<ta;j++)
        {
            f[i][j]=1e9;
            if(i&(1<<j))
            {
                if(i==(1<<j)){f[i][j]=len[a[j+1]];continue;}
                for(int k=0;k<ta;k++) if((i-(1<<j))&(1<<k)&&j!=k) f[i][j]=min(f[i][j],f[i-(1<<j)][k]+len[a[j+1]]-lcp[k+1][j+1]);
            }
        }
    }
    int ans=1e9;
    for(int i=0;i<ta;i++) ans=min(ans,f[(1<<ta)-1][i]);
    printf("%d",ans);
    return 0;
}