原题呈现

P1688 新单词接龙问题#

题目描述#

给定一个包含 $n$ 个单词的字典，定义字典序为单词在这本字典的顺序．从中选择若干个单词，按字典序进行单词接龙，使得接龙的长度最大．

新单词接龙的规则：

单词变换：单词 $w_i$ 添加一个字母，删除一个字母，或修改一个字母可以得到单词 $w_{i+1}$ ；
字典序接龙： $w_1,w_2,\cdots,w_n$ ，满足字典序．

输入格式#

第一行一个整数 $n$ （ $1 \le n \le 25,000$ ），表示字典中单词的总数．接下来 $n$ 行，按字典序输入 $n$ 个单词，每行一个字符串，表示单词，单词仅由小写字母组成，长度在 $1$ 至 $16$ 以内．

输出格式#

输出一行一个整数，表示能获得的单词接龙的最大长度．

输入输出样例 #1#

输入 #1#

1
9
2
cat
3
dig
4
dog
5
fig
6
fin
7
fine
8
fog
9
log
10
wine

输出 #1#

1
5

说明/提示#

样例解释#

长度为 $5$ 的单词接龙为： $\texttt{dig}\to \texttt{fig}\to \texttt{fin}\to \texttt{fine}\to\texttt{wine}$ ．

此题动态规划．类似最长上升子序列问题，定义 f[n] 表示以 $n$ 结尾的字符串最长的接龙长度．

观察到字符串的长度很小，远小于 $n$ ．因此，对于此题，我们在转移时不选择枚举之前的所有字符串，而是选择枚举所有能够通过一次修改转移到当前字符串的前置字符串．具体来说：

枚举每一个字符串 $i$ ，在枚举时，遍历所有可能的前置字符串（相对 $i$ 多一个字符、少一个字符、改一个字符），并在前面所有枚举过的给定字符串中查找，如果存在这样的前置字符串 $j$ ，则说明 $i$ 可以接在 $j$ 后面，可以转移：将 f[i] = f[j] + 1．

这样的算法枚举前置字符串的复杂度为 $O(53L)$ ，每一次比较是 $O(L)$ ，总复杂度是 $O(53L^2n^2)$ 的，．

考虑优化枚举前面的字符串，可以使用 unordered_map $um$ 存储前面所有遍历过的给定字符串对应的 f 值，直接在 $um$ 中查找，这样的时间复杂度是 $O(53L^2n)$ 的．

考虑使用哈希优化，这样判断两个字符串相等就可以在 $O(1)$ 的复杂度内完成，时间复杂度 $O(53Ln)$ ．

由于此题字符串比较多，推荐使用 unsigned long long 自然溢出来实现哈希，不易冲突的同时且能够做到时间常数较小．

1
#include <bits/stdc++.h>
2
using namespace std;
3
typedef unsigned long long ull;
4
const int N = 25005;
5
const int BASE = 129;
6
int m, f[N], ans;
7
string s[N];
8
unordered_map<ull, int> um;
9
ull h[N], p[N];
10

11
// l,r 1-based
12
ull H(int l, int r) {
13
    if (l > r)
14
        return 0;
15
    return h[r] - h[l - 1] * p[r - l + 1];
16
}
17

18
signed main() {
19
    cin >> m;
20
    p[0] = 1;
21
    for (int i = 1; i <= 20; i++) {
22
        p[i] = p[i - 1] * BASE;
23
    }
24
    for (int q = 1; q <= m; q++) {
25
        string s;
26
        cin >> s;
27

28
        int len = s.size();
29

30
        for (int i = 1; i <= len; i++) {
31
            h[i] = h[i - 1] * BASE + s[i - 1];
32
        }
33

34
        f[q] = 1;
35

36
        // 增加一个
37
        for (int i = 0; i <= len; i++) {
38
            for (char c = 'a'; c <= 'z'; c++) {
39
                ull hs =
40
                    H(1, i) * p[len - i + 1] + c * p[len - i] + H(i + 1, len);
41
                if (um.count(hs))
42
                    f[q] = max(f[q], f[um[hs]] + 1);
43
            }
44
        }
45
        // 删除一个
46
        for (int i = 1; i <= len; i++) {
47
            ull hs = H(1, i - 1) * p[len - i] + H(i + 1, len);
48
            if (um.count(hs))
49
                f[q] = max(f[q], f[um[hs]] + 1);
50
        }
51
        // 修改一个
52
        for (int i = 1; i <= len; i++) {
53
            for (char c = 'a'; c <= 'z'; c++) {
54
                ull hs = H(1, i - 1) * p[len - i + 1] + c * p[len - i] +
55
                         H(i + 1, len);
56
                if (um.count(hs))
57
                    f[q] = max(f[q], f[um[hs]] + 1);
58
            }
59
        }
60

61
        ans = max(ans, f[q]);
62

63
        um[H(1, len)] = q;
64
    }
65
    cout << ans;
66
    return 0;
67
}

音乐

音乐

P1688 新单词接龙问题#

题目描述#

输入格式#

输出格式#

输入输出样例 #1#

输入 #1#

输出 #1#

说明/提示#

样例解释#

文章分享

音乐

安吉D9-T3

P1688 新单词接龙问题#

题目描述#

输入格式#

输出格式#

输入输出样例 #1#

输入 #1#

输出 #1#

说明/提示#

样例解释#

文章分享