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

# **P1019 [NOIP 2000 提高组] 单词接龙 题解**

## **解题思路：**
主要是运用**搜索**的算法。

先在**主函数**枚举以 $char$ 字母开头的单词，然后再递归枚举之后可以继续**合法**拼接的单词，如果没有了，就回溯。

### **是否合法的判断方式：**
1、不能完全包含，如：at 和 atide 间不能相连。

2、末尾需要有**部分包含**。

### **注意！**

如果拼接该单词，包含的部分只在长度 $len$ 中计算一次！

还有！每个单词最多只可以拼接两次！

# **带注释的AC代码：**
（方便理解具体操作QWQ）
```cpp
#include <bits/stdc++.h>
using namespace std;
int n, maxx = 0;//n和len的最大值
string w[21];//n个单词
int u[21];//记录每个单词的使用次数
int ov(string &a, string &b){
    int l = min(a.size(), b.size());//记录字符串和枚举到的单词更短的那个的长度
    for(int i = 1; i < l; i++){//外层循环：尝试不同重叠长度
        bool f = true;
        for(int k = 0; k < i; k++){//内层循环：字符逐个比较
            if(a[a.size() - i + k] != b[k]) {
                f = false;
                break;
            }
        }
        if(f) return i;//可以拼接
	}
    return 0;//不可以拼接
}
void dfs(string s, int l){
    maxx = max(maxx, l);//更新最大值
    for(int i = 0; i < n; i++){//枚举接下来可以使用的单词
        if(u[i] < 2){//使用次数小于2
            int o = ov(s, w[i]);//o是求出重叠的部分长度是多少
            if(o > 0 && o < w[i].size()){//如果重叠的部分长度大于0，并且重叠小于以当前单词开头的字符串的长度，并并且重叠部分要小于当前的这个单词的长度
                u[i]++;//使用一次
                dfs(w[i], l + w[i].size() - o);//继续递归查看下一个单词
                u[i]--;//减去之前使用一次的操作
            }
        }
    }
}
int main(){//主函数
    cin >> n;
    for(int i = 0; i < n; i++) cin >> w[i];//输入n个单词
    char c;//字符串开头的 char 
    cin >> c;
    for(int i = 0; i < n; i++){//枚举n个单词
        if(w[i][0] == c){//如果这个单词的首字母是 char
            u[i]++;//这个单词因为作为了开头多加一次使用次数
            dfs(w[i], w[i].size());//开始递归，以这个单词为开头
            u[i]--;//递归结束后，这个单词减去开头的一次使用次数
        }
    }
    cout << maxx;//输出最大的长度
    return 0;
}
```

# **干净清爽的AC代码**
```cpp
#include <bits/stdc++.h>
using namespace std;
int n, maxx = 0;
string w[25];
int u[25];
int ov(string &a, string &b){
    int l = min(a.size(), b.size());
    for(int i = 1; i < l; i++){
        bool f = true;
        for(int k = 0; k < i; k++){
            if(a[a.size() - i + k] != b[k]) {
                f = false;
                break;
            }
        }
        if(f) return i;
	}
    return 0;
}
void dfs(string s, int l){
    maxx = max(maxx, l);
    for(int i = 0; i < n; i++){
        if(u[i] < 2){
            int o = ov(s, w[i]);
            if(o > 0 && o < w[i].size()){
                u[i]++;
                dfs(w[i], l + w[i].size() - o);
                u[i]--;
            }
        }
    }
}
int main(){
    cin >> n;
    for(int i = 0; i < n; i++) cin >> w[i];
    char c;
	cin >> c;
    for(int i = 0; i < n; i++){
        if(w[i][0] == c){
            u[i]++;
            dfs(w[i], w[i].size());
            u[i]--;
        }
    }
    cout << maxx;
    return 0;
}
```

这是本蒟蒻在洛谷上发的第一篇题解QWQ，求通过！！！

正在渲染内容...