题目描述就像做阅读理解一样...
首先看到后缀就心中不由得焦急,脑中浮现各种高级算法。
其实不然,这里其实没有用到过多的后缀性质,可以考虑转前缀,也就是把字符串反转。
让我们来理一下题意:
- 若在$x$之后存在是$\alpha$的后缀单词,那么就要付出$n*n$的代价来填$\alpha$。
- 若$\alpha $没有后缀,则填入代价为$x$。
- 在$[1,x-1]$中存在$\alpha $的后缀,下标最大的后缀位置为$y$,填入代价为$x-y$
第一种情况完全可以避免,不做考虑。
把最后构造的序列当成一棵树,
那么叶子节点一定包含它所有的后缀。
通过贪心可以证明,一定先填完一棵子树,才会去填另外一棵子树。
令$j$先于$i$填入,它们两个不属于同一棵子树,若现在$j$在$i$后填入,
那么$j$与它的父亲距离增加,$i$与$i$的孩子距离也增加,代价也就增加了。
同样地,可以通过不等式进行比较,证明子树小的先选。
接下来只需要考虑算法流程了。
反着建Trie树,统计结束结点,重新构造树,按上述方法统计答案即可。
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#define ll long long
#define gc getchar()
#define eps 1e-8
using namespace std;
const int N=6e5+5;
struct Trie{int son[26],s;}t[N];
char s[N];int cnt;
void ins()
{
int len=strlen(s+1),x=0;
for(int i=len;i;i--)
{
int y=s[i]-'a';
if(!t[x].son[y])t[x].son[y]=++cnt;
x=t[x].son[y];
}
++t[x].s;
}
struct edge{int y,next;}a[N<<1];int len,last[N];
void ins(int x,int y){a[++len]=(edge){y,last[x]};last[x]=len;}
void dfs0(int x,int fa)
{
if(t[x].s)ins(fa,x),fa=x;
for(int i=0;i<26;i++)
if(t[x].son[i])dfs0(t[x].son[i],fa);
}
int siz[N];
void dfs(int x)
{
siz[x]=1;
for(int k=last[x],y;k;k=a[k].next)
dfs(y=a[k].y),siz[x]+=siz[y];
}
int tmp=-1,q[N],r;ll ans;
bool cmp(int x,int y){return siz[x]<siz[y];}
void dfs1(int x,int lst)
{
int nw=++tmp,l=r+1;
ans+=tmp-lst;
for(int k=last[x];k;k=a[k].next)
q[++r]=a[k].y;
if(l<r)sort(q+l,q+r+1,cmp);
int rr=r;
for(int i=l;i<=rr;i++)
dfs1(q[i],nw);
}
int main()
{
int n;scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%s",s+1),ins();
dfs0(0,0);
dfs(0);
dfs1(0,0);
printf("%lld\n",ans);
return 0;
}
最后一次更新于2020-03-22
0 条评论