[CODEVS1051]接龙游戏

题目描述

给出了N个单词，已经按长度排好了序。如果某单词i是某单词j的前缀，i->j算一次接龙(两个相同的单词不能算接龙)。

你的任务是：对于输入的单词，找出最长的龙。

输入描述 Input Description

第一行为N(1<=N<=105)。以下N行每行一个单词（由小写组成），已经按长度排序。(每个单词长度<50)

输出描述 Output Description

仅一个数，为最长的龙的长度。

数据范围及提示 Data Size & Hint

1<=N<=105

看到这道题，虽然知道是用栈来做，但是还是没有思路，太弱……就去找题解（捂脸熊

大概是这样子的：

我们玩过的接龙游戏一般都是A是B的后缀，则可以接龙；但是这道题为i是j的前缀，那么i->j算一次接龙，所以可以把输入的单词按字典序排序，那么前缀相同的单词就会堆在一起了（sort(ch,ch+n,cmp)）

这时我们维护一个栈，首先将第一个单词入栈，将每一个单词与栈顶元素find，如果在第i个单词中第0个位置开始可以找到top，那么我们把第i个单词入栈，继续读下一个单词；

如果不能找到，则弹出栈顶元素，将第i个单词与新的栈顶元素进行相同的操作，直到栈空，将第i个单词入栈。

在以上过程中，我们可以不断更新max的值，表示栈中的元素，即最多有多少个单词可以互相接龙，max=max<stack.size()?stack.size():max;

这道题的思路就是这样子了。代码自己改了半天。。。。

代码：

#include<iostream>

#include<cstdio>

#include<stack>

#include<cstring>

#include<algorithm>

using namespace std;

typedef struct data

{

    string s;

}data;

data ch[];

bool cmp (data x,data y)

{

    int len=x.s.length()>y.s.length()?x.s.length():y.s.length();

    for(int i=;i<len;++i)

    {

        if(x.s[i]<y.s[i]) return true;

        else if(x.s[i]>y.s[i]) return false;

    }

    if(x.s.length()<y.s.length()) return true;

    else return false;

}

int main()

{

    int n,max=;

    cin>>n;

    for(int i=;i<n;++i)

    cin>>ch[i].s;

    sort(ch,ch+n,cmp);

    /*for(int i=0;i<n;++i)

    cout<<ch[i].s<<' ';*/

    stack<data> mystack;

    mystack.push(ch[]);

    for(int i=;i<n;++i)

    {

        data tmp;

        tmp=mystack.top();

        if(ch[i].s.find(tmp.s,)==)

        {

            if(tmp.s.length()!=ch[i].s.length())

            mystack.push(ch[i]);

        }

        else

        {

            while(!mystack.empty())

            {

                tmp=mystack.top();

                if(ch[i].s.find(tmp.s,)==)

                break;

                mystack.pop();

            }

            mystack.push(ch[i]);

        }

        max=max>mystack.size()?max:mystack.size();

    }

    cout<<max<<endl;

    return ;

}

巴特西

[CODEVS1051]接龙游戏

最新文章

热门文章