洛谷P3294，一道思路奇妙的Trie树题目

[SCOI2016]背单词

题目传送门

前言

参考这篇博客

题目大意

输入 $n$ 个单词，要求我们给他进行重新排列，使得按以下规则花费最小

1. 如果存在一个单词是它的后缀，并且当前没有被填入表内，那花费 $+= n*n$ ；
2. 当它的所有后缀都被填入表内的情况下，如果在 $1 … x-1$ 的位置上的单词都不是它的后缀，那么花费 $+= x$ ；
3. 当它的所有后缀都被填入表内的情况下，如果 $1 … x-1$ 的位置上存在是它后缀的单词，所有是它后缀的单词中，序号最大为 $y$ ，那么花费 $+=x-y$ 。

思路

读懂题意之后，可以将题意转化为

使得每个单词的后缀都在这个单词前面，且距离尽量近。

题目中需要的后缀，但是后缀不太好处理，于是我们想到把单词反转，用前缀表示后缀。以此可以建出 Trie 树

建好 Trie 树之后，我们呢还需要对这棵树进行重构操作，忽略上面的非单词结尾的点，将每个单词的结尾位置进行相连，即单词之间直接相连。

之后，我们还需要利用 dfs 再对这棵树进行重构，具体内容是将每个节点的子节点进行排序，按以子节点为根的子树的节点数从小到大的规则进行排序。

然后对这样重构之后的树直接进行遍历就是最后的序列，即 dfs 序就是最终的序列。使用 dfs 即可得到答案。

dfs 序为什么正确？

考虑重新建树之后，i节点的子树中的所有节点的后缀都是 $i$

如果同一深度上有不止一棵子树，那么我们先在一棵上取出一个叶子节点 $j$ ，再取出一个根节点 $i$ ，我们发现如果 $j>i$ 的话肯定不如 $i<j$ 优秀

因为调整之后i的子树上所有节点对花费的贡献 $-=$ 子树大小， $j$ 对花费的贡献 $+1$ ，所以我们可以看到 $j>i$ 的花费 $<=i>j$ 的情况

最后我们经过所有的调整可以发现序列变成了 dfs 序

所以 dfs 序最优

最后答案记得用 long long .

代码

#include<cstdio>
#include<algorithm>
#include<map>
#include<queue>
#include<cstring>
#include<vector>
#include<iostream>
#include<string>
#define Inf 0x3f3f3f3f
using namespace std;
typedef long long LL;
typedef pair<int,int> P;
const int MAXX=510005;

int n;
char s[MAXX];
int trie[MAXX][26],id_cnt;
bool vis[MAXX];
int num[MAXX];
vector<int> to[MAXX];

void insert(){
	int now=0,len=strlen(s+1);
	for(int i=1;i<=len;++i){
		if(trie[now][s[i]-'a']==0)
			trie[now][s[i]-'a']=++id_cnt;
		now=trie[now][s[i]-'a'];
	}
	vis[now]=true;
}

void rebuild(int now,int last){
	if(vis[now]){
		to[last].emplace_back(now);
		for(int i=0;i<26;++i)
			if(trie[now][i])
				rebuild(trie[now][i],now);
	}
	else{
		for(int i=0;i<26;++i)
			if(trie[now][i])
				rebuild(trie[now][i],last);
	}
}

bool cmp(int jj,int kk){return num[jj]<num[kk];}

void dfs(int now){
	int si=to[now].size();
	num[now]=1;
	for(int i=0;i<si;++i){
		dfs(to[now][i]);
		num[now]+=num[to[now][i]];
	}
	sort(to[now].begin(),to[now].end(),cmp);
}

int dfn[MAXX],dfn_cnt=-1;

LL getans(int now,int last){
	LL ret=0;
	dfn[now]=++dfn_cnt;
	if(last==0)
		ret+=dfn[now];
	else
		ret+=dfn[now]-dfn[last];
	int si=to[now].size();
	for(int i=0;i<si;++i)
		ret+=getans(to[now][i],now);
	return ret;
}

inline void solve(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		scanf("%s",s+1);
		reverse(s+1,s+strlen(s+1)+1);
		insert();
	}
	
	rebuild(0,0);
	dfs(0);
	
	printf("%lld\n",getans(0,0));
}

int main(){
//	int t;scanf("%d",&t);
//	while(t--)
		solve();
	
	return 0;
}

总结

这道题里面的思维非常的妙，使用前缀来表示后缀，以此可以直接使用 Trie 树。

还有对 Trie 树进行重构，都非常的巧妙。