题目链接

loj#2012. 「SCOI2016」背单词

题解

题面描述有点不清楚.

考虑贪心

type1的花费一定不会是优的，不考虑，

所以先把后缀填进去,对于反串建trie树，

先填父亲再填儿子,这样每个单词的后缀填完了才会被填。

不是单词结束点的点是没用的，去掉

根据直觉，填单词和dfs序有关，所以应该先填Size小的

根据贪心，先填Size小的儿子。因为将Size小的先填可以减少后面儿子的代价

而先填大的会增加代价。

代码

#include<queue>

#include<cstdio>

#include<cstring>

#include<algorithm> 

inline int read() {

	int x = 0,f = 1;

	char c = getchar();

	while(c < '0' || c > '9')c = getchar();

	while(c <= '9' && c >= '0') x = x * 10 + c - '0',c = getchar();

	return x * f;

}

const int maxn = 500007;

char s[maxn];

int tag[maxn],ch[maxn][26];

int tot = 0;

void insert(char *s) {

	int len = strlen(s + 1),now = 0;

	for(int i = len;i >= 1;-- i) {

		int t = s[i] - 'a';

		if(!ch[now][t]) ch[now][t] = ++ tot;

		now = ch[now][t];

	}

	tag[now] = 1;

} 

struct node {

	int v,next;

} edge[maxn << 1];

int num = 0,head[maxn];

inline void add_edge(int u,int v) {

	edge[++ num].v = v;edge[num].next = head[u],head[u] = num;

}

int siz[maxn];

int size[maxn];

void dfs(int x,int fa) {

	if(tag[x]) siz[fa] ++,add_edge(fa,x),fa = x;

	for(int i = 0;i < 26;++ i) if(ch[x][i]) dfs(ch[x][i],fa);

	size[x] = siz[x];

	for(int i = head[x];i;i = edge[i].next) {

		size[x] += size[edge[i].v];

	}

}

#define pr std::pair<int,int>

#define mp std::make_pair

long long ans = 0;

std:: priority_queue<pr>q;

void solve() {

	q.push(mp(0,0)); int cnt = 1;

	while(!q.empty()) {

		int x = q.top().second; q.pop();

		cnt = cnt + siz[x] - 1;

		ans += cnt;

		for(int i = head[x];i;i = edge[i].next) {

			q.push(mp(-size[edge[i].v],edge[i].v));

		}

	}

}

int main() {

	int n  = read();

	for(int i = 1;i <= n;++ i) {

		scanf("%s",s + 1);

		insert(s);

	}

	dfs(0,0);

	solve();

	printf("%lld\n",ans);

	return 0;

}