洛谷题解——P1019：单词接龙

在给点单词中，找出最长的龙。注意每个单词在龙中最多出现两次。

比如样例数据中的 tact 这个单词，正好是首字母和尾字母都为 t，按照接龙规则，是可以自己接自己的。 

样例数据分析

我们根据样例数据，可以绘制出下图所示的关系：

如上图所示，要找出最长的单词，自然是一个 DFS 过程，也就是从 at 出发写出所有的 DFS 可能，找到最长的那个即可。能找到的满足要求的 DFS 遍历可能有以下几种：

atoucheatoucheatactact 22

atoucheatouchoose 17

atoucheatactoucheatact 22

atoucheatactouchoose 20

atoucheatactactoucheat 22

atoucheatactactouchoose 23

atouchoose 10

atactoucheatoucheatact 22

atactoucheatouchoose 20

atactoucheatactoucheat 22

atactoucheatactouchoose 23

atactouchoose 13

atactactoucheatoucheat 22

atactactoucheatouchoose 23

atactactouchoose 16

可以看出上面最长的长度为 23。

算法思路

1、读取数据。

2、找龙头。

3、构造变化关系数据。

4、遍历所有龙头，用当前龙头进行 DFS，得到所有 DFS 可能，找出最长的数据。

如何判断单词可以接龙？

注意，需要找最小的重合长度。比如一个单词为 abababab 和另外一个单词 abababab 进行接龙，重合字符应该是 2 个，即 ab，接龙后的词为 ababababababab。

每次暴力比较

由于本题数据量小，n ≤ 20，所以使用暴力比较是可以的。也就是每次比较字符串 a 和字符串 b 的第 k 个位置能否接龙，即实现一个如下的函数：

bool check(const string &a, const string &b, int k)

生成关系表

维护一个关系表。如同上面的图片，我们在读入用户数据后，生成一个关系表。这个表示描述字符串 a 后面接上字符串 b 将重合几个字符，可以考虑使用二维数组来描述。参考有向图，比如样例输入，我们可以得到如下表所示的关系，考虑初始化问题，0 表示两个单词不能接龙，x>0 表示可以第 i 个单词尾部接上第 j 个单词将重复 x 个字符。

上表什么意思呢？a[i][j] 表示第 i 个字符串后面接第 j 个字符串将重合几个字符。比如 a[1][2]=2，表示字符串 touch 后面如果要接上字符串 cheat，将重复 2 个字符，那么接龙后的单词为 toucheat，长度为 5(touch长度) + 5(cheat长度) - 2(重合长度) = 8。

代码实现思路

1、获取第 i 个单词和第 j 个单词长度的最小值，用 tt 表示。

2、如果 i==j，说明是同一个单词，则 tt 减一。因为自己不能

3、开一个循环，k 从 1 开始到 tt 结束。第 i 个单词从后向前取 k 个字符，第 j 个单词从前向后取 k 个字符，如果这 k 个字符相同，说明第 i 个单词后接上第 j 个单词构成的龙，将有 k 个字符是重复的。

4、循环结束后，判断一下包含关系。如果计算出重复的字符和 tt 大小相同，说明包含关系。

代码实现如下：

    //找龙头和构建重复字符表vector<int> head;for (int i=0; i<n; i++) {if (ch==word[i].at(0)) {head.push_back(i);}//第i个单词后面接上第j个单词，将重复 k 个字符for (int j=0; j<n; j++) {int tt = min(word[i].length(), word[j].length());string tmp1, tmp2;for (int k=1; k<=tt; k++) {//word[i]逆序获取tmp1 = word[i].substr(word[i].length()-k, k);//word[j]正序获取tmp2 = word[j].substr(0, k);if (tmp1==tmp2) {relation[i][j]=k;break;}}//包含关系if (relation[i][j]==tt) {relation[i][j]=0;}}}

AC 参考代码

#include <iostream>
#include <string>
#include <vector>using namespace std;const int MAXN = 20+2;
const int MAXUSED = 2;
string word[MAXN];//单词
int used[MAXN];//单词已经使用次数
int relation[MAXN][MAXN];
int sum;//当前龙单词长度
int ans;//最长的长度
int n;//
string dragon; //用第 i 个单词开始接龙
void dfs(int i) {//标志位，如果发生遍历说明数据构造没有结束bool flag = true;//遍历for (int j=0; j<n; j++) {//第 j 个单词没有超过使用限制//并且第 j 个单词可以接着第 i 个单词后面if (used[j]<MAXUSED && relation[i][j]>0) {used[j]++;sum += (word[j].length()-relation[i][j]);dragon += word[j].substr(relation[i][j], word[j].length()-relation[i][j]);dfs(j);sum -= (word[j].length()-relation[i][j]);used[j]--;dragon = dragon.substr(0, dragon.length()-(word[j].length()-relation[i][j]));flag = false;}}if (true == flag) {//cout << dragon << " " << sum << endl;ans = max(ans, sum);}
}int main() {cin >> n;for (int i=0; i<n; i++) {cin>>word[i];}char ch;cin >> ch;//找龙头和构建重复字符表vector<int> head;for (int i=0; i<n; i++) {if (ch==word[i].at(0)) {head.push_back(i);}//第i个单词后面接上第j个单词，将重复 k 个字符for (int j=0; j<n; j++) {int tt = min(word[i].length(), word[j].length());string tmp1, tmp2;for (int k=1; k<=tt; k++) {//word[i]逆序获取tmp1 = word[i].substr(word[i].length()-k, k);//word[j]正序获取tmp2 = word[j].substr(0, k);if (tmp1==tmp2) {relation[i][j]=k;break;}}//包含关系if (relation[i][j]==tt) {relation[i][j]=0;}}}int index;vector<int>::iterator it;for (it=head.begin(); it<head.end(); it++) {index = *it;used[index]++;sum += word[index].length();dragon = word[index];dfs(index);sum -= word[index].length();used[index]--;}cout << ans << endl;return 0;
}

P.S.

写题解报告太tmd累了，这个报告前前后后写了 4+ 小时，不停的修改算法思路部分。题解报道中题解，也就是题目分析是最重要的，代码反而可以不看。