[Luogu2462][SDOI2007]游戏(字符串Hash,最长路)

发布于 2018-05-28  190 次阅读


本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[Luogu2462][SDOI2007]游戏(字符串Hash,最长路)

Description

小木木和小凳子试两个聪明的孩子,他们五岁的时候就开始学习英语了。
英语老师教他们玩一个很简单的游戏。老师给他们一张全小写并无特殊符号的英语单词表,单词表如下:
ab arc arco bar bran carbon carbons
cobra crab crayon narc
然后让他们从单词表里找词语接龙。接龙的规则如下:
1 前一个单词拥有的所有字母,在后一个单词里必须出现,而且字母出现次数不少于前一单词。
2 后一个单词的长度比前一个单词的长度恰好多1
对于以上例子,一合法的接龙为:
ab bar crab cobra carbon carbons
他们之中,谁接龙的长度长,谁就赢了。小木木肯定不想输,所以找到你,放肆撒娇,导致你因为不想再被打扰而帮他了。至于小凳子呢??说不定找郭大牛去了。嘿嘿,你和郭大牛的编程比赛??加油吧!!!

Tag

字符串Hash,最长路

解决思路

标签中给的虚树?
把单词\(Hash\)起来,然后枚举加上哪一个字母,再\(hash\)判断是否存在这样的单词,如果存在则连边,这样可以构建出一张\(DAG\),在\(DAG\)上动态规划求最长路就好。

代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

#define ll long long
#define mem(Arr,x) memset(Arr,x,sizeof(Arr))

const int maxN=11000;
const int maxM=maxN*100;
const int HashSize=1000000;
const int maxS=110;
const int Base=29;
const int maxAlpha=26;
const int inf=2147483647;

int n;
int Map[HashSize];
int edgecnt=0,Head[maxN],Next[maxM],V[maxM];
char Input[maxN][maxS];
int Cnt[maxN][maxAlpha];
int Degree[maxN],Queue[maxN],F[maxN],Path[maxN];

void Add_Edge(int u,int v);
void Outp(int id);

int main()
{
    n=0;mem(Head,-1);
    while (scanf("%s",Input[++n]+1)!=EOF);
    n--;
    for (int i=1;i<=n;i++)
    {
        int l=strlen(Input[i]+1);
        for (int j=1;j<=l;j++) Cnt[i][Input[i][j]-'a']++;
        int hash=0;
        for (int j=0;j<maxAlpha;j++) hash=(hash*Base%HashSize+Cnt[i][j])%HashSize;
        Map[hash]=i;
    }
    for (int i=1;i<=n;i++)
    {
        for (int j=0;j<maxAlpha;j++)
        {
            Cnt[i][j]++;
            int hash=0;
            for (int k=0;k<maxAlpha;k++) hash=(hash*Base%HashSize+Cnt[i][k])%HashSize;
            if (Map[hash]) Add_Edge(i,Map[hash]);
            Cnt[i][j]--;
        }
    }
    int h=0,t=0;
    for (int i=1;i<=n;i++) if (Degree[i]==0) Queue[++h]=i,F[i]=1;
    do
    {
        int u=Queue[++t];
        for (int i=Head[u];i!=-1;i=Next[i])
        {
            Degree[V[i]]--;
            if (F[V[i]]<F[u]+1) F[V[i]]=F[u]+1,Path[V[i]]=u;
            if (Degree[V[i]]==0) Queue[++h]=V[i];
        }
    }
    while (t!=h);
    int id=1;
    for (int i=2;i<=n;i++) if (F[i]>F[id]) id=i;
    printf("%d\n",F[id]);
    Outp(id);
    return 0;
}

void Add_Edge(int u,int v)
{
    edgecnt++;Next[edgecnt]=Head[u];Head[u]=edgecnt;V[edgecnt]=v;Degree[v]++;
    return;
}

void Outp(int id)
{
    if (id==0) return;
    Outp(Path[id]);
    printf("%s\n",Input[id]+1);
    return;
}

本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[Luogu2462][SDOI2007]游戏(字符串Hash,最长路)


HNCJ OIer 一枚