首页 > 代码库 > 单词接龙（codevs 1018）
单词接龙（codevs 1018）
2000年NOIP全国联赛普及组NOIP全国联赛提高组
时间限制: 1 s
空间限制: 128000 KB
题目等级 : 黄金 Gold
题解
题目描述 Description
单词接龙是一个与我们经常玩的成语接龙相类似的游戏，现在我们已知一组单词，且给定一个开头的字母，要求出以这个字母开头的最长的“龙”（每个单词都最多在“龙”中出现两次），在两个单词相连时，其重合部分合为一部分，例如beast和astonish，如果接成一条龙则变为beastonish，另外相邻的两部分不能存在包含关系，例如at和atide间不能相连。
输入描述 Input Description
输入的第一行为一个单独的整数n(n<=20)表示单词数，以下n行每行有一个单词，输入的最后一行为一个单个字符，表示“龙”开头的字母。你可以假定以此字母开头的“龙”一定存在.
输出描述 Output Description
只需输出以此字母开头的最长的“龙”的长度
样例输入 Sample Input
5
at
touch
cheat
choose
tact
a
样例输出 Sample Output
23
数据范围及提示 Data Size & Hint
（连成的“龙”为atoucheatactactouchoose）
/* 先预处理一下联合个单词首尾相连的重复字母数，然后搜索 */ #include<cstdio>#include<iostream>#include<cstring>#define N 22using namespace std;int head[N],len[N],vis[N],n,ans,cnt;string s[N];char a1;struct node{ int u,v,pre,t;};node e[N*N];void add(int x,int y,int z){ ++cnt; e[cnt].u=x; e[cnt].v=y; e[cnt].t=z; e[cnt].pre=head[x]; head[x]=cnt;}void dfs(int x,int t){ ans=max(ans,t); for(int i=head[x];i;i=e[i].pre) if(vis[e[i].v]<2) { vis[e[i].v]++; dfs(e[i].v,t+len[e[i].v]-e[i].t); vis[e[i].v]--; }}int main(){ scanf("%d",&n); for(int i=1;i<=n;i++) { string ss;cin>>ss; s[i]=" ";s[i]+=ss; len[i]=ss.size(); } cin>>a1; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) { for(int k=1;k<=min(len[i],len[j])-1;k++) { string s1="",s2=""; for(int l=len[i]-k+1;l<=len[i];l++) s1+=s[i][l]; for(int l=1;l<=k;l++) s2+=s[j][l]; if(s1==s2) { add(i,j,k);break; } } } for(int i=1;i<=n;i++) if(s[i][1]==a1) { memset(vis,0,sizeof(vis)); vis[i]++; dfs(i,len[i]); } printf("%d",ans); return 0;}
单词接龙（codevs 1018）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。