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

题意

给出 n 个单词和一个起始字母。

要求拼出一条最长的“单词龙”，规则是：

第一个单词必须以给定字母开头
相邻两个单词要有一段前后缀重合
重合部分会合并成一份
但不能整段包含，也就是重合长度不能等于其中任意一个单词的长度
每个单词最多使用 2 次

输出最终这条龙的最大长度。

思路

先看一个最直接的小数据暴力：

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#include <bits/stdc++.h>
using namespace std;

const int MAXN = 25;

int n;
string word[MAXN];
int len_word[MAXN];
vector<int> overlap_list[MAXN][MAXN];  // 记录所有合法重叠长度
int used[MAXN];
char start_ch;
int ans = 0;

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;
}

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(len_word[i], len_word[j]) - 1;
            for (int k = 1; k <= limit; k++) {
                if (same_overlap(word[i], word[j], k)) {
                    overlap_list[i][j].push_back(k);
                }
            }
        }
    }
}

// 暴力：每次不仅枚举下一个单词，还枚举本次采用哪一种合法重叠长度。
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 + len_word[nxt] - 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];
        len_word[i] = (int)word[i].size();
    }
    cin >> start_ch;

    build_overlap_list();

    for (int i = 1; i <= n; i++) {
        if (word[i][0] != start_ch) {
            continue;
        }
        memset(used, 0, sizeof(used));
        used[i] = 1;
        dfs(i, len_word[i]);
    }

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

brute.cpp 会枚举：

下一个接哪个单词
这一对单词到底采用哪一种合法重叠长度

这和题目定义完全一致，很适合拿来对拍。

第一步：把题目看成 DFS 搜索

如果当前龙的最后一个单词是 A，那么下一步只需要考虑：

选哪个还没用满 2 次的单词 B
A 和 B 能不能首尾重合

因此可以直接做 DFS：

状态：当前最后一个单词是谁、每个单词已经用了几次
转移：接上一个还能用、且有合法重叠的单词

第二步：为什么一对单词只保留一种重叠就够了

设当前最后一个单词是 A，下一步接 B。

如果 A 和 B 有多种合法重叠长度，比如：

重叠 1 个字符
重叠 2 个字符

那么为了让总长度尽量大，显然应该选 更小的正重叠。

原因是：

本次增加的长度是 len(B) - overlap
重叠越小，本次增加的长度越大

更重要的是，接完以后，后续搜索只和：

最后一个单词变成了 B
各单词使用次数

有关，而和“刚才 A 到 B 重叠了几位”无关。

所以对于每一对单词 (A, B)：

只保留最小的合法正重叠长度

就一定不会比别的重叠方案更差。

第三步：预处理后再 DFS

于是先预处理：

best_overlap[i][j] 表示第 i 个单词接第 j 个单词时，最优的重叠长度

如果两者不能连接，就记为 0。

之后 DFS 时就不用再反复比较字符串了，只要：

枚举下一个单词 j
判断 best_overlap[last][j] 是否非 0
判断 j 是否已经用了两次
递归搜索

Python 知识

left.endswith(right[:length]) 直接表达后缀与前缀是否重合。
next((length for ... if ...),0) 找到第一个，也就是最小合法正重叠；不存在时返回 0。
二维列表推导式一次预处理所有单词对的重叠长度。
used[nxt] += 1、递归、-=1 是计数型回溯的状态恢复模式。
/home/rainboy/mycode/hugo-blog/content/program_language/python/generator_expression.md：用 next 取得第一个满足条件的候选。
/home/rainboy/mycode/hugo-blog/content/program_language/python/brute_force_validation.md：DFS 选择与撤销。

代码

python

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
39n = int(input())
words = [input().strip() for _ in range(n)]
start = input().strip()
used = [0] * n


def overlap(left, right):
    return next(
        (
            length
            for length in range(1, min(len(left), len(right)))
            if left.endswith(right[:length])
        ),
        0,
    )


overlaps = [[overlap(left, right) for right in words] for left in words]


def dfs(last, length):
    best = length
    for nxt, shared in enumerate(overlaps[last]):
        if not shared or used[nxt] == 2:
            continue
        used[nxt] += 1
        best = max(best, dfs(nxt, length + len(words[nxt]) - shared))
        used[nxt] -= 1
    return best


answer = 0
for index, word in enumerate(words):
    if word.startswith(start):
        used[index] = 1
        answer = max(answer, dfs(index, len(word)))
        used[index] = 0

print(answer)

复杂度

预处理重叠长度的时间复杂度是 $O(n^2 * L^2)$ ，其中 L 是单词最大长度
DFS 部分最坏情况下是指数级搜索
递归深度最多是 2n，因为每个单词最多使用两次

这题本质上还是搜索题，正式做法的优化重点不是把指数级变成多项式，而是减少每次转移里的重复字符串比较。

总结

这题最关键的两个判断是：

状态其实只需要关心“最后一个单词是谁”和“每个单词用了几次”
对固定的一对单词，应该选最小的合法正重叠长度

这样题目就能整理成一个比较清楚的 DFS 搜索模型。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。