[NOIP2000 提高组] 单词接龙
题目背景
注意:本题为上古 NOIP 原题,不保证存在靠谱的做法能通过该数据范围下的所有数据。
题目描述
单词接龙是一个与我们经常玩的成语接龙相类似的游戏,现在我们已知一组单词,且给定一个开头的字母,要求出以这个字母开头的最长的“龙”(每个单词都最多在“龙”中出现两次),在两个单词相连时,其重合部分合为一部分,例如 beast
和 astonish
,如果接成一条龙则变为 beastonish
,另外相邻的两部分不能存在包含关系,例如 at
和 atide
间不能相连。
输入格式
输入的第一行为一个单独的整数 \(n\) 表示单词数,以下 \(n\) 行每行有一个单词,输入的最后一行为一个单个字符,表示“龙”开头的字母。你可以假定以此字母开头的“龙”一定存在。
输出格式
只需输出以此字母开头的最长的“龙”的长度。
样例 #1
样例输入 #1
5
at
touch
cheat
choose
tact
a
样例输出 #1
23
样例输入 #2
2
abababab
abababc
a
样例输出 #2
19
提示
样例解释:连成的“龙”为 atoucheatactactouchoose
。
\(n \le 20\)。
题解
思路:采用dfs搜索每一种情况,在搜索过程中保证加入到结果的字符串,满足题目的要求,不能出现包含的情况。结果要求指定字母开头最长的”龙“,所以我们合并两个字符串应尽量长一些。
坑点:
- 题目对”龙“的首字母有限制
- 结果要求最长的字符串,所以我们合并两个字符串时,一定要尽量少删除
- 两个字符串不能有包含关系
#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define ppb pop_back
#define SZ(v) ((int)v.size())
typedef long long ll;
typedef unsigned int u32;
typedef unsigned long long u64;
typedef double db;
using namespace std;
const int N = 1e6+10;
int _;
int n;
vector<string> a;
int ans;
int vis[N];
char c;
string b;
int calc(string a, string b) { // a和b最小重复值
// if(a == b) return -1;
int i, j;
int len1 = SZ(a), len2 = SZ(b);
int len = min(len1, len2);
for(i = 1; i <= len-1; i++) { // 重合字符串长度
for(j = 0; j < i; j++) { // 遍历两个字符串相应位置
if(a[len1-i+j] != b[j]) break;
}
if(j == i) return i;
}
return -1; // 若含有包含关系或者没有相连关系返回-1
}
void dfs(int step, string s) {
if(ans < SZ(s)) {
ans = SZ(s);
b = s;
}
for(int i = 0; i < n; i++) {
if(vis[i] <= 1) {
int k = calc(s, a[i]);
if(k != -1) {
vis[i] += 1;
dfs(step+1, s+a[i].substr(k));
vis[i] -= 1;
}
}
}
}
void solve() {
cin >> n;
for(int i = 0; i < n; i++) {
string s;
cin >> s;
a.pb(s);
}
cin >> c;
for(int i = 0; i < n; i++) {
if(a[i][0] == c) {
vis[i] += 1;
dfs(0, a[i]);
vis[i] -= 1;
}
}
cout << ans << "\n";
// cout << b << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
_ = 1;
// cin >> _;
while(_--) {
solve();
}
return 0;
}