文档章节

CodeForces 955D - Scissors

o
 osc_g8254g7s
发布于 2019/08/19 20:50
字数 1503
阅读 20
收藏 0

昨晚CF比赛比较颓,今天有心情写题解就不错了QWQ

洛谷题目页面传送门 & CodeForces题目页面传送门

给定字符串$a,b,|a|=n,|b|=m$,求是否可以在$a$中选$2$个长度为$s$的不相交子串,使得$b$是这$2$个串按在$a$中的顺序连起来后得到的串的子串,若可以,输出任一选法。

$2\le m\le 2s\le n\le 5\times 10^5$。

设从$a$中选出的$2$个子串为$a1,a2$。分$2$种情况:

  1. $a1$或$a2$完全包含$b$;
  2. $a1$的一个后缀与$a2$的一个前缀组成$b$。

第$1$种情况比较容易,直接将$b$作为模式串匹配$a$(这里我用的是Z算法(如果聪明的读者还不知道Z算法是什么,please点击这个)),匹配成功的位置再分$2$种情况:$a1$包含$b$和$a2$包含$b$。$a1$包含$b$的情况考虑贪心地将$a1$最左化,好给$a2$留位置,最后如果放得下直接输出答案return 0;;$a2$包含$b$类似。

第$2$种情况,设$lft_i$表示满足$a_{j\sim j+s-1}$的长度为$i$的后缀匹配$b$的长度为$i$的前缀的最小的$j$,$rit_i$表示满足$a_{j\sim j+s-1}$的长度为$i$的前缀匹配$b$的长度为$i$的后缀的最大的$j$,若没有满足条件的$j$则分别为$\infty,-\infty$。“最小”和“最大”是基于贪心的思想,与第$1$种情况类似,为的是尽可能给另一个子串留位置。这样最后我们可以枚举$i\in[0,s]$,若$m-i\in[0,s]$且$lft_i+s-1<rit_{m-i}$,则存在答案$(lft_i,rit_{m-i})$。

下面考虑$lft$和$rit$数组怎么求。以$lft$为栗例,我们令$c=b+\texttt{!}+a$,对$c$跑一遍Z算法。$\forall i\in[1,n]$,考虑若$a1$的后缀从第$i$位开始,能影响到哪些$lft_j$。显然$j_{\max}=z_{c,m+1+j}$,因为最多能往后拓展$z_{c,m+1+j}$个字符,满足这个后缀与$b$的前缀匹配。$j_{\min}$呢?$j$越小,即$a1$在第$i$位后面的字符越少,那么$a1$在第$i$位前面的字符就越多,多到一定程度就会抵到位置$1$,所以$j_{\min}$是刚好抵到的情况,如果不会抵到就是$1$。于是$j_{\min}=\max(s-(i-1),1)$。算出影响范围后,我们要去“影响”啊,即令$\require{cancel}\forall j\in[j_{\min},j_{\max}],lft_j=\min(lft_j,i+j\cancel{-1}-s\cancel{+1})$。这个可以用线段树维护,差分也可以,虽然都是$\mathrm O(n\log_2n)$,但差分好写一点。

下面讲具体怎么差分:$\forall k\in[0,m]$,维护一个添加序列$add_k$和删除序列$del_k$。对于每次影响,在$add_{j_{\min}}$和$del_{j_{\max}+1}$里插入$i-s$。最后维护一个multiset$st$(初始为${\infty}$),从$i=1$到$i=m$递推,每次将$add_i$里的元素insert进去,将$del_i$里的元素erase掉(注意如果写st.erase(x)会把所有的$x$都删掉,应该写st.erase(st.find(x))),*st.begin()+i就是$lft_i$。

$rit$数组的求法类似,不同在于$c=b^\mathrm r+\texttt!+a^\mathrm r$,访问$z$数组时要访问在倒串中的位置,$j_{\min}=\max(s-(n-i),1),j_{\max}=z_{c,m+1+(n+1-i)}$,影响为$\forall j\in[j_{\min},j_{\max}],rit_j=\min(rit_j,i-j+1)$,$st$初始为${-\infty}$,每次插入$i+1$,$rit_i$为*--st.end()-i

下面贴代码吧:(写不动了)

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
const int inf=0x3f3f3f3f;
const int N=500000,M=500000;
int n/*|a|*/,m/*|b|*/,s/*要选的字串的长度*/,t/*|c|*/;
int rev_pos(int pos){return n+1-pos;}//在倒串中的位置 
char a[N+5],b[M+5],ra[N+5]/*rev(a)*/,rb[M+5]/*rev(b)*/,c[N+1+M+5]/*b+'!'+a或rb+'!'+ra*/;
void con(char str1[],char str2[]){//令c=str1+'!'+str2 
	t=0;
	for(int i=1;i<=m;i++)c[++t]=str1[i];
	c[++t]='!';
	for(int i=1;i<=n;i++)c[++t]=str2[i]; 
}
int z1[N+1+M+1]/*a,b正着的z数组*/,z2[N+1+M+1]/*a,b倒着的z数组*/;
void z_init(int z[]){//Z算法 
	int zl=0,zr=0;
	for(int i=2;i<=t;i++)
		if(zr<i){
			while(i+z[i]<=t&&c[i+z[i]]==c[1+z[i]])z[i]++;
			if(z[i])zl=i,zr=i+z[i]-1;
		}
		else if(i+z[i-zl+1]<=zr)z[i]=z[i-zl+1];
		else{
			z[i]=zr-i+1;
			while(i+z[i]<=t&&c[i+z[i]]==c[1+z[i]])z[i]++;
			zl=i;zr=i+z[i]-1;
		}
}
int lft[M+1],rit[M+1];
vector<int> dadd[M+1],ddel[N+1];//差分 
multiset<int> st;
int main(){
	cin>>n>>m>>s>>a+1>>b+1;
	memcpy(ra+1,a+1,n+1);reverse(ra+1,ra+n+1);
	memcpy(rb+1,b+1,m+1);reverse(rb+1,rb+m+1);
	con(b,a);z_init(z1);
	con(rb,ra);z_init(z2);
	if(s>=m)//第1种情况 
		for(int i=1;i<=n;i++)
			if(z1[m+1+i]==m){
				int l=max(1,i-(s-m)),r=l+s;
				if(r+s-1<=n)return cout<<"Yes\n"<<l<<" "<<r,0;
				r=min(n,i+s-1)-s+1;l=r-s;
				if(l>=1)return cout<<"Yes\n"<<l<<" "<<r,0;
			}
	//第2种情况 
	for(int i=1;i<=n;i++){//对lft影响 
		int l=max(s-(i-1),1),r=z1[m+1+i];
		if(l>r)continue;
		dadd[l].pb(i-s);if(r<m)ddel[r+1].pb(i-s);
	}
	st.insert(inf);//初始化 
	for(int i=1;i<=m;i++){//递推差分求lft 
		for(int j=0;j<dadd[i].size();j++)st.insert(dadd[i][j]);
		for(int j=0;j<ddel[i].size();j++)st.erase(st.find(ddel[i][j]));
		lft[i]=*st.begin()+i;
	}
	for(int i=1;i<=m;i++)dadd[i].clear(),ddel[i].clear();//数据不清空,爆零两行泪 
	for(int i=1;i<=n;i++){//对rit影响 
		int l=max(s-(n-i),1),r=z2[m+1+rev_pos(i)];
		if(l>r)continue;
		dadd[l].pb(i+1);if(r<m)ddel[r+1].pb(i+1);
	}
	st.clear();st.insert(-inf);//初始化 
	for(int i=1;i<=m;i++){//递推差分求rit 
		for(int j=0;j<dadd[i].size();j++)st.insert(dadd[i][j]);
		for(int j=0;j<ddel[i].size();j++)st.erase(st.find(ddel[i][j]));
		rit[i]=*--st.end()-i;
	}
//	for(int i=1;i<=m;i++)printf("lft[%d]=%d rit[%d]=%d\n",i,lft[i],i,rit[i]);
	for(int i=0;i<=s;i++)if(0<=m-i&&m-i<=s)
		if(lft[i]+s-1<rit[m-i])//不相交 
			return cout<<"Yes\n"<<lft[i]<<" "<<rit[m-i],0;
	puts("No");
	return 0;
}
o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。

暂无文章

pycurl libcurl link-time ssl backend (nss)

pip uninstall pycurlecho 'pycurl==7.19.5.1 --global-option="--with-nss"' > requires.pypip install -r requires.py...

小红手
16分钟前
17
0
计算机网络性能衡量

1、速率 单位时间(s)内传输信息(bit)量 单位:KB/s, MB/s, Gb/s K = 10^3 ,M = 10^6, G=10^9 一般表示的是理想的传输速率 2、带宽 计算机网络中的带宽和通信等领域的带宽概念不一样,计算机网...

osc_np3y0rbq
16分钟前
3
0
互联网掀起农家乐,巨头上演AI掘金战

配图来自Canva **前有网易、阿里AI养猪,后有腾讯AI养鹅,互联网大佬们纷纷玩起了“农家乐”,互联网的生意在尖端技术的引领之下频频跨界,巨头之间的较量也从线上延伸至线下。**自古“民以食...

osc_5cok9i01
17分钟前
5
0
原来!我在4年前就开始体验雾游戏了!

前有云游戏后有雾游戏,游戏的方式看来起来越来越多种多样。那么“震撼业界”的雾游戏到底是什么来头?它依靠什么改变游戏界?它的原理又是什么? 本月月初,著名的日本游戏杂志《Fami通》表...

osc_j34n26zn
19分钟前
5
0
活动预告|田溯宁与你相约GSMA Thrive·万物生晖,分享5G风口下的创新与投资洞察

在万物互联的时代背景下,5G+AI+IoT的技术变革与融合,正在引发一场深刻的全产业创新与变革。5G技术创新、行业应用及投资机遇已成为科技行业所瞩目的焦点。 6月30日,宽带资本董事长田溯宁将...

osc_0qnrwmy3
20分钟前
7
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部