Codevs 1051 接龙游戏

接龙游戏"/>

Codevs 1051 接龙游戏

1051 接龙游戏

题目描述  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

/*不知道我的hash哪里出了错，才得了这么点分
*/
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#define mod 137593233
using namespace std;
int n;
char s[100010][60];
int h[100010][60],lth[100010];
int dp[100010],ans;
void Hash(int k){int len=strlen(s[k]+1);lth[k]=len;for(int i=1;i<=len;i++){h[k][i]=(h[k][i-1]+s[k][i]-'a')%mod;}
}
int main(){freopen("Cola.txt","r",stdin);scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%s",s[i]+1);Hash(i);}for(int i=1;i<=n;i++)dp[i]=1;for(int i=2;i<=n;i++){for(int j=1;j<i;j++){int len=lth[j];if(h[j][len]==h[i][len])dp[i]=max(dp[i],dp[j]+1);}ans=max(ans,dp[i]);}printf("%d",ans);
}

20分

/*
先排序，将所有单词按字典序排序，这样就使得前缀相同的单词排在一起了
然后我们维护一个栈，枚举所有的字符串（按字典序排好的） 如果当前的字符串能和栈顶的字符串接龙的话，那么当前字符串入栈，继续枚举下一个字符串，如果不能接龙，那么栈顶字符串弹出，当前字符串继续与弹出后的栈顶字符串比较，直到当前字符串与栈顶字符串能接成龙，然后当前字符串入栈，在这期间统计栈最多有多少个元素
*/
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
int n;
string s[1000001];
string a[1000001];
int k=0;
int top=0;
bool pd(string x,string y)
{if(x==y) return 0;int l=x.size();if(x!=y.substr(0,l)) return 0;return 1;
}
int main()
{freopen("Cola.txt","r",stdin);cin>>n;for(int i=1;i<=n;i++)cin>>s[i];sort(s+1,s+n+1);for(int i=1;i<=n;i++){if(top==0)top++,a[top]=s[i];elsewhile(top>0){if(pd(a[top],s[i])==1){top++;a[top]=s[i];break;}elsetop--;}if(top==0){top++;a[top]=s[i];}k=max(k,top);}cout<<k<<endl;return 0;
}

100分

 

转载于:.html