首页 > 代码库 > codevs 1051 接龙游戏
codevs 1051 接龙游戏
给出了N个单词,已经按长度排好了序。如果某单词i是某单词j的前缀,i->j算一次接龙(两个相同的单词不能算接龙)。
你的任务是:对于输入的单词,找出最长的龙。
第一行为N(1<=N<=105)。以下N行每行一个单词(由小写组成),已经按长度排序。(每个单词长度<50)
仅一个数,为最长的龙的长度。
5
i
a
int
able
inter
3
1<=N<=105
方法一:模拟栈
先将输入数据按字典序排序,然后依次枚举,栈顶是当前字符串的前缀,就入栈,否则,栈顶出栈直至当前字符串可以入栈。在此期间,随时更新接龙最大值
以样例为例:设栈为stack[],答案为ans
排序后为:a able i int inter
1、栈为空,a入栈 stack:a ans=1
2、a是able的前缀,able入栈 stack:a able ans=2
3、able不是i的前缀, able出栈 stack:a ans=2
4、a不是i的前缀,a出栈 stack: ans=2
5、栈为空,i入栈 stack:i ans=2
6、i是int的前缀,int入栈 stack:i int ans=2
7、int是inter的前缀,inter入栈 stack:i int inter ans=3
结束
截取前缀时,可以使用assign函数,头文件:cstring
格式:p.assign(s,start,len) 在s中从位置start开始,截取长尾len的字符串复制给p
附:string常用函数:http://www.cnblogs.com/wangkangluo1/archive/2011/07/22/2114118.html
#include<cstdio> #include<cstring> #include<algorithm> #include<iostream> using namespace std; string s[100001],stack[100001]; int n,top,ans; bool cmp(string a,string b) { return a<b;//按字典序排序,string可以直接调用<,>,=,与int,double一样 } int main() { cin>>n; for(int i=1;i<=n;i++) cin>>s[i];//s存原数据 sort(s+1,s+n+1,cmp);//按字典序排序 stack[top++]+=s[1];//第一个先入栈 ans++;//至少有一个 for(int k=2;k<=n;k++)//所有的top均为开区间 { int l=stack[top-1].size();//当前栈顶元素的长度,即s[k]要想入栈,要判断前缀的长度 string p; p.assign(s[k],0,l);//在s[k]中从第0位开始,截取长度为l的字符串,赋值给p if(p==stack[top-1])//因为top为开区间,所以比较的是top-1 { if(s[k].size()==stack[top-1].size()) continue;//前缀相等,总单词长度也相等,那么这两个单词相等,题目说了不能算 stack[top++]=s[k];//可以入栈 } else { while(top&&stack[top-1]!=p.assign(s[k],0,l))//一直退到能入栈或栈为空 { top--; if(top)//栈为空时,top=0,不加这句会RE l=stack[top-1].size();//l转变为下一个要比较的单词的长度 } stack[top++]=s[k];//入栈 } ans=max(ans,top);//更新答案 } cout<<ans; }
方法二:http://www.cnblogs.com/IUUUUUUUskyyy/p/6193997.html
两个错误:1.退栈时,在比较的是当前栈顶元素,所以l、p需要更新。开始做的时候没有更新,一直用最初的栈顶元素比
2、ans初值为0,for循环从2开始,所以如果只有1个元素,输出0,但应该输出1
codevs 1051 接龙游戏