P1019 [NOIP 2000 提高组] 单词接龙
https://www.luogu.com.cn/problem/P1019
来发题解的
首先看题目会觉得很简单，但是要怎么用代码实现呢。
字符串这个东西本质其实和数组差不多，只要我们掌握一些语法和函数
substr(x,y)
这是一个可以取出字符串任意一个部分的函数
第一个参数 x -- 代表要截字符串的起始位置
第二个参数 y -- 代表要截字符串的长度
比如 t = 'string' , t.substr(0,2) 就是 st
还有一个用法，比如 substr(4) 就是 ng //从位置4开始到结尾的子字符串
//字符串默认是从0开始索引的
有了这个函数，这个题目就会简单很多，接下来我们继续思考
1.怎么找到对应相等的部分，并接起来
2.怎么递归，要传递什么参数下去，即怎么去dfs。
----首先我们要先找到龙头，即第一个字母的对应，这样才会进行dfs
这很简单，我们只需一个for循环的判断即可。
然后进行匹配，当找到两个字符串相对应的两个部分，就把加起来，再进行dfs
#include<bits/stdc++.h> using namespace std; #define int long long #define endl '\n' const int N = 39; int n,ans = 0; char c; string ss[N]; int v[N] = {0}; void dfs(string s){ int ank = s.size(); ans = max(ans,ank); for(int i = 1 ; i <= n ; i++){ if(v[i] == 2) continue; //每个字符串最多只能被用一次 for(int j = 1 ; j <= min(s.size(),ss[i].size()) ; j++){ if(s.substr(s.size() - j) == ss[i].substr(0,j)){ v[i] ++; dfs(s + ss[i].substr(j));//把后面不相等的部分给接上 v[i] --; } } } } void solve(){ cin>>n; for(int i = 1 ; i <= n ; i++) cin>>ss[i]; cin>>c; for(int i = 1 ; i<= n ; i++){ if(ss[i][0] == c){ v[i] ++; dfs(ss[i]); v[i]--; // 回溯 } } cout<<ans; } signed main() { ios::sync_with_stdio(0); cin.tie(0); int t = 1; //cin >> t; while (t--) { solve(); } return 0; }
