题解 P3294 【[SCOI2016]背单词】

# 题意解释（本题最重要的部分） ~~本篇题解过于详细，适合初学者食用~~ 给你一些字符串，让你对其进行排列，使得按以下规则花费最少(然而题意真的不清楚，很容易就让人以为字符串的顺序是排好的) > （$x$为字符串在自行排定的序列中的位置，当前字符串为$a$) > 1.如果$a$存在后缀且a的后缀在a之后，花费$+=n^2$ > 2.如果$a$不存在后缀则花费$+=x$ > 3.设$y$为$a$之前离其最近的是$a$的后缀的字符串的位置，$a$存在后缀且$a$的后缀在$a$之前，则花费$+=x-y$ 经过转化题意就比较显然了，但是我们如果仔细读题我们发现1，2规则其实完全没有必要。 规则1我们只要把$a$的后缀放在$a$之前就好了，这样肯定优于放在$a$的后面因为$x-y$的值最大只能是n-1显然优于$n^2$ 规则2我们发现其实就是规则三中$y=0$的特殊情况，直接当规则3来处理就好 # 大体思路 看到后缀我们显然首先想到的是后缀数组，但是本蒟蒻太弱了不会怎么办？？？（~~而且本蒟蒻也不知道本题能不能用后缀数组~~） 我们把字符串翻个顺序就会发现后缀其实就是前缀，所以我们可以翻转字符串，处理前缀。 而处理前缀我们首先就会想到trie字典树，座椅本题我们采用建立trie字典树的做法。 看懂题目的规则之后我们发现可以贪心的求解此题，只要让字符串的后缀与字符串之间所隔的字符串数目最小即可 所以第一步我们建立一颗trie树 第二步我们发现一个字符串有可能有很多后缀，所以我们需要判重，这里使用**并查集** + 优于字符串的后缀与字符串之间存在有向的关系，便建立一张有向图。$x->y$代表$x$是$y$的后缀 因为要保证字符串与字符串的后缀之间距离最小所以贪心的选取以x为根的最小的子树 （使用vector在算出每棵子树大小后进行排序即可） 最后按照规则求和 # 求和时使用dfs序的正确性的证明 ## 经WQY查阅无误^_^ 如果你有认真看我的或其他人的题解，你可以发现我们在最后求和的时候是按照dfs序的。那么为什么？（~~我不会~~） 所以我在夏令营时找了wqy神仙请教。 >考虑建出一棵树之后，对于构建的任意合法的序列，都满足i的父亲一定在i之前出现，i的孩子们都一定在i之后出现 >先尝试证明dfs序一定最优，对于以同一深度的节点为根的子树，在一颗中找一个叶子节点j,在另一颗里找一个根节点i(当前序列中j所在的子树的根在i之前出现 >假设j<i的时候代价最小，尝试将j放在i的后面，此时i<j。那么我们发现如果j放在i与i的孩子们之间，i的孩子们和i的距离都会加1，所以总代价会增加，而j和j的父亲的距离一定也会增加，所以总代价也会增加 >所以对于j所在子树的根比i在序列中出现的早的情况，j<i的情况是最优的 >那么每个子树形成了一段连续的区间，对于每个节点进行调整，最后我们发现形成了一个dfs序(有时别的序列也会和dfs序列一样优秀，但是此处证明的是dfs序列是最优解之一，不是唯一解 >接下来再证明先遍历子树小的更优秀。 >WQY: >月明风清 2019.11.4 21:28:04 >因为你所有的size排序之后 >月明风清 2019.11.4 21:28:17 >第i个根节点的贡献是前面所有树的size之和 >所以要排序 >综上所述，当我们进行dfs序且按子树大小排序时，求出代价即为最优。 >Q.E.D 感谢wqy，给了我很大的帮助[wucstdio](https://www.luogu.org/space/show?uid=54214) # CODE ```cpp #include <iostream> #include <cstdio> #include <cstring> #include <vector> #include <algorithm> using namespace std; #define N 510050 #define M 100050 #define ll long long ll ans=0; char x[N]; int n,cnt,bo[N],tot=1,trie[5000050][27],fa[N],id[N],son[N],num; vector<int>tu[N]; int read() { int s=0,p=1; char ch=getchar(); while(ch<'0' || ch>'9') { if(ch=='-')p=-1; ch=getchar(); } while(ch>='0' && ch<='9') { s=(s<<1)+(s<<3)+(ch^48); ch=getchar(); } return s*p; } int find(int x) { if(fa[x]==x)return fa[x]; else return fa[x]=find(fa[x]); } void insert(char *s,int bh) { int l=strlen(s); int u=1; for(int i=l-1;i>=0;i--) { int c=s[i]-'a'; if(!trie[u][c])trie[u][c]=++tot; u=trie[u][c]; } bo[u]=bh; } void make(int x) { for(int i=0;i<26;i++) { int v=trie[x][i]; if(v) { if(!bo[v]) { fa[v]=find(x); } else { tu[bo[find(x)]].push_back(bo[v]); } make(v); } } } int cmp(int x,int y) { return son[x]<son[y]; } void sonsum(int x) { son[x]=1; for(vector<int> :: iterator it=tu[x].begin();it!=tu[x].end();it++) { int v=*it; sonsum(v); son[x]+=son[v]; } sort(tu[x].begin(),tu[x].end(),cmp); } void dfs(int x) { id[x]=num++; for(vector<int> :: iterator it=tu[x].begin();it!=tu[x].end();it++) { int v=*it; ans+=num-id[x]; dfs(v); } } void dfss(int x) { for(vector<int> :: iterator it=tu[x].begin();it!=tu[x].end();it++) { int v=*it; cout<<v<<endl; dfss(v); } } int main() { n=read(); for(int i=1;i<=n;i++) { scanf("%s",x); insert(x,i); } for(int i=1;i<=tot;i++)fa[i]=i; make(1); sonsum(0);dfs(0); printf("%lld",ans); return 0; } ``` 并查集去重的思路来源于[此篇blog](https://www.luogu.org/blog/communist/solution-p3294)