洛谷 1019.单词接龙

2024-03-10 04:20
文章标签 单词 洛谷 接龙 1019

本文主要是介绍洛谷 1019.单词接龙,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

这道题用的搜索,也就是DFS,但是有一点难度,虽然说是对于搜索的知识点的考察,但是对于编程者的编程模拟能力和分析能力会有比较大的要求。

思路:首先我们审题,会注意到以下几点:

1.单词后面相同的部分和另一个单词前面相同的部分可以接在一块,并不是直接接上,而是重合的地方合并了;

2.每个单词还不止用一次,每个单词至多用2次。

那么,我们纯靠DFS肯定不会有什么效果的。DFS要搜索的话也是有目的的搜索的,但是上面的问题有很多,我们需要逐个处理完才能够比较明确的枚举。

我们想,如果说每个单词需要不多于2次使用,我们是不是需要记录每个单词使用的次数呢?这是一点,可以定义used数组进行记录每一个单词的使用次数,这里输入字符我们就用string,因为这样会很方便的知道多个字符串的序号是什么。

既然说是相同的部分不能重复接上,那么我们会想到一个string函数中的功能:substr,这个东西能够定义从某一个字符的位置开始,从后面连上它本身能够连接多少字符,这是个很方便的运用。我们就运用这个进行接上单词。

但是还有一个问题:我们需要怎么判断每个单词到底能不能连接呢?

这样就需要有一定的刷题经验了,我们可以用一个数组cnt[][]的二维数组表示第i个单词后面与第j个单词卡面重合的个数是多少,这样既能够记录这两个单词到底能不能接上,而且还能知道个数有多少个!这样就很方便了。

解决完上面这几个问题,还有一点需要知道:怎么接上单词才能达到最长呢?我们在接上单词的过程中,明显一个特点就是重合的字符少了,自然接上的单词长度就长了,这就是结论,当我们遍历的时候,一旦找到可以重合的单词就直接认定这就是最长的,也就是所谓的重合的越少越好。

预处理结束了,我们需要开始dfs搜索了,在我们搜索的时候需要遍历全部的单词,知道哪个单词的首位与所给出的字母相同,在这个单词的基础上进行搜索,dfs函数定义两个变量,一个就是单词接龙的第一个字符串,第二个变量就是对应的这个字符串在刚刚定义的编号是多少。

写DFS时,第一件事就是把这个将要接上单词的单词的使用个数+1,然后再去遍历其他单词,判断条件就是能否接上,这个能接上的单词使用次数超过2了没有,然后接上继续搜索。

上代码:

#include<iostream>
#include<stdio.h>
#include<cstring>
#include<cstdlib>
#include<cmath> 
#include<vector>
#include<algorithm>
#include<stack>
#include<queue>
#include<sstream>
#include<map>
#include<limits.h>
#include<set>
#define MAX 30
#define _for(i,a,b) for(int i=a;i<(b);i++)
#define ALL(x) x.begin(),x.end()
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;LL n, m, counts, num;
string s[MAX];
int cnt[MAX][MAX];
int used[MAX];
void dfs(string haha, int u) {used[u] ++;counts = max(counts, (LL)haha.size());for (int i = 0; i < n; i++) {if (cnt[u][i] && used[i] < 2) {dfs(haha + s[i].substr(cnt[u][i]), i);}}used[u]--;
}
int main() {ios::sync_with_stdio(false);cin.tie(NULL); cout.tie(NULL);cin >> n;for (int i = 0; i < n; i++) {cin >> s[i];}char word;cin >> word;//下面的操作都是对于各个单词的预处理,也就是对于单词能不能接上的判断,能接上的话重合个数是多少进行处理操作。for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {string a = s[i];string b = s[j];for (int k = 1; k < min(a.size(), b.size()); k++) {if (a.substr(a.size() - k, k) == b.substr(0, k)) {cnt[i][j] = k;break;//重合的越少越好,这样才能保证接龙的数列是最长的长度.}}}}for (int i = 0; i < n; i++) {if (s[i][0] == word) {dfs(s[i], i);}}cout << counts << endl;return 0;
}

这篇关于洛谷 1019.单词接龙的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/793029

相关文章

每日一练7:简写单词(含链接)

1.链接 简写单词_牛客题霸_牛客网 2.题目 3.代码1(错误经验) #include <iostream>#include <string>using namespace std;int main() {string s;string ret;int count = 0;while(cin >> s)for(auto a : s){if(count == 0){if( a <=

高精度计算(代码加解析,洛谷p1601,p1303)除法待更新

目录 高精度加法 高精度减法 高精度乘法 高精度加法 我们知道在c++语言中任何数据类型都有一定的表示范围。当两个被加数很大时,正常加法不能得到精确解。在小学,我们做加法都采用竖式方法。那么我们也只需要按照加法进位的方式就能得到最终解。 8 5 6+ 2 5 5-------1 1 1 1 加法进位: c[i] = a[i] + b[i];if(c[i] >=

洛谷 凸多边形划分

T282062 凸多边形的划分 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 先整一个半成品,高精度过两天复习一下补上 #include <iostream>#include <algorithm>#include <set>#include <cstring>#include <string>#include <vector>#include <map>

能量项链,洛谷

解释:  环形dp问题还是考虑将环拉直,可以参考我上一篇文章:环形石子合并 [2 3 5 10 2] 3 5 10 将环拉直,[]内是一个有效的区间,可以模拟吸收珠子的过程,         如[2 3 5] <=>(2,3)(3,5)    2是头,3是中间,5是尾 len >= 3:因为最后[2 10 2]是最小的可以合并的有效区间 len <= n + 1因为[2 3

动态规划---单词拆分

题目: 给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。 注意:不要求字典中出现的单词全部都使用,并且字典中的单词可以重复使用。 思路:本题属于完全背包问题,字符串s的长度为背包容量,字符串列表wordDict中的每一个元素相当于物品。 动态规划五部曲: 1.确定dp数组及含义 dp数组为元素类型是布

WPS如何查看已添加到词典的单词

WPS Office(12.1.0.17827) ① 点击文件,在文件中找到选项 ② 找到拼写检查并点击自定义词典 ③ 如果要删除已添加到词典的"错词",则点击修改 ④ 选择"错词", 点击删除

【C】单词长度

课程:程序设计入门——C语言(翁恺) 题目内容: 你的程序要读入一行文本,其中以空格分隔为若干个单词,以‘.’结束。你要输出这行文本中每个单词的长度。这里的单词与语言无关,可以包括各种符号,比如“it's”算一个单词,长度为4。注意,行中可能出现连续的空格。 输入格式: 输入在一行中给出一行文本,以‘.’结束,结尾的句号不能计算在最后一个单词的长度内。 输出格式: 在一行中输出这行

代码随想录第八天|151.翻转字符串里的单词 卡码网:55.右旋转字符串 28. 实现 strStr() 459.重复的子字符串

反转字符串的单词 思路:刷过稍微忘记 class Solution {public://去除空格string remove(string s){//使用快慢指针int slow=0;int i=0;for(;i<s.size();i++){if(s[i]!=' '){if(slow!=0){s[slow++]=' ';}while(s[i]!=' '&&i<s.size()){s[slow+

洛谷P5490扫描线

0是最小的数字,将一个线段看成一个区间,对于一个矩形,从下扫到上,入边为1,而出边为-1,意思是将这个区间上的所有点加1(区间修改).把线段表示为Line[i],其中记录了l,r,h,tag,左右端点,高度,入边还是出边(1或-1) 那么每次区间修改后不为0的区间它的值可能是1,2,3或者是其它数字,这不好统计,可以将它转化一下,0是不是表示没有被覆盖过的地方,我们只要统计0的个数然后用总长减去

实操在聆思CSK6大模型开发板的英文评测SDK中自定义添加单词、短语、句子资源

引言 英文评测示例通过对用户语音输入的英文单词进行精准识别,提供 单词、短语、句子 三种类型,用户在选择好类型后,可根据屏幕上的提示进行语音输入,评测算法将对输入的英文语音进行精准识别,并对单词的发音、错读、漏读、多读等方面进行评估。 本文将详细介绍在聆思CSK6大模型语音视觉开发板上,如何替换英文评测示例中的单词、短语和句子,从而让您有更好的AI应用体验。 ·· 获取英文评测SDK 部