BZOJ

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.