SCOI2016Day1 第一道

题目链接

题目大意

这个题目的意思非常的模糊, 读到最后才理解了, 是确定一个字符串的编号,如果存在一个字符串后缀的编号\(>\)大于这个字符串,那么要付出\(n^2\)的巨额代价,否则有付出编号减去后缀最大编号的代价。

解题报告

首先后缀倒过来就是前缀,可以通过trie树+重建树得到字符串之间的后缀关系。

需要一个结论, 就是因为后缀靠后的代价太高, 显然需要让所有的后缀的编号都小于当前串。

在重构的树上, 有一个可以通过推广得到的结论, 就是编号一定先编完一棵子树再进入另外的一棵子树。

首先题目中“编号减去后缀最大的编号”相当于当前点的编号减去树上父亲节点的编号。

考虑二叉树的情况, 联想到’holidy’那个题目, 如下图(1)(2), 其中第一个图显然更优。

在二叉树中,显然先进入较短的一侧可以付出更小的代价, 所以推广到多叉树,先进入size较小的子树代价更小。

代码

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
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=int(a),nn=int(b);i<=nn;++i)
#define vep(i,a,b) for(int i=int(a),nn=int(b);i>=nn;--i)
#define xep(i,b) for(int i=0,nn=int(b);i<nn;++i)
#define mp make_pair
typedef pair<int,int> pii;
const int N=110001;
struct edge {
int nxt,to; edge(int nxt=0,int to=0)
:nxt(nxt),to(to) {}
} e[N];
int hed[N],tot,n,sn[N*5][26],na[N*5],cnt=1,rt=1;
int sz[N],rc; char s[N*5];
inline void add(int x,int y) {
e[++tot]=edge(hed[x],y), hed[x]=tot;
}
inline void rvs_ins(char *s,int id) {
int x=rt,no; vep(i,strlen(s)-1,0) {
no=s[i]-'a'; if (!sn[x][no]) sn[x][no]=++cnt;
x=sn[x][no]; if (i==0) na[x]=id+1;
}
}
void build(int x,int f) {
if (na[x]) add(f,na[x]), f=na[x];
xep(i,26) if (sn[x][i]) build(sn[x][i],f);
}
void dfs(int x) {
sz[x]=1; for (int i=hed[x];i;i=e[i].nxt)
dfs(e[i].to), sz[x]+=sz[e[i].to];
}
int v[N],od[N]; long long as;
void got(int x,int fm) {
if (x) v[x]=++rc, as+=v[x]-v[fm];
vector<pii> ss;
for(int i=hed[x];i;i=e[i].nxt)
ss.push_back(mp(sz[e[i].to],e[i].to));
sort(ss.begin(),ss.end());
xep(i,ss.size()) got(ss[i].second,x);
}
int main() {
scanf("%d",&n);
xep(i,n) scanf("%s",s), rvs_ins(s,i);
build(1,0), dfs(0), got(0,-1);
printf("%lld\n",as);
return 0;
}

留言