欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

[SDOI2007]游戏(哈希+拓扑)

程序员文章站 2024-03-19 11:55:28
...

题目描述

小木木和小凳子试两个聪明的孩子,他们五岁的时候就开始学习英语了。

英语老师教他们玩一个很简单的游戏。老师给他们一张全小写并无特殊符号的英语单词表,单词表如下:

a b    a r c    a r c o    b a r    b r a n    c a r b o n    c a r b o n s    c o b r a    c r a b    c r a y o n    n a r c ab \; arc\; arco \;bar\; bran \;carbon\; carbons\;cobra \; crab \; crayon \;narc abarcarcobarbrancarboncarbonscobracrabcrayonnarc

然后让他们从单词表里找词语接龙。接龙的规则如下:

1 1 1 前一个单词拥有的所有字母,在后一个单词里必须出现,而且字母出现次数不少于前一单词。

2 2 2 后一个单词的长度比前一个单词的长度恰好多1

对于以上例子,一合法的接龙为:

a b    b a r    c r a b    c o b r a    c a r b o n    c a r b o n s ab \;bar \;crab\; cobra\; carbon\; carbons abbarcrabcobracarboncarbons

他们之中,谁接龙的长度长,谁就赢了。小木木肯定不想输,所以找到你,放肆撒娇,导致你因为不想再被打扰而帮他了。至于小凳子呢??说不定找郭大牛去了。嘿嘿,你和郭大牛的编程比赛??加油吧!!!

输入格式

n ( 1 < = n < = 10000 ) n(1<=n<=10000) n(1<=n<=10000) 行,每行一个长度不超过 100 100 100 的单词。

输出格式

第一行,输出最大长度 a n s ans ans

接下来的 a n s ans ans 行,每行输出一个字符串代表你的方案。

输入输出样例

输入

ab
arc
arco
bar
bran
carbon
carbons
cobra
crab
crayon
narc

输出

6
ab
bar
crab
cobra
carbon
carbons

[SDOI2007]游戏(哈希+拓扑)
首先排除这个题是个动态规划
我们可以用 H a s h + T o p s o r t Hash+Topsort Hash+Topsort来水这个题
在每次输入字符串的时候,可以存一下有几个 a a a,几个 b b b,几个 c … … c…… c
并且找一个合适的质数,给每个字母搞一个 H a s h Hash Hash值,然后给每个字符串做一个 H a s h Hash Hash
扫下看有没有比该字符串长一个字母的字符串,然后在他们两个之间连一个有向边
在拓扑的时候,利用先前记录的每个字母的个数,来进行验证
还有一点就是因为要输出方案,所以我们拓扑时可以记录下该点的上一个点的下标
然后就 A A A

#include<bits/stdc++.h>
using namespace std;
#define N 10010
#define ZS 4099
#define MOD 19260817
struct ao{int y,nxt;}e[N<<3];
struct zyzyyds{int zm[27],ans;char c[110];}zyz[N];//这个题是一个叫zyz的学长给我的
char lp[N][110];
int rudu[N],cnt,cd[110],linshi,maxx,hd[N],n,tot,hx[27],zz[20050000],zz2[N],mm;
void lian(int x,int y){e[++tot].y=y;e[tot].nxt=hd[x];hd[x]=tot;rudu[y]++;}//正常的连边
void tuopu()
{
	queue<int>q;
	for(int i=1;i<=n;i++)if(!rudu[i])q.push(i);
	while(q.size())
	{
		int x=q.front();q.pop();
		for(int i=hd[x];i;i=e[i].nxt)
		{
			int y=e[i].y,duo=0;bool flag=0;
			for(int j=0;j<26;j++)//对比每个字母个数
			{
				int cha=zyz[y].zm[j]-zyz[x].zm[j];
				if(cha<0){flag=1;break;}
				if(cha>1){flag=1;break;}
				duo+=cha;
			}
			if(duo==1&&flag==0&&zyz[y].ans<zyz[x].ans+1{zyz[y].ans=zyz[x].ans+1;zz2[y]=x;}
			//传递接龙长度,并建立一个反过来指的边
			if(--rudu[y]==0)q.push(y);
		}
	}
}
int main()
{
	hx[0]=ZS%MOD;
	for(int i=1;i<=26;i++) hx[i]=(1ll*hx[i-1]*ZS)%MOD;//给每个字母搞个Hash值
	while(scanf("%s",zyz[n+1].c+1)!=EOF)
	{
		n++;zyz[n].ans=1;linshi=0;//记录有n个字符串,只输出这个字符串的话答案为1
		for(int j=1;zyz[n].c[j]!='\0';j++)
		{
			zyz[n].zm[zyz[n].c[j]-'a']++;//存字符串对于每个字母的个数
			linshi=(linshi+hx[zyz[n].c[j]-'a'])%MOD;//linshi记录Hash值
		}
		zz[linshi]=n;//以该字符串Hash后的值为下标,记录字符串节点的下标
	}
	for(int i=0;i<=MOD;i++)//扫描
	{
		if(zz[i]==0) continue;
		for(int j=0;j<26;j++)if((zz[(i+hx[j])%MOD])!=0)lian(zz[i],(zz[(i+hx[j])%MOD]));
		//扫一下关于该字符串加上任意一个字母后的Hash值是否存在节点,如果有,就连下边
	}
	tuopu();//拓扑排序
	for(int i=1;i<=n;i++)if(maxx<zyz[i].ans){maxx=zyz[i].ans;mm=i;}//记录最大答案和字符串下标
	cout<<maxx<<'\n';//先输出答案
	for(int i=mm;i;i=zz2[i])strcpy(lp[++cnt],zyz[i].c+1);//往回扫一遍并复制字符串
	while(cnt){printf("%s\n",lp[cnt]);cnt--;}//输出
	return 0;
}

zyz学长太强了

相关标签: 水题 c++