首页 > 代码库 > codevs 1051 接龙游戏(栈模拟)
codevs 1051 接龙游戏(栈模拟)
传送门
Description
给出了N个单词,已经按长度排好了序。如果某单词i是某单词j的前缀,i->j算一次接龙(两个相同的单词不能算接龙)。
你的任务是:对于输入的单词,找出最长的龙。
Input
第一行为N(1<=N<=105)。以下N行每行一个单词(由小写组成),已经按长度排序。(每个单词长度<50)
Output
仅一个数,为最长的龙的长度。
Sample Input
5
i
a
int
able
inter
Sample Output
3
思路
某单词i是某单词j的前缀,因此可以按照字典序先排序(注:sort似乎不能对char类型的二维数组排序,有空要学学qsort的写法),然后从字典序最小的数开始枚举,看一下当前单词是否能成为下一个单词的前缀,可以则将下一个单词继续压入栈中,不行则将当前单词出栈,按照这种想法去模拟维护一个栈,更新最大值即可。
#include<iostream>#include<cstdio>#include<cstring>#include<stack>#include<string> #include<algorithm>using namespace std;const int maxn = 100005;string word[maxn];int main(){ int N; while (~scanf("%d",&N)) { stack<int>stk; int res = 1; for (int i = 0;i < N;i++) { cin >> word[i]; } sort(word,word+N); stk.push(0); for (int i = 1;i < N;i++) { bool flag = false; while (!stk.empty()) { int tmp = stk.top(); int len1 = word[tmp].size(); int len2 = word[i].size(); if (len2 > len1) { flag = true; for (int j = 0;j < len1;j++) { if (word[tmp][j] != word[i][j]) { flag = false; break; } } } if (flag) break; stk.pop(); } stk.push(i); int len3 = stk.size(); res = max(res,len3); } printf("%d\n",res); } return 0;}
codevs 1051 接龙游戏(栈模拟)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。