[BZOJ4567/Luogu3294][SCOI2016]背单词(Trie树,贪心)

发布于 2018-04-08  88 次阅读


本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[BZOJ4567/Luogu3294][SCOI2016]背单词(Trie树,贪心)

Description

Lweb 面对如山的英语单词,陷入了深深的沉思,“我怎么样才能快点学完,然后去玩三国杀呢?”。这时候睿智的凤老师从远处飘来,他送给了 Lweb 一本计划册和一大缸泡椒,他的计划册是长这样的:
—————
序号 单词
—————
1
2
……
n-2
n-1
n
—————
然后凤老师告诉 Lweb ,我知道你要学习的单词总共有 n 个,现在我们从上往下完成计划表,对于一个序号为 x 的单词(序号 1...x-1 都已经被填入):
1) 如果存在一个单词是它的后缀,并且当前没有被填入表内,那他需要吃 n×n 颗泡椒才能学会;
2) 当它的所有后缀都被填入表内的情况下,如果在 1...x-1 的位置上的单词都不是它的后缀,那么你吃 x 颗泡椒就能记住它;
3) 当它的所有后缀都被填入表内的情况下,如果 1...x-1的位置上存在是它后缀的单词,所有是它后缀的单词中,序号最大为 y ,那么你只要吃 x-y 颗泡椒就能把它记住。
Lweb 是一个吃到辣辣的东西会暴走的奇怪小朋友,所以请你帮助 Lweb ,寻找一种最优的填写单词方案,使得他记住这 n 个单词的情况下,吃最少的泡椒。

Tag

Trie树,贪心

解决思路

首先肯定是要尽量避免第一种情况的,那么就让一个串的所有后缀的位置一定优于这个串。所以可以想到把字符串反过来插入到Trie树中,这样我们就可以处理后缀的问题了。
把Trie树中所有是单词结尾的地方以及0号根节点单独提出来,建立一棵新的树。现在的问题是,如歌分配这些点的编号使得所有的儿子-父亲的编号之和最小。
贪心地想到,每一次向下走的时候,优先走size更小的子树,这样使得差值会尽量小。所以统计出size后,对每一个点的儿子按照size排序,优先走小的进行编号。
注意对根节点0的特殊处理

代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;

#define ll long long
#define mem(Arr,x) memset(Arr,x,sizeof(Arr))

const int maxTrie=600010;
const int maxAlpha=26;
const int inf=2147483647;

class Trie
{
public:
    int end;
    int son[maxAlpha];
    int id;
};

int n,nodecnt;
Trie T[maxTrie];
char str[maxTrie];
vector<int> Son[maxTrie];
ll Size[maxTrie];
ll Ans=0;
ll idcnt=0,Id[maxTrie];

void dfs(int u,int top);
void GetSize(int u);
void Calc(int u);
bool cmp(int a,int b);

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%s",str+1);
        int len=strlen(str+1);
        int now=0;
        for (int j=len;j>=1;j--)//建立Trie树
        {
            if (T[now].son[str[j]-'a']==0) T[now].son[str[j]-'a']=++nodecnt;
            now=T[now].son[str[j]-'a'];
        }
        T[now].end=1;T[now].id=i;
    }
    dfs(0,0);//第一遍dfs在Trie树上构出那棵只包含根节点和所有单词结尾节点的树
    GetSize(0);//第二遍dfs统计出每一个点的size
    Calc(0);//第三遍dfs按照size从小到大遍历,统计答案
    printf("%lld\n",Ans);
    return 0;
}

void dfs(int u,int top)
{
    if (T[u].end){
        Son[top].push_back(u);
        top=u;
    }
    for (int i=0;i<maxAlpha;i++) if (T[u].son[i]) dfs(T[u].son[i],top);
    return;
}

void GetSize(int u)
{
    Size[u]=1;
    int cnt=Son[u].size();
    for (int i=0;i<cnt;i++) GetSize(Son[u][i]),Size[u]+=Size[Son[u][i]];
    return;
}

void Calc(int u)
{
    sort(Son[u].begin(),Son[u].end(),cmp);//排序
    int cnt=Son[u].size();if (u!=0) Id[u]=++idcnt;
    for (int i=0;i<cnt;i++){
        Calc(Son[u][i]);Ans+=Id[Son[u][i]]-Id[u];
    }
    return;
}

bool cmp(int a,int b)
{
    return Size[a]<Size[b];
}

本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[BZOJ4567/Luogu3294][SCOI2016]背单词(Trie树,贪心)


HNCJ OIer 一枚