[NOIP 2000 提高组] 单词接龙（疑似错题）

形式化题目

给定 $n$ 个单词和一个起始字母。用这些单词拼接一条“龙”：

第一个单词必须以起始字母开头；
相邻单词 $A \to B$ 必须存在一个长度 $k \geqslant 1$ ，使得 $A$ 的后 $k$ 个字符等于 $B$ 的前 $k$ 个字符，且 $k$ 严格小于 $A$ 、 $B$ 两者的长度（即一个单词不能被另一个完全包含）；
重合部分在龙中只出现一次，龙的总长度 = 各单词长度之和 - 各次重合长度之和；
每个单词最多使用两次。

要求输出能拼出的最长龙的长度。

思路

这个暴力把每一步接龙看成选择序列：每一层递归选择“接哪个单词、采用哪一种合法重叠长度”，拼完一条合法龙就更新答案：

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
92
93
94/**
 * 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-08-13 13:32
 * update_at: 2026-08-13 13:32
 */
// brute.cpp：小数据暴力解，把每一步接龙看成选择序列来递归枚举。
// 每一层递归做两个选择：接哪个单词、采用哪种合法重叠长度。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 25;

int n;
string word[MAXN];                    // 单词，下标从 1 开始
vector<int> overlap_list[MAXN][MAXN]; // overlap_list[i][j]：i 接 j 的所有合法重叠长度
int used[MAXN];                       // used[i]：单词 i 已经使用的次数（最多 2 次）
char start_ch;                        // 龙的开头字母
int ans;                              // 最长接龙长度

// 判断 s 的后 k 个字符是否等于 t 的前 k 个字符。
bool same_overlap(const string &s, const string &t, int k) {
    int len_s = (int)s.size();
    for (int i = 0; i < k; i++) {
        if (s[len_s - k + i] != t[i]) {
            return false;
        }
    }
    return true;
}

// 预处理：枚举 1 <= k <= min(|s|,|t|) - 1 的所有合法重叠长度。
// 上界排除“一个单词被另一个完全包含”的非法情况。
void build_overlap_list() {
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            overlap_list[i][j].clear();
            int limit = min((int)word[i].size(), (int)word[j].size()) - 1;
            for (int k = 1; k <= limit; k++) {
                if (same_overlap(word[i], word[j], k)) {
                    overlap_list[i][j].push_back(k);
                }
            }
        }
    }
}

// 暴力 DFS：这一层先选下一个单词 nxt，再选一种合法重叠长度。
// 与最终解不同：这里保留全部重叠长度，完全照题意枚举，只适合小数据。
void dfs(int last, int cur_len) {
    if (cur_len > ans) {
        ans = cur_len;
    }

    for (int nxt = 1; nxt <= n; nxt++) {
        if (used[nxt] >= 2) {                 // 每个单词最多使用两次
            continue;
        }
        int sz = (int)overlap_list[last][nxt].size();
        for (int i = 0; i < sz; i++) {        // 每一种合法重叠长度都试一遍
            int overlap_len = overlap_list[last][nxt][i];
            used[nxt]++;
            dfs(nxt, cur_len + (int)word[nxt].size() - overlap_len);
            used[nxt]--;
        }
    }
}

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

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> word[i];
    }
    cin >> start_ch;

    build_overlap_list();

    // 从所有以 start_ch 开头的单词出发各搜一次，每个起点用掉该单词一次。
    for (int i = 1; i <= n; i++) {
        if (word[i][0] != start_ch) {
            continue;
        }
        memset(used, 0, sizeof(used));
        used[i] = 1;
        dfs(i, (int)word[i].size());
    }

    cout << ans << '\n';
    return 0;
}

brute.cpp 完全照题意枚举：重叠长度从 $1$ 到 $\min(|A|, |B|) - 1$ 全部检查、全部尝试，最忠实于题目定义，适合作为小数据对拍基准。它的瓶颈有两个：

每次转移都要重新比较字符串判断后缀与前缀是否重合；
同一对单词有多种重叠时，每一种都要开一个分支。

关键观察：固定一对单词 $A \to B$ 时，只需保留最小的合法正重叠长度。设两种合法重叠为 $x < y$ ：

本次新增长度分别是 $|B| - x$ 与 $|B| - y$ ，选 $x$ 更大；
接完以后，后续能接什么只取决于“最后一个单词是 $B$ ”和“各单词使用次数”，与刚才具体重叠了多少无关。

所以对每一对单词取最小正重叠，不会丢失任何更优接法。

最终做法：先预处理 best_overlap[i][j]（ $i$ 接 $j$ 的最小合法正重叠长度，无法相接记 $0$ ），再对每个以起始字母开头的单词作为龙的开头做 DFS：

状态：当前最后一个单词 last、当前龙长 cur_len、每个单词已使用次数 used[i]；
转移：枚举 used[nxt] < 2 且 best_overlap[last][nxt] != 0 的 nxt，新增长度 $|word_{nxt}| - best\_overlap[last][nxt]$ ；
回溯：进入下一层前 used[nxt]++，返回后 used[nxt]--。

代码

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
92
93/**
 * 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-08-13 13:32
 * update_at: 2026-08-13 13:32
 */
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 25;

int n;
string word[MAXN];                    // 单词，下标从 1 开始
int best_overlap[MAXN][MAXN];         // best_overlap[i][j]：i 接 j 的最小合法正重叠长度，0 表示不能接
int used[MAXN];                       // used[i]：单词 i 已经使用的次数（最多 2 次）
char start_ch;                        // 龙的开头字母
int ans;                              // 最长接龙长度

// 判断 s 的后 k 个字符是否等于 t 的前 k 个字符。
bool same_overlap(const string &s, const string &t, int k) {
    int len_s = (int)s.size();
    for (int i = 0; i < k; i++) {
        if (s[len_s - k + i] != t[i]) {
            return false;
        }
    }
    return true;
}

// 求单词 i 接单词 j 的最小合法正重叠长度。
// 重叠长度必须严格小于两个单词的长度，否则一个单词会被另一个完全包含。
int get_best_overlap(int i, int j) {
    int limit = min((int)word[i].size(), (int)word[j].size()) - 1;
    for (int k = 1; k <= limit; k++) {
        if (same_overlap(word[i], word[j], k)) {
            return k;
        }
    }
    return 0;
}

// dfs(last, cur_len)：当前龙以单词 last 结尾，总长度为 cur_len。
// 枚举下一个能接的单词 nxt，进入递归前 used[nxt]++，返回后 -- 完成回溯。
void dfs(int last, int cur_len) {
    if (cur_len > ans) {
        ans = cur_len;
    }

    for (int nxt = 1; nxt <= n; nxt++) {
        if (used[nxt] >= 2) {                 // 每个单词最多使用两次
            continue;
        }
        if (best_overlap[last][nxt] == 0) {   // 不能首尾相接
            continue;
        }

        used[nxt]++;
        dfs(nxt, cur_len + (int)word[nxt].size() - best_overlap[last][nxt]);
        used[nxt]--;
    }
}

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

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> word[i];
    }
    cin >> start_ch;

    // 预处理任意两个单词之间的最小合法正重叠长度。
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            best_overlap[i][j] = get_best_overlap(i, j);
        }
    }

    // 从所有以 start_ch 开头的单词出发各搜一次，每个起点用掉该单词一次。
    for (int i = 1; i <= n; i++) {
        if (word[i][0] != start_ch) {
            continue;
        }
        memset(used, 0, sizeof(used));
        used[i] = 1;
        dfs(i, (int)word[i].size());
    }

    cout << ans << '\n';
    return 0;
}

复杂度

预处理： $O(n^2 \cdot L^2)$ ，其中 $L$ 为单词最大长度（每对单词最坏比较 $O(L^2)$ 个字符）。
搜索：最坏指数级。深度不超过 $2n$ （每个单词最多用两次），每层至多 $n$ 个分支；本题被官方标注为“疑似错题”，数据以题面为准， $n \leqslant 20$ 的原始数据可通过。
空间： $O(n^2)$ （重叠表）加递归栈 $O(2n)$ 。

总结

本题的模型是“有向图上带次数限制的最长路径搜索”，核心是两个问题：

怎么判断能不能接：后缀等于前缀，且重叠长度严格小于两边单词长度，排除完全包含；
一对单词只需记一种重叠：最小正重叠让本次新增长度最大，且后续状态不受本次重叠影响。

预处理把“每步重复比较字符串”的成本一次性摊掉，剩下的就是带 used[] 回溯的 DFS。这种“每层选一个还没用满的元素”的枚举结构，与 rbook 的《全排列》文章是同一种 DFS 回溯模型。

图示解析

这张 ASCII 图展示本题从重叠判定到搜索求解的完整路线：

text

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19两个单词 A -> B 能否接
   判定：A 的后 k 个字符 == B 的前 k 个字符
   排除：k < min(|A|, |B|)（不能完全包含）
        |
        v
预处理 best_overlap[i][j]
   对每对单词取最小合法正重叠长度
   重叠越小，本次新增长度 |w_j| - overlap 越大
   接完后只与最后一个单词 j 和已用次数有关
        |
        v
DFS 搜索接龙（main.cpp）
   起点：所有以 start_ch 开头的单词
   状态：最后一个单词 last、当前长度 cur_len、每词已用次数 used[]
   转移：used[nxt] < 2 且 best_overlap[last][nxt] != 0 时接上 nxt
   回溯：used[nxt]++ 进入、-- 返回
        |
        v
答案：所有合法接龙长度的最大值

图中三条主线分别对应“如何判定一条边存在”“为什么一条边只需记一种重叠”“如何做带次数限制的搜索”。核心是：把每步重复的字符串比较一次性摊到预处理，把多重叠分支合并成唯一转移，之后的 DFS 只是一个枚举 + 回溯的过程。