「SCOI2016」背单词 https://loj.ac/problem/2012
出题人 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
来源: http://www.bubuko.com/infodetail-2976027.html