首页 > 代码库 > AC日记——接龙游戏 codevs 1051

AC日记——接龙游戏 codevs 1051

2024-08-27 21:09:57   219人阅读

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

 

思路：

　　用hash表把所有的单词给存起来

　　然后比较的时候用hash表比较

　　然后线性结构比较是否为前缀的复杂度为n^2

　　然而n<=100000

　　超时稳稳的

　　那，如何优化呢？

　　考虑把线性比较转化成树

　　建立一个根节点

　　我们从根节点找这个单词的前缀

　　如果没有这个单词的前缀

　　则把这个单词作为一个叶节点生长在根节点上

　　如果找到了

　　则跳入这个叶节点

　　继续从这个叶节点找前缀

　　直到找不到，然后把这个单词作为一个新的叶节点生长在当前节点上

　　这样会优化很多很多

　　轻松ac

 

 

来，上代码：

#include<cstdio>#include<string>#include<cstring>#include<iostream>#define mod 10000007using namespace std;struct node {    int from,to,dis,next;};struct node edge[100001];int n,len[100001],hash[100001][51],dp[100001];int head[100001],num,ans=0;string word[100001];inline void edge_add(int from,int to){    num++;    edge[num].to=to;    edge[num].from=from;    edge[num].next=head[from];    head[from]=num;}void dfs(int now,int pos,int be){    ans=max(now,ans);    for(int i=head[be];i;i=edge[i].next)    {        if(len[edge[i].to]<len[pos])        {            if(hash[edge[i].to][len[edge[i].to]-1]==hash[pos][len[edge[i].to]-1])            {                dfs(now+1,pos,edge[i].to);                return ;            }        }        }    edge_add(be,pos);}int main(){    len[0]=1;    scanf("%d",&n);    for(int i=1;i<=n;i++)    {        dp[i]=1;        cin>>word[i];        len[i]=word[i].length();        for(int j=0;j<len[i];j++)        {            hash[i][j]=word[i][j]-‘a‘+1;            if(j) hash[i][j]+=(hash[i][j-1]*29)%mod;            hash[i][j]%=mod;        }        dfs(1,i,0);    }    cout<<ans<<endl;    return 0;}

 

AC日记——接龙游戏 codevs 1051


联系
我们