2018.9.22 ACM训练 CCPC北京 [email protected]的博客-程序员宅基地

技术标签: 个人总结  ACM  CCPC  ONline  

网络赛的画风都略有奇怪
但是我们发挥的更差了
话说网络赛没有题解真是气人!

题目

I 是道好题,但是莫名奇妙T了
给出一些子串,求将它们顺次排列后序列,使相邻串lcp的字典序。
做法: 后缀树+虚树+树形dp
考场上没有想到dp的思想把每个子树中的序列按字典序排序后合并起来。分隔符是这个点的val。启发式合并保证复杂度。
当时写的奇奇怪怪的贪心细节很多没有考虑全面,调了很久也没有调出来。

把代码粘出来留坑。有两个问题:1. 可能是vec开得太多。不知道为什么超级慢,把maxn一开大就会慢
2. 在后缀树上定位串需要倍增,不能直接暴力跳

#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define per(i,a,b) for(int i=a;i>=b;--i)
#define rvc(i,S) for(int i=0;i<(int)S.size();++i)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define debug(...) fprintf(stderr,__VA_ARGS__)
using namespace std;
#define inf 0x3f3f3f3f
#define maxn 4020

struct node{
	int next,to;
}e[maxn];

int head[maxn],cnt,tot;
int id[maxn],sz[maxn],fa[maxn],mn[21][maxn * 2],num[maxn * 2],a[maxn * 2],dfstime,dth[maxn],dfn[maxn],len[maxn],pnt[maxn];
int stack_[maxn],tops,rec,rt,tag[maxn];
int n,m,T;
char ch[maxn];
vector <int> vec[maxn],son[maxn],ans,dt[maxn],p;

inline void adde(int x,int y){
	e[++cnt].to = y;
	e[cnt].next = head[x];
	head[x] = cnt;
}
struct SAM{
	int next[maxn][26],val[maxn],pnt[maxn],last,tot;
	void clear(){
		rep(i,0,tot) memset(next,0,sizeof(next)) , val[i] = pnt[i] = 0;
		tot = last = 0;
	}
	void Add(int x){
		int p = last , np = ++tot;
		val[np] = val[p] + 1 , id[val[np]] = tot + 1;
		while ( !next[p][x] && p ) next[p][x] = np , p = pnt[p];
		int q = next[p][x];
		if ( !q ) next[p][x] = np , pnt[np] = p;
		else if ( val[p] + 1 == val[q] ) pnt[np] = q;
		else{
			int nq = ++tot;
			val[nq] = val[p] + 1;
			pnt[nq] = pnt[q];
			pnt[np] = pnt[q] = nq;
			memcpy(next[nq],next[q],sizeof(next[q]));
			while ( p && next[p][x] == q ) next[p][x] = nq , p = pnt[p];
			if ( next[p][x] == q ) next[p][x] = nq;
		}
		last = np;
	}
	void pre(){
		rep(i,1,tot + 1) head[i] = 0;
		cnt = 0;
		rep(i,1,tot) adde(pnt[i] + 1,i + 1) , len[i + 1] = val[i];
	}
	void print(){
		rep(i,1,tot) cout<<i + 1<<" "<<pnt[i] + 1<<endl;
	}
}sam;


void clear(){
	sam.clear();
	cnt = tot = 0;
}
void clear2(){
	cnt = 0;
	tops = 0;
	p.clear();
}

inline bool cmp(int x,int y){ return dfn[x] < dfn[y]; }

void dfs(int x){
	a[++tot] = x , dfn[x] = tot;
	for (int &i = head[x] ; i ; i = e[i].next){
		pnt[e[i].to] = x , dth[e[i].to] = dth[x] + 1;
		dfs(e[i].to);
		a[++tot] = x;
	}
}
void Init_Tree(){
	dfs(1);
	rep(i,1,tot){
		num[i] = num[i - 1];
		if ( (1 << (num[i] + 1)) < i ) num[i]++;
	}		
	rep(i,1,tot) mn[0][i] = a[i];
	rep(i,1,20){
		rep(j,1,tot){
			if ( j + (1 << (i - 1)) > tot || dth[mn[i - 1][j]] < dth[mn[i - 1][j + (1 << (i - 1))]] ) 
				mn[i][j] = mn[i - 1][j];
			else 
				mn[i][j] = mn[i - 1][j + (1 << (i -1))];
		}
	}
}

void init(){
	rep(i,1,n) sam.Add(ch[i] - 'a');
	sam.pre();
	Init_Tree();
//	sam.print();
}
inline int lca(int x,int y){
	int l = dfn[x] , r = dfn[y];
	if ( l > r ) swap(l,r);
	int len = r - l + 1,c = num[len],id1 = mn[c][l],id2 = mn[c][r - (1 << c) + 1];
	if ( dth[id1] < dth[id2] ) return id1;
	return id2;
}
void insert(int x){
	if ( !tops ){ stack_[++tops] = x; return; }
	int v = stack_[tops] , lca_ = lca(v,x) , w = stack_[tops - 1];
	while ( tops > 1 && dth[w] > dth[lca_] ){
		adde(w,v);
		tops--;
		v = w;
		w = stack_[tops - 1];
	}
	if ( v != lca_ ){
		adde(lca_,v) , tops--;
		if ( stack_[tops] != lca_ ) stack_[++tops] = lca_;
	}
	stack_[++tops] = x;
}

inline bool cmp2(int x,int y){
	if ( !vec[x].size() ) return 0;
	if ( !vec[y].size() ) return 1;
	rep(i,0,min(vec[x].size(),vec[y].size()) - 1) if ( vec[x][i] != vec[y][i] ) return vec[x][i] > vec[y][i];
	return vec[x].size() > vec[y].size();
}	
inline void merge(int x,int y){
	if ( vec[x].size() > vec[y].size() ){
		rvc(i,vec[y]) vec[x].pb(vec[y][i]);
	}
	else{
		rvc(i,vec[x]) vec[y].pb(vec[x][i]);
		//vec[x].begin() = vec[y].begin();
		//vec[x].swap(vec[y]);
		swap(vec[x],vec[y]);
	}
}
void dfs2(int x){
	for (int i = head[x] ; i ; i = e[i].next){
		dfs2(e[i].to);
		if ( sz[e[i].to] ) son[x].pb(e[i].to);
		sz[x] += sz[e[i].to];
	}	
	sort(son[x].begin(),son[x].end(),cmp2);
	rvc(i,son[x]){
		merge(x,son[x][i]);
		if ( i < (int)son[x].size() - 1 ) vec[x].pb(len[x]);
	}
	if ( dt[x].size() && son[x].size() ) vec[x].pb(dt[x].back());
	while ( dt[x].size() > 1 ) vec[x].pb(dt[x][dt[x].size() - 2]) , dt[x].pop_back(); 
}
void dfs_c(int x){
	vec[x].clear() , dt[x].clear() , son[x].clear();
	sz[x] = 0;
	for (int &i = head[x] ; i ; i = e[i].next){
		fa[e[i].to] = 0;
		dfs_c(e[i].to);
	}
}

void solve(){
	dfs_c(rt);
	clear2();
	int t,l,r,clen,cur;
	scanf("%d",&t);
	rep(i,1,t){
		scanf("%d %d",&l,&r) , l++ , r++;
		clen = r - l + 1 , l = n - l + 1;
		cur = id[l];
		while ( clen <= len[pnt[cur]] ) cur = pnt[cur];
		sz[cur]++ , p.pb(cur) , dt[cur].pb(clen);
	}
	sort(p.begin(),p.end(),cmp);
	p.erase(unique(p.begin(),p.end()),p.end());
	rvc(i,p) insert(p[i]);
//	rvc(i,p) cout<<p[i]<<" ";
//	cout<<endl;
	while ( tops > 1 ) adde(stack_[tops - 1],stack_[tops]) , tops--;
	rt = stack_[1];
	dfs2(rt);
	
	rvc(i,vec[rt]){
		printf("%d",vec[rt][i]);
		if ( i < vec[rt].size() - 1 ) printf(" ");
		else printf("\n");
	}

}
int main(){
	freopen("input.txt","r",stdin);
	scanf("%d",&T);
	rep(t,1,T){
		printf("Case %d:\n",t);
		clear();
		scanf("%d %d",&n,&m);
		scanf("%s",ch + 1);
		reverse(ch + 1,ch + n + 1);
		init();
		while ( m-- ){
			solve();
		}	
	}
}


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

智能推荐

springMVC使用Antisamy防御XSS配置(包括请求黑白名单)_Abdulaziz02的博客-程序员宅基地_antisamy springmvc

AntiSamy是OWASP的一个开源项目,通过对用户输入的 HTML / CSS / JavaScript 等内容进行检验和清理,确保输入符合应用规范。AntiSamy被广泛应用于Web服务对存储型和反射型XSS的防御中。1、maven依赖 &lt;dependency&gt; &lt;groupId&gt;org.owasp.antisamy&lt;/groupId&gt; &lt;artifactId&gt;antisamy&lt;/artifactId&gt; &lt;version

Eclipse3.5与Flex Builder3安装和Flash Builder4安装_weixin_33805743的博客-程序员宅基地

使用Eclipse3.5集成Flex3或Flashbuilder4插件 运行环境 Windows32操作系统 引用Eclipse3.5 galileo win32 版本 http://www.eclipse.org/downloads/download.php?file=/technology/epp/downloads/release/galileo/SR1/eclipse-jee-ga...

dbgrideh、dxdbgrid和cxgrid保留上次的列宽、列序_qq_27612335的博客-程序员宅基地

delphi中常用的数据显示控件大多数都可以用拖动来调列顺序和列宽,而且这些设置是可以在下次打开时保留上次的操作的,这是个很实用也很有用的功能,能给用户很好的使用体验,下面是常用的DBGridEh、DxDbGrid和cxgrid三个数据显示控件的设置方法: dbgrideh:需要另外一个控件,PropStorageEh  PropStorageEh 可以很方便的将窗体中控件

mysql 5.7.18-winx64_MySQL免安装版mysql-5.7.18-winx64 在win10系统下配置过程_weixin_39603537的博客-程序员宅基地

本文是参照上面三个文章针对本人情况进行的整理,感谢上面三位作者分享的MySQL下载地址:1.下载解压MySQL压缩包将以下载的MySQL压缩包解压到自定义目录下,我的解压目录是:"D:\JavaDevelop\mysql-5.7.18-winx64"在目录下新建一个my.ini文件内容为[mysql]#设置mysql客户端默认字符集default-character-set=utf8[mysql...

面向切面编程——java_leesire的博客-程序员宅基地

-AOP(面向切面编程)-AOP为Aspect Oriented Programming的缩写,意为:面向切面编程,通过预编译方式和运行期动态代理实现程序功能的统一维护的一种技术。AOP是OOP的延续,是软件开发中的一个热点,也是Spring框架中的一个重要内容,是函数式编程的一种衍生范型。利用AOP可以对业务逻辑的各个部分进行隔离,从而使得业务逻辑各部分之间的耦合度降低,提高程序的可重用

mysql进程间通信_数据库进程间通信解决方案(二)_尸姐的博客-程序员宅基地

在《数据库进程间通信解决方案(一)》中我介绍了使用 fifo 管道实现数据与进程通信。netkiller:数据库进程间通信解决方案(一)​zhuanlan.zhihu.com作者:Mr. Neo Chen (陈景峯), netkiller, BG7NYT下面我们介绍使用 ZeroMQ 实现数据库与进程通信1. 背景该文章中提出了通过fifo 管道,实现数据库与其他进程的通信。属于 IPC 机制(同...

随便推点

算法图解1-二分法与大O表示法_/少司命的博客-程序员宅基地

目录一,二分法与大O表示法1.1写在前面1.2需要具备的知识1.3二分法1.4更佳的查找方式1.4.1代码设计1.4.2运行时间1.5大O表示法1.5.1算法的运行时间以不同的速度增加1.5.3一些常见的大O运行时间一,二分法与大O表示法1.1写在前面从今天开始,我将开始更新算法图解入门,也是自己在不断的学习中总结经验,感兴趣的可以点个关注,有时间就会更新算法相关的知识点,可能在十天内就可以完成更新,你的每一个点赞和收藏都是我最大的动力。文字和图片...

【Spring】一次线上@Transational事务注解未生效的原因探究_kingmax54212008的博客-程序员宅基地

【Spring】一次线上@Transational事务注解未生效的原因探究  java   spring   事务   aop   动态代理4现象描述上周同事发现其基于mySql实现的分布式锁的线上代码存在问题,代码简化如下:@Controllerclass XService { @Autowired private YService yS...

032_《Delphi下用Intraweb开发WEB程序应用实战(第二版)》_iteye_365的博客-程序员宅基地

《Delphi下用Intraweb开发WEB程序应用实战第二版》Delphi 教程 系列书籍 (032) 《Delphi下用Intraweb开发WEB程序应用实战第二版》 网友(邦)整理 EMail: [email protected]下载地址:Pdf作 者:高勇内容简介IntraWeb是Delphi自带的一套Web开发框架,它由Atozed Software公司(...

8.5. Windows_Sumarua的博客-程序员宅基地

文章目录8.5. Windows8.5.1. 本地用户认证8.5.2. SAM8.5.3. 密码破解8.5. Windows8.5.1. 本地用户认证Windows 在进行本地登录认证时操作系统会使用用户输入的密码作为凭证去与系统中的密码进行对比验证。通过 winlogon.exe 接收用户输入传递至lsass.exe 进行认证。winlogon.exe 用于在用户注销、重启、锁屏后显示登录界面。lsass.exe 用于将明文密码变成NTLM Hash的形式与SAM数据库比较认证。8.5.2. S

Selenium登录验证码解决方案细解_大牛测试的博客-程序员宅基地

#大牛测试,专注测试技术#qq:2574674466#简简单单自动化测试在网站中加入验证码的目的是加强用户安全性和提高反爬虫机制,在登录网站时,经常遇到各种各样验证码如:1) 英文与数字结合2) 汉字3) 图形,如12306登录等等,因验证码的存在,对自动化测试工具造成极大困扰有困难,但还是要解决的........以下列出一些处理策略1)调用OCR识别: ...

推荐文章

热门文章

相关标签