BZOJ 3998

传送门


我就放图不说话… 喂,110吗?真是日了评测机了…

恩…首先后缀自动机是要建的吧…

设$Cnt_i$为以$i$为结尾的子串个数

然后若$T=0$,则以后缀自动机的一个节点为结尾的子串再多也只能算一个,所以$Cnt_i$全部赋为$1$

若$T=1$
$$Cnt_i=\sum_{fa_j=i}Cnt_j+1$$

然后统计一下经过每个节点的子串个数,设它为$Sum_i$
$$Sum_i=Cnt_i+\sum_{j=son_i}Cnt_j$$

然后对自动机进行一遍DFS,先挑字典序小的走,若能走就输出并继续,这样就可以了…


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
86
87
88
89
90
91
92
93
94
95
96
97
98
program bzoj_3998;
const maxn=1000005;
var fa,cnt,sum,l,seq,c:array[0..maxn]of longint;
son:array[0..maxn,1..26]of longint;
n,t,k,tot,last,p,q,np,nq:longint;
ch:char;
procedure insert(c:longint);
begin
inc(tot);
np:=tot;
cnt[np]:=1;
p:=last;
last:=tot;
l[np]:=l[p]+1;
while (p<>0)and(son[p,c]=0) do
begin
son[p,c]:=np;
p:=fa[p];
end;
if p=0 then fa[np]:=1 else
begin
q:=son[p,c];
if l[p]+1=l[q] then fa[np]:=q else
begin
inc(tot);
nq:=tot;
son[nq]:=son[q];
fa[nq]:=fa[q];
fa[q]:=nq;
fa[np]:=nq;
l[nq]:=l[p]+1;
while (p<>0)and(son[p,c]=q) do
begin
son[p,c]:=nq;
p:=fa[p];
end;
end;
end;
end;
procedure init;
var i,j:longint;
begin
for i:=1 to tot do c[i]:=0;
for i:=1 to tot do inc(c[l[i]]);
for i:=1 to n do inc(c[i],c[i-1]);
for i:=tot downto 1 do
begin
seq[c[l[i]]]:=i;
dec(c[l[i]]);
end;
for i:=tot downto 1 do
begin
p:=seq[i];
if t=1 then inc(cnt[fa[p]],cnt[p]) else cnt[p]:=1;
end;
cnt[1]:=0;
for i:=tot downto 1 do
begin
p:=seq[i];
sum[p]:=cnt[p];
for j:=1 to 26 do if son[p,j]<>0 then inc(sum[p],sum[son[p,j]]);
end;
end;
procedure dfs(t,k:longint);
var i:longint;
begin
if k<=cnt[t] then exit;
dec(k,cnt[t]);
for i:=1 to 26 do
if son[t,i]<>0 then
begin
if k<=sum[son[t,i]] then
begin
write(chr(i+96));
dfs(son[t,i],k);
exit;
end else dec(k,sum[son[t,i]]);
end;
end;
begin
n:=0;
tot:=1;
last:=1;
while not eoln do
begin
inc(n);
read(ch);
insert(ord(ch)-96);
end;
readln(t,k);
init;
if k>sum[1] then write('-1') else dfs(1,k);
writeln;
end.