CodeForces 955D Scissors
2019-08-26 05:35:58来源:博客园 阅读 ()
CodeForces 955D Scissors
昨晚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\)种情况:
- \(a1\)或\(a2\)完全包含\(b\);
- \(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+`\text{!'}+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=\mathrm{rev}(b)+`\text{!'}+\mathrm{rev}(a)\),访问\(z\)数组时要访问在倒串中的位置,\(j_{\min}=\max(s-(n-i),1),j_{\max}=z_{c,m+1+rev\_pos(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;
}
原文链接:https://www.cnblogs.com/ycx-akioi/p/CodeForces-955D.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- CodeForces 1326E - Bombs 2020-03-25
- CodeForces 1320D - Reachable Strings 2020-03-20
- CodeForces 1324 - Codeforces Round #627 (Div. 3) 2020-03-13
- CodeForces 710D Two Arithmetic Progressions 2020-03-06
- CodeForces 1313D Happy New Year 2020-03-04
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash