Kris's Blog
0%

洛谷 P3883 [JLOI2008]棋局定式

发表于 更新于 分类于

分析

这题本质上还是个 AC 自动机的板子，只需要存下定式对应的名称然后输出就好了。不会 AC 自动机的可以去学习一下。

只是存在一个问题：如果直接建树字符集会过大，导致 MLE。

考虑到实际棋谱中会出现的字符其实很有限，可以对每一个字符建立唯一的映射。这样再建树就不会 MLE 了。

剩下的细节见代码。

代码

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
#include <cstring>
#include <iostream>
#include <queue>

const int MAX_N = 700050;
const int MAX_M = 2050;
const int CHA_SIZE = 35;

int tree[MAX_N][CHA_SIZE], exi[MAX_N], nxt[MAX_N], ans[MAX_M];
int tot;
std::string s[MAX_M];

int tt[255];  // 字符映射

void init();

void build();

void insert(std::string s, int c);

void query(std::string s);

int main() {
    std::ios::sync_with_stdio(false);
    init();

    int n, m;
    std::cin >> n >> m;

    auto* nam = new std::string[n + 5];
    for (int i = 1; i <= n; i++) {
        int k;
        std::cin >> k;
        std::getline(std::cin, nam[i]);  // 还有换行符未被 cin 读入
        std::getline(std::cin, nam[i]);

        for (int j = 1; j <= k; j++) {
            std::string x;
            std::cin >> x;
            s[i] += x;  // 将每个定式当作一个字符串
        }
        insert(s[i], i);
    }
    build();

    std::string k;
    for (int i = 1; i <= m; i++) {
        std::string s;
        std::cin >> s;
        k += s;  // 同理
    }
    query(k);

    for (int i = 1; i <= n; i++) {
        if (ans[i]) {  // 出现过就输出
            std::cout << nam[i] << '\n';
        }
    }

    return 0;
}

void build() {
    std::queue<int> q;
    for (int i = 0; i < CHA_SIZE; i++) {
        if (tree[0][i]) {
            q.push(tree[0][i]);
        }
    }
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        for (int i = 0; i < CHA_SIZE; i++) {
            if (!tree[x][i]) {
                tree[x][i] = tree[nxt[x]][i];
            } else {
                q.push(tree[x][i]);
                nxt[tree[x][i]] = tree[nxt[x]][i];
            }
        }
    }
}

void init() {
    int cnt = 0;
    for (int i = '1'; i <= '8'; ++i) {
        tt[i] = ++cnt;
    }
    tt['B'] = ++cnt;
    tt['K'] = ++cnt;
    tt['N'] = ++cnt;
    tt['P'] = ++cnt;
    tt['Q'] = ++cnt;
    tt['R'] = ++cnt;
    for (int i = 'a'; i <= 'h'; ++i) {
        tt[i] = ++cnt;
    }
    tt['x'] = ++cnt;
}

void insert(std::string s, int c) {
    int x = 0;
    for (int i = 0; s[i]; i++) {
        int ch = tt[s[i]];
        if (!tree[x][ch]) {
            tree[x][ch] = ++tot;
        }
        x = tree[x][ch];
    }
    exi[x] = c;
}

void query(std::string s) {
    int x = 0;
    for (int i = 0; s[i]; i++) {
        int ch = tt[s[i]];
        x = tree[x][ch];
        for (int j = x; j; j = nxt[j]) {
            ans[exi[j]]++;
        }
    }
}