首页 > 代码库 > 1051 接龙游戏
1051 接龙游戏
1051 接龙游戏
时间限制: 1 s
空间限制: 128000 KB
题目等级 : 钻石 Diamond
题目描述 Description
给出了N个单词,已经按长度排好了序。如果某单词i是某单词j的前缀,i->j算一次接龙(两个相同的单词不能算接龙)。
你的任务是:对于输入的单词,找出最长的龙。
输入描述 Input Description
第一行为N(1<=N<=105)。以下N行每行一个单词(由小写组成),已经按长度排序。(每个单词长度<50)
输出描述 Output Description
仅一个数,为最长的龙的长度。
样例输入 Sample Input
5
i
a
int
able
inter
样例输出 Sample Output
3
数据范围及提示 Data Size & Hint
1<=N<=105
1 #include<iostream> 2 #include<cstdio> 3 #include<stack> 4 #include<cstring> 5 #include<algorithm> 6 using namespace std; 7 string a[1000001]; 8 int tot=1; 9 stack<int>s;10 int main()11 {12 int n;13 scanf("%d",&n);14 for(int i=1;i<=n;i++)15 {16 //scanf("%s",a[i]);17 cin>>a[i];18 }19 sort(a+1,a+n+1);20 s.push(1);21 for(int i=2;i<=n;i++)22 {23 while(!s.empty())24 {25 int t=s.top();26 int flag=0;27 if(a[t].size()<a[i].size())28 {29 if(a[i].find(a[t])==0)30 {31 break;32 }33 else34 {35 flag=1;36 }37 }38 else flag=1;39 if(flag==0)40 break;41 if(flag==1)42 {43 s.pop();44 }45 }46 s.push(i);47 if(s.size()>tot)48 tot=s.size();49 }50 cout<<tot;51 return 0;52 }
1051 接龙游戏
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。