【BZOJ2754】【SCOI2012】喵星球上的点名 后缀数组优化暴力_空灰冰魂的博客-程序员宝宝

技术标签: BZOJ2754  SCOI2012  喵星球上的点名  后缀数组  暴力  

转载请注明出处谢谢:http://blog.csdn.net/vmurder/article/details/42963375

题意:

那个输入中每个串先是一个长度然后才是串。

然后如果某猫姓名abcd·efgh,那么点名abc,bcd,fg等都是好使的,但是cde就不行。


然后输入姓名时格式为一行

a a个数,b b个数。

A表示姓,B表示名。


题解:

直接暴力枚举每个点名是哪些的子串,

然后我们发现可以用后缀数组来优化这个事情~~


时间复杂度是不准确的,也就是说可以被卡成TLE,但是大家都没有写正解,

所以应该不会有丧(Po)心(Po)病(Q)狂(Q)者(Q)去Hack这道题的。


所以安心乱搞吧。

代码:

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 501000
#define M 50100
#define inf 10100
using namespace std;

int s[N],len;
int sa[N],rank[N],height[N];
int cnt[N],val[N],_val[N];
int stk[N],top;

int n,m,crs[N];
struct QUERY
{
	int n,s;
}Query[M];
int ans[M],vis[M];

void Input()
{
	int i,j,k,fengefu=inf;
	scanf("%d%d",&n,&m);
	// 为了避免多匹配,所以分隔符都不一样
	for(i=1;i<=n;i++) // 读入每个喵的姓名,中间有分隔符。
	{
		for(scanf("%d",&k);k--;)
		{
			crs[len]=i;
			scanf("%d",&s[len++]);
		}
		s[len++]=++fengefu;
		for(scanf("%d",&k);k--;)
		{
			crs[len]=i;
			scanf("%d",&s[len++]);
		}
		s[len++]=++fengefu;
	}
	for(i=1;i<=m;i++) // 输入每个点名
	{
		scanf("%d",&Query[i].n);
		Query[i].s=len;
		for(j=1;j<=Query[i].n;j++)
			scanf("%d",&s[len++]);
		s[len++]=++fengefu;
	}
}
inline bool cmp(int x,int y,int hl)
{return val[x]==val[y]&&((x+hl>=len&&y+hl>=len)||(x+hl<len&&y+hl<len&&val[x+hl]==val[y+hl]));}
void SA(int lim=256)
{
	int i,j,k,hl;

	for(i=0;i<lim;i++)cnt[i]=0;
	for(i=0;i<len;i++)cnt[val[i]=s[i]]++;
	for(i=1;i<lim;i++)cnt[i]+=cnt[i-1];
	for(i=len-1;i>=0;i--)sa[--cnt[val[i]]]=i;

	for(k=0;;k++)
	{
		top=0,hl=1<<k;
		for(i=0;i<len;i++)if(sa[i]+hl>=len)stk[++top]=sa[i];
		for(i=0;i<len;i++)if(sa[i]>=hl)stk[++top]=sa[i]-hl;

		for(i=0;i<lim;i++)cnt[i]=0;
		for(i=0;i<len;i++)cnt[val[i]]++;
		for(i=1;i<lim;i++)cnt[i]+=cnt[i-1];
		for(i=len;i;i--)sa[--cnt[val[stk[i]]]]=stk[i];

		for(i=lim=0;i<len;lim++)
		{
			for(j=i;j<len-1&&cmp(sa[j],sa[j+1],hl);j++);
			for(;i<=j;i++)_val[sa[i]]=lim;
		}
		for(i=0;i<len;i++)val[i]=_val[i];
		if(lim==len)break;
	}
	for(i=0;i<len;i++)rank[sa[i]]=i;
	for(k=i=0;i<len;i++)
	{
		if(k)k--;
		if(!rank[i])continue;
		while(s[i+k]==s[sa[rank[i]-1]+k])k++;
		height[rank[i]]=k;
	}
}
void Work()
{
	int i,j,k;
	int l,r,res;
	for(i=1;i<=m;i++){
		l=r=rank[Query[i].s];
		while(height[l]>=Query[i].n)l--;
		while(height[r]>=Query[i].n)r++;
		r--,res=0;
		for(j=l;j<=r;j++){
			if(crs[sa[j]]){
				if(vis[crs[sa[j]]]!=i){
					vis[crs[sa[j]]]=i;
					res++;
					ans[crs[sa[j]]]++;
				}
			}
		}
		printf("%d\n",res);
	}
	for(i=1;i<=n;i++)
	{
		printf("%d",ans[i]);
		if(i!=n)putchar(' ');
	}
}
int main()
{
	freopen("test.in","r",stdin);
	Input();
	SA(200000);
	Work();
	return 0;
}


版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/Vmurder/article/details/42963375

智能推荐

【自然语言处理】word2vec/doc2vec基础学习以及简单实践_贾继康的博客-程序员宝宝

文章目录一、前言二、 向量化算法word2vec2.1 引言2.2 word2vec原理2.3 词的表示三、神经网络语言模型四、C&amp;W模型五、CBOW模型5.1 CBOW模型结构图5.2 CBOW的输入输出六、Skip-gram模型6.1 Skip-gram模型结构图6.2 Skip-gram模型输入输出七、向量化算法doc2vec/str2vec7.1 doc2vec模型八、文本向量化...

pickle模块保存python对象到文件的使用方法_zjLOVEcyj的博客-程序员宝宝

1.保存python对象到文件import pickles = "测试串"f = open("./data/run.pkl", "wb")pickle.dump(s, f)f.close()2.从文件读取python对象import picklef = open("./data/run.pkl", "rb")s = pickle.load(f)f.close()pri...

Spring Cloud微服务架构实践与经验总结_豆奶快攻的博客-程序员宝宝_微服务架构经验

Spring Cloud 在国内中小型公司能用起来吗?从 2016 年初一直到现在,我们在这条路上已经走了一年多。在使用 Spring Cloud 之前,我们对微服务实践是没有太多的体会和经验的。从最初的开源软件云收藏来熟悉 Spring Boot,到项目中的慢慢使用,再到最后全面拥抱 Spring Cloud。这篇文章给大家介绍我们使用 Spring Boot / Cloud 一年多的经验总结。...

敦煌文化背后的区块链,让你的莫高窟线上燃灯被“永久”点亮_区块链大本营的博客-程序员宝宝

作者 | 宋慧责编 | 晋兆雨疫情的反复,让2021年的中国新年依旧与众不同。云过年、云喝酒,也让人们更切实体会了互联网与技术的妙处。今天是农历的腊月二十四,中国民间传统的“小年”,腾讯联...

骑士漫游_qq_775395462的博客-程序员宝宝_骑士漫游

DescriptionBackgroundThe knight is getting bored of seeing the same black and white squares again and again and has decided to make a journey around the world. Whenever a knight moves, it is

通俗易懂的nginx入门_way_more的博客-程序员宝宝

nginxNginx (engine x) 是一个高性能的HTTP和反向代理web服务器,同时也提供了IMAP/POP3/SMTP服务。Nginx是由伊戈尔·赛索耶夫为俄罗斯访问量第二的Rambler.ru站点(俄文:Рамблер)开发的,第一个公开版本0.1.0发布于2004年10月4日。Nginx是一款轻量级的Web 服务器/反向代理服务器及电子邮件(IMAP/POP3)代理服务器,在BSD-like 协议下发行。其特点是占有内存少,并发能力强,事实上nginx的并发能力在同类型的网页服务器中表现

随便推点

刚刚!字节跳动发布了600+前端岗位,平均薪资40K!_frontend_frank的博客-程序员宝宝

不愧是字节!5月官方又发布了600+前端工程师岗位!来源:字节跳动招聘官网那么本批有哪些优质岗位可选择?薪资待遇如何?下面给大家列出几类具体的岗位及要求,同时分享一份由字节3-1 面试官整...

利用Kail Linux进行目标侦察_bushi1787的博客-程序员宝宝

渗 透测试重要的阶段之一就是信息收集。作为攻 击者的一方会将大部分精力用在信息收集阶段。而对于企业中的渗 透测试人员来说,为了保证渗 透测试的准确性和有效性,测试人员需要收集关于目标主机的各方面信息,得到的信息越多,渗 透测试成功得概率就越大。侦察分为两种类型:被动侦察:一般是指分析公开的额信息,这些信息包括目标本身的信息和在线的公共资源信息,在获取这些信息是,测试者或攻 击者不会与目标交互,...

java基础--StringBuffer类常用方法以及案例_大数据小小罗的博客-程序员宝宝

StringBuffer类概述我们如果对字符串进行拼接操作,每次拼接,都会构建一个新的String对象,既耗时,又浪费空间。而StringBuffer就可以解决这个问题 线程安全的可变字符序列StringBuffer和String的区别?简单地说,就是一个变量和常量的关系。 StringBuffer对象的内容可以修改;而String对象一旦产生后就不可以被修改,重新赋值其实是两个对象。Strin

(实验15)单片机,STM32F4学习笔记,代码讲解【RTC实时时钟实验】【正点原子】【原创】_情系淮思的博客-程序员宝宝

(实验15)单片机,STM32F4学习笔记,代码讲解【RTC实时时钟实验】【正点原子】【原创】

Cluster sampling整群抽样例子_moonmoonb的博客-程序员宝宝_整群抽样的例子

整群(聚类)抽样的例子例题与方法步骤转述一下例子一个年级有3k名学生,要调查他们的数学成绩吧一共有60个班(群),每个班50人。大概只需要调查其中1000人,也就是20个班(群)。因此只需要在60个群里面随机抽取10个群即可。在R语言如何实现呢?set.seed(1996)# 定义班级id以及模拟每个学生的成绩class.id &lt;- rep(c(1:60),50)student.score &lt;- round(runif(3000,60,100))# 将以上数据合并dat

推荐文章

热门文章

相关标签