首页 > 其他分享 >[NOIP2000 提高组] 单词接龙

[NOIP2000 提高组] 单词接龙

时间:2023-06-07 14:23:33浏览次数:45  
标签:NOIP2000 string int 字母 单词 接龙 开头

题目背景

注意:本题为上古 NOIP 原题,不保证存在靠谱的做法能通过该数据范围下的所有数据。

题目描述

单词接龙是一个与我们经常玩的成语接龙相类似的游戏,现在我们已知一组单词,且给定一个开头的字母,要求出以这个字母开头的最长的“龙”(每个单词都最多在“龙”中出现两次),在两个单词相连时,其重合部分合为一部分,例如 beast 和 astonish,如果接成一条龙则变为 beastonish,另外相邻的两部分不能存在包含关系,例如 at 和 atide 间不能相连。

输入格式

输入的第一行为一个单独的整数 n 表示单词数,以下 n 行每行有一个单词,输入的最后一行为一个单个字符,表示“龙”开头的字母。你可以假定以此字母开头的“龙”一定存在。

输出格式

只需输出以此字母开头的最长的“龙”的长度。

输入输出样例

输入 #1
5
at
touch
cheat
choose
tact
a
输出 #1
23

说明/提示

样例解释:连成的“龙”为 atoucheatactactouchoose

≤20n≤20。2023-06-07

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int N=1e5+10;
 4 int n,res,vis[N];
 5 string s[30],st;
 6 int chong(string s1,string s2)
 7 {
 8     for(int i=s1.size()-1;i>=0;i--)
 9     {
10         if(s1[i]==s2[0])
11         {
12             int l=i;
13             for(int j=0;j<s2.size();j++) {if(s1[l]==s2[j]) l++;else break;}
14             if(l==s1.size()) return l-i;
15         }
16     }
17     return 0;
18 }
19 void dfs(int num,string now)
20 {
21     res=max(res,(int)now.size()-num);
22     for(int i=0;i<n;i++)
23     {
24         int p=0;
25         if(vis[i]>=2) continue;
26         p=chong(now,s[i]);
27         if(p==0) continue;
28         vis[i]++;
29         dfs(num+p,now+s[i]);
30         vis[i]--;
31     }
32 }
33 int main()
34 {
35     cin>>n;
36     for(int i=0;i<n;i++) cin>>s[i];
37     cin>>st;
38     dfs(0,st);
39     cout<<res;
40     return 0;
41 }

 

标签:NOIP2000,string,int,字母,单词,接龙,开头
From: https://www.cnblogs.com/o-Sakurajimamai-o/p/17463153.html

相关文章

  • 最后一个单词的长度
     给你一个字符串s,由若干单词组成,单词前后用一些空格字符隔开。返回字符串中最后一个单词的长度。单词是指仅由字母组成、不包含任何空格字符的最大子字符串。来源:力扣(LeetCode)链接:https://leetcode.cn/problems/length-of-last-word著作权归领扣网络所有。商业转载请联系......
  • 英语背单词 专四词汇 2023年06月 ChatGPT
    2023-06-022023-06-01Explainthemeaningofthefollowingwordsalongwithindexandphoneticsymbol:bugle,greed,stink,smear,coffin,peep,kidney,robin,needy,artistic,conceited,fleece,parenthood,improper,mowIndexWordPhoneticSymbolDefini......
  • 1万9千多单词大冲关含真人读音ACCESS数据库
    英语类的数据其实已经有很多很多人,但是不同的需求适合的也会是各种的不同,甚至可能需要将多个相关的数据整合起来应用,而今天这份数据库对于整合来说是非常方便的,因为它是以单词为关键词进行各种关联的,也就是说只要是英语类的数据都可以与这份数据关联起来。这个数据的好处在于有17......
  • 单词数
    #define_CRT_SECURE_NO_WARNINGS1#include<stdio.h>intmain(){ voidfound(float(*p)[3],intn); floatarr[3][3]; inti,j; printf("请输入三行五列的数组:\n"); for(i=0;i<3;i++) for(j=0;j<3;j++)  scanf("%f",&am......
  • 有意义的单词分割——经典dfs题目
     680.分割字符串中文English给一个字符串,你可以选择在一个字符或两个相邻字符之后拆分字符串,使字符串由仅一个字符或两个字符组成,输出所有可能的结果样例样例1输入:"123"输出:[["1","2","3"],["12","3"],["1","23"]]样例2输入:"12345"输出:[["1&q......
  • 139. 单词拆分
    给你一个字符串s和一个字符串列表wordDict作为字典。请你判断是否可以利用字典中出现的单词拼接出s。注意:不要求字典中出现的单词全部都使用,并且字典中的单词可以重复使用。输入:s="leetcode",wordDict=["leet","code"]输出:true解释:返回true因为"leetcod......
  • 剑指 Offer 58 - I. 翻转单词顺序
    题目描述:输入一个英文句子,翻转句子中单词的顺序,但单词内字符的顺序不变。为简单起见,标点符号和普通字母一样处理。例如输入字符串"Iamastudent.",则输出"student.aamI"。  方法:分割+倒序  classSolution{publicStringreverseWords(Strings){......
  • [NOIP2000 提高组] 单词接龙
    [NOIP2000提高组]单词接龙题目背景注意:本题为上古NOIP原题,不保证存在靠谱的做法能通过该数据范围下的所有数据。题目描述单词接龙是一个与我们经常玩的成语接龙相类似的游戏,现在我们已知一组单词,且给定一个开头的字母,要求出以这个字母开头的最长的“龙”(每个单词都最多在......
  • 【华为机试】单词倒叙
    题目描述:输入单行英文句子,里面包含英文字母,空格以及,.?三种标点符号,请将句子内每个单词进行倒序,并输出倒序后的语句输入描述:输入字符串S,S的长度1≤N≤100输出描述:输出逆序后的字符串。解题思路:遍历给定句子,判断如果字母,则插入到指定位置,如果是指定标点,则追......
  • P1859 单词接龙
    #include<iostream>#include<cstring>#include<cmath>usingnamespacestd;intn,length=0,vis[1000]={0};stringstr[1000];inlineintcheck(stringa,stringb){intp=min(a.length(),b.length());for(inti=1;a.length()==1?i<=p:i......