像素

用户名：dotcpp0735122

访问量：808

签　名：

落山

等　　级
排　　名	6642
经　　验	1395
参赛次数	0
文章发表	15
年　　龄	0
在职情况	学生
学　　校
专　　业

　　自我简介：

TA的其他文章

寻找配对数量总和
浏览：3

你可能喜欢

好好学string及相关方法~

　　作者: 像素　　　　发表时间：2024-04-24 17:52:25 浏览：65　|　评论：0　

原题链接：蓝桥杯算法训练VIP-单词接龙

***阅读须知:s.substr(x)的意思是从字符串s的第x个开始截取到s的末尾,那substr(0,x)不必多说了吧...为方便大家更容易理解，我将解决字符串之间的拼接的部分单独放入一个check函数来解释。*
**

样例为at touch cheat choose tact
龙头为a

要进行拼接，我们可以从要拼接的那个字符串的第一个下标0开始加入到我们定义一个临时字符串中string t="";t+=s[i];然后与被拼接的字符串用被拼接字符串的大小减去1再减去s[i]当前的下标i，同时要保证被拼接的字符串必须大于拼接字符串，废话不多说直接看样例:

假设要拼接at与touch,看check函数s1此时为at,l长度为2,s2=touch
第一轮i=0 t="t";
正好s1.substr(l-i-1)也等于"t"同时l-i-1>=0也满足条件那就开始拼接

那么atouch与choose的情况呢？
第一轮i=0肯定不符合条件的(t="c"但是s1[l-i-1="h")

但第二轮i=1(t="ch"而且s1.substr(l-i-1)=="ch")符合条件进行拼接

最后at与atouch在i=2的情况时l-i-1会小于0，这会导致在截取字符串判断时会出现
下标小于0的情况！！！所以要多加一条判断是否越界的情况
```cpp
#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define int long long

const int N=20;
string s[N];
int n,used[N],maximum; //
char c;

void check(string s1,int l,string s2);
void dfs(string tp,int len);

signed main(){
	
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	cin>>n;
	
	for(int i=0;i<n;i++){
	    cin>>s[i];
	}
	
	cin>>c;
	for(int i=0;i<n;i++){
	    if(s[i][0]==c){ //龙头
	        used[i]+=1;
	        dfs(s[i],s[i].size()); //起始字符串及大小
	        used[i]-=1;
	    }
	}
	
    cout<<maximum<<endl;
	
	return 0;
}

void dfs(string tp,int len){
    if(maximum<len){
        maximum=len;
//        cout<<tp<<endl;
    }
    
    for(int i=0;i<n;i++){
        if(used[i]>=2){ //被使用2次的肯定不能再使用
            continue;
        }
        
        used[i]+=1;
        check(tp,len,s[i]); //未超过2次使用的字符串进入判断
        used[i]-=1; //现场恢复
    }
}

void check(string s1, int l, string s2) { //最终字符串 大小 拼接的字符串
    int i, j = 0;
    string t = "";
    for (i = 0; i < s2.size(); i++) { //枚举从s2 0到s2.size的拼接情况 
        t += s2[i];
        if (l - i - 1 >= 0 && s1.substr(l - i - 1) == t) { //l-i-1>=0的情况就是防止后序substr截取字符串出问题 
            string temp = s2.substr(t.size()); //取字符串
            dfs(s1 + temp, l + temp.size());
        }
    }

}

```

0.0分

1 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

像素

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题5.8 （C语言代码）

求最大公约数-模板题

点我有惊喜！你懂得！

C语言程序设计教程（第三版）课后习题1.6 （C语言代码）

C语言程序设计教程（第三版）课后习题7.4 （C语言代码）

好好学string及相关方法~

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题10.7 （C语言代码）

WU-蓝桥杯算法提高VIP-勾股数（C++代码）

WU-判定字符位置（C++代码）

三角形（C++代码）递归（存在大量重复计算，容易出现时间超限）

C语言程序设计教程（第三版）课后习题6.9 （C语言代码）

哥德巴赫曾猜测（C语言代码）

C语言程序设计教程（第三版）课后习题11.1 （C语言代码）

C语言程序设计教程（第三版）课后习题4.9 （C语言代码）

矩阵加法（C语言代码）

C语言程序设计教程（第三版）课后习题6.2 （C语言代码）

像素

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题5.8 （C语言代码）

求最大公约数-模板题

点我有惊喜！你懂得！

C语言程序设计教程（第三版）课后习题1.6 （C语言代码）

C语言程序设计教程（第三版）课后习题7.4 （C语言代码）

好好学string及相关方法~

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题10.7 （C语言代码）

WU-蓝桥杯算法提高VIP-勾股数 （C++代码）

WU-判定字符位置 （C++代码）

三角形 （C++代码）递归（存在大量重复计算，容易出现时间超限）

C语言程序设计教程（第三版）课后习题6.9 （C语言代码）

哥德巴赫曾猜测 （C语言代码）

C语言程序设计教程（第三版）课后习题11.1 （C语言代码）

C语言程序设计教程（第三版）课后习题4.9 （C语言代码）

矩阵加法 （C语言代码）

C语言程序设计教程（第三版）课后习题6.2 （C语言代码）

　　评论区

WU-蓝桥杯算法提高VIP-勾股数（C++代码）

WU-判定字符位置（C++代码）

三角形（C++代码）递归（存在大量重复计算，容易出现时间超限）

哥德巴赫曾猜测（C语言代码）

矩阵加法（C语言代码）