「SCOI2016」背单词 解题报告

时间：2021-03-30 16:35:18

「SCOI2016」背单词

出题人sb

题意有毒

大概是告诉你，你给一堆n个单词安排顺序

如果当前位置为x

当前单词的后缀没在这堆单词出现过，代价x

这里的后缀是原意，但不算自己，举个例子比如abc的后缀是bc和c

否则

如果它的后缀(指在n个单词中的)在1~x-1全部出现了，代价为x-最后一个后缀的位置y

如果没有全部出现，代价n^2

看我气的连latex都懒得用了

然后你发现按后缀建字典树就可以了

然后你发现直接按子树大小贪心就可以了

但是我一开始偷懒就直接在trie上贪心走子树，这样是不行的，大小是错误的

得把关键点树建出来做

Code:

#include <cstdio>

#include <cstring>

#include <vector>

#include <algorithm>

#define ll long long

const int N=6e5+10;

std::vector <int> Edge[N];

char s[N];

int ch[N][26],endro[N],tot;

int n,clock=-1,siz[N];

ll ans;

void ins()

{

    scanf("%s",s+1);

    int now=0,len=strlen(s+1);

    for(int i=len;i;i--)

    {

        int c=s[i]-'a';

        if(!ch[now][c]) ch[now][c]=++tot;

        now=ch[now][c];

    }

    endro[now]=1;

}

void dfs0(int now,int anc)

{

    if(endro[now]) Edge[anc].push_back(now),anc=now;

    for(int i=0;i<26;i++)

        if(ch[now][i])

            dfs0(ch[now][i],anc);

}

void dfs(int now)

{

    siz[now]=1;

    for(int i=0;i<Edge[now].size();i++)

        dfs(Edge[now][i]),siz[now]+=siz[Edge[now][i]];

}

bool cmp(int x,int y){return siz[x]<siz[y];}

void dfs(int now,int las)

{

    int tim=++clock;

    ans=ans+tim-las;

    std::sort(Edge[now].begin(),Edge[now].end(),cmp);

    for(int i=0;i<Edge[now].size();i++)

        dfs(Edge[now][i],tim);

}

int main()

{

    scanf("%d",&n);

    for(int i=1;i<=n;i++) ins();

    dfs0(0,0);

    dfs(0);

    dfs(0,0);

    printf("%lld\n",ans);

    return 0;

}

2019.3.4

相关文章