[HAOI2008] 玩具取名

形式化题目

字母表固定为 $\{\text{W},\text{I},\text{N},\text{G}\}$ 。给定一组替换规则，每条规则形如 $c \to xy$ ，其中 $c,x,y$ 都是字母表中的字母。

名字的生成方式是：先取单个字母作为初始名，然后反复执行「把当前串中的某一个字母按某条规则换成两个字母」。每执行一次替换，串长加 $1$ 。因此长度为 $L$ 的串恰好由 $L-1$ 次替换得到。

给定长度为 $L$ 的目标串 $S$ ，求所有满足「从该单字母出发，经过零次或多次替换能得到 $S$ 」的字母。按 $\text{W},\text{I},\text{N},\text{G}$ 的固定顺序输出，若一个都没有则报告无解。

$S$ 长度 $L\le 200$ ，每类字母的规则条数不超过 $16$ 。

暴力解法

思路

生成的每一步都只在串内做一次「一变二」，反过来看就是把相邻的两个字符折回成一个字符。于是问题的核心变成：

$S$ 的某个子串能否折叠成字母 $c$ ？

折叠一棵树如果根的替换是 $c \to xy$ ，那么左右两条分支覆盖的必然是 $S$ 中前后相邻的两段连续区间。原因是替换只把「一个字母」换成「两个相邻字母」，任何一个节点的子孙在最终串里始终是一段连续区间，兄弟之间按顺序紧挨着、不会交错。所以左右两半恰好切出一个分裂点。

于是可以直接写递归： $S[l..r]$ 折成 $c$ ，当且仅当

$l = r$ 且 $S[l] = c$ （长度 1，不需要任何替换）；或
存在规则 $c \to xy$ 与分裂点 $m \in [l, r-1]$ ，使 $S[l..m]$ 折成 $x$ 、 $S[m+1..r]$ 折成 $y$ 。

答案就是所有能让整体 $S[1..L]$ 折成的字母。

用样例验证一下：规则为 $W\to II$ 、 $I\to WW$ 、 $N\to WW$ 、 $G\to IG$ ，串为 IIII。

I 折成 $I$ （长度 1）。
II 折成 $W$ （规则 $W\to II$ ）。
III 用分裂点 $m=1$ ：左 I 折成 $I$ 、右 II 折成 $W$ ，需要规则 $I\to IW$ ，没有；用 $m=2$ ：左 II 折成 $W$ 、右 I 折成 $I$ ，需要 $W\to WI$ ，也没有。所以 III 折不成任何字母。
IIII 用 $m=2$ ：左、右都折成 $W$ ，需要规则 $c\to WW$ ，命中 $I\to WW$ 与 $N\to WW$ 。于是 IIII 折成 $I$ 或 $N$ 。

按 $W,I,N,G$ 顺序输出得到 IN，与样例一致。

代码

cpp

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/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-23 23:12
 * update_at: 2026-10-23 23:19
 */
// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
// 直接照“折叠的最后一步”递归：S[l..r] 折成 c，当且仅当存在规则 c -> xy 与分裂点 m，
// 使左半折成 x、右半折成 y。这里不做记忆化，重复子区间会被反复重算，
// 复杂度指数级，只适合 L <= 20 的小数据（正好对应 30% 部分分）。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MAXL = 205;   // L <= 200
const int MAXC = 4;     // 字母表只有 W I N G 四个

ll rule_cnt[MAXC];               // 每个字母的规则条数
vector<pair<int,int> > rule[MAXC]; // rule[c]：字母 c 的所有右部 (x, y)，元素是字母编号
char s[MAXL];                    // 1-indexed 的目标名字
ll n;                            // 名字长度 L

// 把字母映射到 0..3 的编号，顺序 W I N G
int to_id(char ch) {
    if (ch == 'W') return 0;
    if (ch == 'I') return 1;
    if (ch == 'N') return 2;
    return 3; // 'G'
}

char id_to_char[4] = {'W', 'I', 'N', 'G'};

// fold(c, l, r)：S[l..r] 能否折叠成单个字母 c
bool fold(int c, int l, int r) {
    if (l == r) {
        return s[l] == id_to_char[c];
    }
    for (auto &p : rule[c]) {           // 枚举最后一步替换 c -> x y
        int x = p.first;
        int y = p.second;
        for (int m = l; m < r; m++) {   // 枚举分裂点
            if (fold(x, l, m) && fold(y, m + 1, r)) {
                return true;
            }
        }
    }
    return false;
}

void read_data() {
    for (int c = 0; c < MAXC; c++) {
        cin >> rule_cnt[c];
    }
    for (int c = 0; c < MAXC; c++) {
        for (int k = 0; k < rule_cnt[c]; k++) {
            string t;
            cin >> t;
            rule[c].push_back(make_pair(to_id(t[0]), to_id(t[1])));
        }
    }
    string name;
    cin >> name;
    n = name.size();
    for (int i = 1; i <= n; i++) {
        s[i] = name[i - 1];
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    read_data();

    string ans;
    for (int c = 0; c < MAXC; c++) {
        if (fold(c, 1, n)) ans.push_back(id_to_char[c]);
    }
    if (ans.empty()) cout << "The name is wrong!" << "\n";
    else cout << ans << "\n";

    return 0;
}

复杂度

递归不做任何记忆化，同一对 $(c,l,r)$ 会在不同分支下被反复计算，最坏情况需要枚举 $L-1$ 层、每层有「规则数 $\times$ 分裂点」个选择，量级是指数级的。

瓶颈

fold(x, l, m) 的结果只与 $(x,l,m)$ 这三个参数有关，与「它是从哪个上层调用过来的」毫无关系。但纯递归每次都会重新算一遍同样的子问题。 $L\le 20$ 时还能勉强跑， $L=200$ 时这条路彻底走不通。

真正的浪费点只有一个：子区间的折叠结果没有被留下来复用。

正解

关键观察

把暴力里「 $S[l..r]$ 能折成 $c$ 」这个判断做成一个状态，记为 $C[l][r]$ （一个不超过 4 个元素的字母集合）。由上一节的分裂公式， $C[l][r]$ 只依赖长度严格更短的区间 $C[l][m]$ 和 $C[m+1][r]$ 。

既然依赖关系总是「短区间 $\to$ 长区间」，就不必再用递归，直接按区间长度从小到大把表填出来，每个状态只算一次。

思路

长度 1： $C[i][i] = \{S[i]\}$ 。长度 1 的串不需要任何替换，它本身就是那个字母。
长度 $\text{len} = 2 \ldots L$ ：对每个左端点 $l$ （右端点 $r = l+\text{len}-1$ ），枚举分裂点 $m \in [l, r-1]$ ，再枚举规则 $c \to xy$ ：若 $x \in C[l][m]$ 且 $y \in C[m+1][r]$ ，就把 $c$ 加入 $C[l][r]$ 。
答案： $C[1][L]$ 中的字母按 $W,I,N,G$ 顺序输出；为空则输出 The name is wrong!。

以样例的 IIII 为例，按填表顺序把各区间能折成的字母集合列在下表（行是区间长度，列是该长度下的所有区间）：

区间长度	长度内的所有区间及其集合
1	$[1,1]=\{I\}$ ， $[2,2]=\{I\}$ ， $[3,3]=\{I\}$ ， $[4,4]=\{I\}$
2	$[1,2]=\{W\}$ ， $[2,3]=\{W\}$ ， $[3,4]=\{W\}$
3	$[1,3]=\varnothing$ ， $[2,4]=\varnothing$
4	$[1,4]=\{I,N\}$

长度 2 的每个区间都是 II，命中规则 $W\to II$ ，得到 $W$ 。长度 3 找不到匹配（需要左半折成 $W$ 、右半折成 $I$ 即规则 $W\to WI$ ，或左 $I$ 右 $W$ 即 $I\to IW$ ，两条都不存在），为空。长度 4 时切在 $m=2$ ，左右两半都是 $W$ ，命中 $I\to WW$ 与 $N\to WW$ ，于是 $[1,4]$ 得到 $\{I,N\}$ 。

存储上用 can[l][r][c]（bool）最直白：三个下标分别是左端点、右端点、字母编号（ $W=0,I=1,N=2,G=3$ ）。规则只有四类，每类至多 16 条，用 rule[c] 存 $c$ 的所有右部，枚举时直接范围 for。

为什么按长度递增就够

递推 $C[l][r]$ 时只查 $C[l][m]$ 与 $C[m+1][r]$ ，它们的长度分别是 $m-l+1$ 和 $r-m$ ，都严格小于 $r-l+1$ 。所以外层循环按 $\text{len}$ 递增，内层状态被用到时一定已经算完，不需要考虑「先算哪一个」。

代码

cpp

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/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-23 23:12
 * update_at: 2026-10-23 23:19
 */
// 正解：区间 DP。can[l][r][c] 表示子串 S[l..r] 能否折叠成字母 c。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MAXL = 205;   // L <= 200
const int MAXC = 4;     // 字母表只有 W I N G 四个

ll len_limit[MAXC];            // 每个字母的规则条数
vector<pair<int,int> > rule[MAXC]; // rule[c]：字母 c 的所有右部 (x, y)，元素是字母编号
bool can[MAXL][MAXL][MAXC];    // can[l][r][c]：S[l..r] 能否折叠成字母 c
char s[MAXL];                  // 1-indexed 的目标名字
ll n;                          // 名字长度 L

// 把字母映射到 0..3 的编号，顺序与题目输出顺序一致：W I N G
int to_id(char ch) {
    if (ch == 'W') return 0;
    if (ch == 'I') return 1;
    if (ch == 'N') return 2;
    return 3; // 'G'
}

char id_to_char[4] = {'W', 'I', 'N', 'G'};

void read_data() {
    for (int c = 0; c < MAXC; c++) {
        cin >> len_limit[c];
    }
    for (int c = 0; c < MAXC; c++) {
        for (int k = 0; k < len_limit[c]; k++) {
            string t;
            cin >> t;
            rule[c].push_back(make_pair(to_id(t[0]), to_id(t[1])));
        }
    }
    string name;
    cin >> name;
    n = name.size();
    for (int i = 1; i <= n; i++) {
        s[i] = name[i - 1];
    }
}

void solve() {
    // 长度 1：不需要替换，只能是被折叠的那个字母本身
    for (int i = 1; i <= n; i++) {
        can[i][i][to_id(s[i])] = true;
    }

    // 按区间长度从小到大递推，保证用到的更短区间已经算好
    for (int len = 2; len <= n; len++) {
        for (int l = 1; l + len - 1 <= n; l++) {
            int r = l + len - 1;
            for (int m = l; m < r; m++) {   // 枚举分裂点：左半 S[l..m]，右半 S[m+1..r]
                for (int c = 0; c < MAXC; c++) {
                    if (can[l][r][c]) continue; // 已经能折成 c，跳过
                    for (auto &p : rule[c]) {
                        if (can[l][m][p.first] && can[m + 1][r][p.second]) {
                            can[l][r][c] = true;
                            break;
                        }
                    }
                }
            }
        }
    }
}

void print_answer() {
    string ans;
    for (int c = 0; c < MAXC; c++) {
        if (can[1][n][c]) ans.push_back(id_to_char[c]);
    }
    if (ans.empty()) cout << "The name is wrong!" << "\n";
    else cout << ans << "\n";
}

signed main() {
    ios::sync_with_stdio(false); cin.tie(0);
    read_data();
    solve();
    print_answer();
    return 0;
}

复杂度

状态数 $4L^2$ ，每个状态枚举 $O(L)$ 个分裂点、 $4$ 个字母与至多 $16$ 条规则，故

O(L^2 \cdot L \cdot 4 \cdot 16) = O(64L^3)

$L=200$ 时约 $1.7\times 10^8$ 次最内层比较量级，实测仅需 3–4 ms（内层是位判断并带提前 break）。空间 $O(4L^2)$ ，约 160 KB。

总结

这道题的关键不在「怎么搜」，而在把展开过程倒过来看：一步替换就是一变二，倒过来就是把相邻两段合并，于是每个区间的答案只由它的两半决定——这是典型的区间 DP 结构。

暴力递归把「区间能否折成 $c$ 」直接当递归算，问题在于同一区间被重复求值。
正解把这个判断做成状态 $C[l][r]$ ，按区间长度递增填表，每个状态只算一次，指数级降到 $O(L^3)$ 。

写代码时最容易漏的是 长度 1 的初始化： $L=1$ 时不需要任何替换，答案就是那个字母本身，只按 $\text{len}\ge 2$ 递推会输出错误结果。