欢迎访问 如意编程网!

如意编程网

当前位置: 首页 > 编程资源 > 编程问答 >内容正文

编程问答

Luogu 1019 单词接龙

发布时间:2024/7/5 编程问答 4 豆豆
如意编程网 收集整理的这篇文章主要介绍了 Luogu 1019 单词接龙 小编觉得挺不错的,现在分享给大家,帮大家做个参考.

题目链接:https://www.luogu.org/problemnew/show/P1019

思路:

审题很重要。

题中有一些要注意的点:

1.每个单词都最多在“龙”中出现两次

2.两个单词合并取的是较小的重叠部分,特判也基于此

剩下就是稍微有些复杂的模拟了。

值得提的一点,本题中$check$函数可使用$substr$来优化代码量。

代码:

#include <cstdio> #include <cctype> #include <cstring> #include <iostream> #include <algorithm> #include <queue> #include <map> const int INF=1<<30; const int MAXN=25; using namespace std; int n,cnt,cntt,Min,ans=-INF,num[MAXN]; char b; bool flag; map<string,bool> mapp; string s[MAXN],ss; queue<string> q; bool check(string qq,int y){Min=INF,cnt=0;cntt=0;ss.clear();int len1=qq.length(),len2=s[y].length();for(int i=0;i<len1;i++){if(qq[i]!=s[y][0]) continue;for(int j=i,l=0;j<len1&&l<len1;j++,l++)if(qq[j]==s[y][l]) cnt++;if(cnt==len1-i&&cnt<Min){ss.clear();Min=cnt;for(int l=0;l<i;l++) ss+=qq[l];for(int l=0;l<len2;l++) ss+=s[y][l]; }cnt=0;}return Min<INF; } void dfs(string g,int x){ans=max(ans,(int)g.length());for(int i=0;i<n;i++){if(!check(g,i)) continue;if(mapp[ss]||num[i]>=2) continue;mapp[ss]=true;num[i]++;dfs(ss,i);num[i]--;} } void init(){memset(num,0,sizeof(num));mapp.clear(); } int main(){cin>>n;for(int i=0;i<n;i++)cin>>s[i];cin>>b;for(int i=0;i<n;i++){if(s[i][0]==b){mapp[s[i]]=true;num[i]++;dfs(s[i],i);init();}}cout<<ans<<endl;return 0; }

 

转载于:https://www.cnblogs.com/BeyondLimits/p/11148716.html

创作挑战赛新人创作奖励来咯,坚持创作打卡瓜分现金大奖

总结

以上是如意编程网为你收集整理的Luogu 1019 单词接龙的全部内容,希望文章能够帮你解决所遇到的问题。

如果觉得如意编程网网站内容还不错,欢迎将如意编程网推荐给好友。