Loading [MathJax]/jax/output/HTML-CSS/jax.js
Codechef 12.5 LEBOXES meet-in-the-middle+DP
Codechef 11.10 BAKE 树状数组

Codechef 12.4 TSUBSTR 后缀自动机+Trie

shinbokuow posted @ 9 年前 in Something with tags 后缀自动机 Trie , 1233 阅读

 

题目大意:
给定一棵n个点的有根树,每个节点上都有一个字母,我们说一个字符串出现在这棵树上当且仅当这个字符串能够由树上一条深度递增的路径中的节点上的字母顺次连接起来形成。首先求出现在这棵树上的字符串集合的大小,然后有Q组询问,每次给定一个字母之间的字典序大小,求字符串集合中的字典序第k小的字符串。:
数据范围:n250000,q50000,1k<263,总输出大小不超过800KB。:
算法讨论:
我们不妨考虑后缀自动机在字典树上的拓展,对于每个节点我们都从他的树上的父亲结束插入的节点上开始插入,这样用一次BFS就能完成构造。
后缀自动机可以被看成一张拓扑图,从根节点出发的每条路径都对应着一个子串,那么我们只需要用一次拓扑序动态规划就能求出后缀自动机上从每个节点出发能走出的路径条数了。
对于每组询问,我们可以从根节点出发,类似树上二分的过程,每次按照字母的字典序大小开始走,由于总输出的大小是有限的,所以复杂度是有保证的。
时空复杂度:
时间复杂度O(n+q+800000),空间复杂度O(n|α|)
代码:
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
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
#include <cstdio>
#include <cstring>
#include <cctype>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
#define N 250010
int pa[N << 1], len[N << 1], tr[N << 1][26], cnt, root;
int newnode(int _len) {
    len[++cnt] = _len;
    return cnt;
}
char ch[N];
int head[N], nxt[N << 1], to[N << 1];
void addedge(int a, int b) {
    static int q = 1;
    to[q] = b;
    nxt[q] = head[a];
    head[a] = q++;
}
void make(int a,int b) {
    addedge(a, b);
    addedge(b, a);
}
void dfs(int x, int dep, int fa, int last) {
    static int p, np, q, nq, temp, y;
    y = ch[x] - 'a';
    if ((q = tr[last][y])) {
        if (len[q] != dep) {
            temp = newnode(dep);
            pa[temp] = pa[q];
            pa[q] = temp;
            memcpy(tr[temp], tr[q], sizeof tr[q]);
            for (p = last; p && tr[p][y] == q; p = pa[p])
                tr[p][y] = temp;
            last = temp;
        }
        else
            last = q;
    }
    else {
        np = newnode(dep);
        for (p = last; p && !tr[p][y]; p = pa[p])
            tr[p][y] = np;
        if (!p)
            pa[np] = root;
        else {
            if (len[q = tr[p][y]] == len[p] + 1)
                pa[np] = q;
            else {
                nq = newnode(len[p] + 1);
                pa[nq] = pa[q];
                pa[q] = pa[np] = nq;
                memcpy(tr[nq], tr[q], sizeof tr[q]);
                for (; p && tr[p][y] == q; p = pa[p])
                    tr[p][y] = nq;
            }
        }
        last = np;
    }
    for (int j = head[x]; j; j = nxt[j])
        if (to[j] != fa)
            dfs(to[j], dep + 1, x, last);
}
int in[N << 1];
int q[N << 1], fr, ta; 
ll f[N << 1];
char per[26];
void getAns(int x, ll k) {
    if (k == 1)
        return;
    --k;
     
    for (int i = 0; i < 26; ++i) {
        if (f[tr[x][per[i] - 'a']] >= k) {
            putchar(per[i]);
            getAns(tr[x][per[i] - 'a'], k);
            return;
        }
        else
            k -= f[tr[x][per[i] - 'a']];
    }
}
int main() {
#ifndef ONLINE_JUDGE
    freopen("tt.in", "r", stdin);
#endif
    int n, Q;
    cin >> n >> Q;
    scanf("%s", ch + 1);
    int a, b, i, j;
    for (i = 1; i < n; ++i) {
        scanf("%d%d", &a, &b);
        make(a, b);
    }
     
    root = newnode(0);
     
    dfs(1, 1, -1, root);
    for (i = 1; i <= cnt; ++i)
        for (j = 0; j < 26; ++j)
            if (tr[i][j])
                ++in[tr[i][j]];
     
    q[ta++] = 1;
    while (fr != ta) {
        i = q[fr++];
        for (j = 0; j < 26; ++j)
            if (tr[i][j]) {
                if (!(--in[tr[i][j]]))
                    q[ta++] = tr[i][j];
            }
    }
    for (i = cnt - 1; i >= 0; --i) {
        f[q[i]] = 1;
        for (j = 0; j < 26; ++j)
            if (tr[q[i]][j])
                f[q[i]] += f[tr[q[i]][j]];
    }
         
    ll total = f[1];
     
    cout << total << endl;
     
    ll k;
    while (Q--) {
        scanf("%s%I64d", per, &k);
        if (k > total)
            puts("-1");
        else {
            getAns(1, k);
            puts("");
        }
    }
     
    return 0;
}

 


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter