BZOJ 4567 背单词

发表于 | 更新于

Link

Solution

3) 当它的所有后缀都被填入表内的情况下，如果 1...x-1的位置上存在是它后缀的单词，所有是它后缀的单词中，序号最大为 y ，那么你只要吃 x-y 颗泡椒就能把它记住。

序号就是位置，位置就是序号。呵呵 第一种情况可以避免。 对反串建Trie,就可以DFS贪心地求第二、三种情况的最优解。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include "lucida"
using std::sort;
using std::reverse;
using std::fill;
const int MAXSUM=510000+11,MAXN=100000+11;
namespace trie {
	struct Node {
		Node *son[26];int id;
		Node(int id):id(id) {
			fill(son,son+26,(Node*)0);
		}
		Node *&next(char c) {
			return son[c-'a'];
		}
		void *operator new(size_t) {
			static Node *Me=alloc(Node,MAXSUM);//static.
			return Me++;
		}
	};
	struct Trie {
		typedef Node *Iter;
		Node *root;
		Trie():root(new Node(0)) {}
		void Insert(char *s,int len,int id) {
			Node *pos=root;
			for(int i=1;i<=len;++i) {
				pos=pos->next(s[i])?pos->next(s[i]):(pos->next(s[i])=new Node(-1));
			}
			pos->id=id;
		}
	};
}using trie::Trie;
int sz[MAXN],fa[MAXN],dc,dfn[MAXN];
array<int> son[MAXN];
bool cmp(const int &a,const int &b) {
	return sz[a]<sz[b];
}
void Build(Trie::Iter pos,int last) {
	if(~pos->id) {
		if(~last) {
			fa[pos->id]=last;
			son[last].push_back(pos->id);
		}
		last=pos->id;
	}
	for(char c='a';c<='z';++c) {
		if(pos->next(c)) {
			Build(pos->next(c),last);
		}
	}
}
void GetSize(int pos) {
	sz[pos]=1;
	for(size_t i=0;i<son[pos].size();++i) {
		int u=son[pos][i];
		GetSize(u);
		sz[pos]+=sz[u];
	}
	sort(son[pos].begin(),son[pos].end(),cmp);
}
int64 DFS(int pos) {
	dfn[pos]=++dc;
	int64 res=dfn[pos]-dfn[fa[pos]];
	for(size_t i=0;i<son[pos].size();++i) {
		int u=son[pos][i];
		res+=DFS(u);
	}
	return res;
}
int main() {
	freopen("input","r",stdin);
	static char s[MAXSUM];
	int n;is>>n;
	Trie tri;
	for(int i=1;i<=n;++i) {
		is>>(s+1);int len=strlen(s+1);
		reverse(s+1,s+1+len);
		tri.Insert(s,len,i);
	}
	Build(tri.root,-1);
	GetSize(0);
	int64 Ans=DFS(0);
	os<<Ans<<'\n';
	return 0;
}