题解 [SCOI2016] 背单词

题意

题目链接： 传送门

题目大意是给一些互不相同的字符串，对于第$ i $个字符串 $ a_i $ ,它对答案的贡献是：

1. 若存在一个字符串$ a_j $，满足 $ a_j $ 是 \(a_i\) 的后缀且 $ j>i $，则贡献为 $ n^2 $
2. 若 \(a_i\)的所有后缀均不出现在字符串序列中，则贡献为 $ i $
3. 若 \(a_i\)的所有后缀均不出现在$ a_i$后，记距离 \(a_i\)最近的后缀为 \(a_j\),则贡献为 \(i-j\)

希望将其排序，使得答案最小

Solution

做法：贪心+Trie

不难发现题目中给出的前两条规则并没有意义，对于规则1，可以把\(a_i\)的后缀放到\(a_i\)前，显然这是可以做到的。对于规则2，可以等效为规则3中 \(j=0\)的情况，所以实际上我们希望一个字符串离它的后缀尽可能的近。
对于一个字符串 $ ai$ 它的后缀应当恰好顺次排列在它的前面，若这样的字符串组的大小为$ Size $，显然 $ Size $越小的应当被放到前面，我们假设这组字符串的中第一个字符串位于 \(i\) ，则这一组所产生的贡献应是 \(i+Size-1\)，那么总的贡献显然只与 \(i\)的位置有关，根据贪心的思想排序即可。

接下来考虑如何处理后缀（听说这题可以后缀数组？），发现并不是很好做，于是想到将字符串翻转，变为前缀处理。

注意到字符串总长 $ len<=510000$，可以用考虑建立字典树。

上述的排序方式体现到trie上，即使按每棵子树的大小排序，因为对于一个确定前缀 $ pre$ ,它所对应的字符串组中 \(Size\) 小的应该被放在前面。（即被优先遍历）

我们只关心各个字符串之间的关系（已经通过trie建立），并不关心字符串具体的内容，从而发现我们可以删去不作为任何字符串结尾的节点，考虑重新建树，仅加入字符串的结尾节点。

然后就可以统计答案了。

先dfs求一下每棵子树的 $Size $ ，对于每个节点，按\(Size\)从小到大排列它的子树，然后再求每个节点的dfs序，依据规则3统计答案即可，注意开ll

#include
#define rep(a,b,c) for (int a=b;a<=c;a++)
#define per(a,b,c) for (int a=b;a>=c;a--)
using namespace std;
typedef long long ll;
template  inline void read(T &x){
    ll f = 1;x = 0;char ch = getchar();
    while (!isdigit(ch)){if (ch == '-')f = -1;ch = getchar();}
    while (isdigit(ch)){x = (x << 1)+(x << 3)+(ch ^ 48);ch = getchar();}
    x *= f;
}
const int MAXN=550000;

int n;
ll SIZE[MAXN];
inline bool cmp(int x,int y)
{
    return SIZE[x] Son[MAXN];
   
  inline void insert(char *st)
  {
  	int Len=strlen(st),pos=0;
  	per(i,Len-1,0)
  	{
  		int ch=st[i]-'a';
  		if(!tmp[pos][ch])tmp[pos][ch]=++tot;
  		pos=tmp[pos][ch];
  	}
  	end[pos]=1;
  }
  
  inline void rebuild(int pos,int fa) 
  {
  	if(end[pos])
  		Son[fa].push_back(pos),fa=pos;		
  	rep(i,0,25) 
  		if(tmp[pos][i])rebuild(tmp[pos][i],fa);
  
  }
  inline void Sum(int pos)
  {
  	SIZE[pos]=1;
  	int L=Son[pos].size();
  	rep(i,0,L-1)
  	{	
  		Sum(Son[pos][i]);
  		SIZE[pos]+=SIZE[Son[pos][i]];
  	}
  	sort(Son[pos].begin(),Son[pos].end(),cmp);
  }
  inline void dfs(int pos)
  {
  	dfn[pos]=cnt++;
  	int L=Son[pos].size();
  	rep(i,0,L-1)
  	{
  		ans+=cnt-dfn[pos];
  		dfs(Son[pos][i]);
  	}
  }
};
node Trie;
int main()
{
  read(n);
  rep(i,1,n)
  {
  	char st[MAXN];
  	scanf("%s",st);
  	Trie.insert(st);
  }
  
  Trie.rebuild(0,0);
  Trie.Sum(0);
  Trie.dfs(0);
  printf("%lld\n",Trie.ans);
  
  return 0;