CodeForces 1320D - Reachable Strings
2020-03-20 16:01:24来源:博客园 阅读 ()
CodeForces 1320D - Reachable Strings
分析性质,二分查找+序列哈希洛谷题目页面传送门 & CodeForces题目页面传送门
有一个01串\(a,|a|=n\)。\(q\)次询问,每次给出\(l1,l2,len\),问\(a_{l1\sim l1+len-1},a_{l2\sim l2+len-1}\)这\(2\)个01串是否能通过若干次操作变得相等,其中一次操作指的是将任意一个01串的任意一个等于\(\texttt{110}\)的子串变成\(\texttt{011}\)或将\(\texttt{011}\)变成\(\texttt{110}\)。
\(n,q\in\left[1,2\times10^5\right]\)。
考虑分析能通过若干次操作变得相等的充要条件。
不难发现,每次操作都不可能改变01串中\(\texttt0\)和\(\texttt1\)分别的数量,所以\(2\)个01串中\(\texttt0\)和\(\texttt1\)的数量分别相等是能通过若干次操作变得相等的必要条件,但充分性还远远不够。
又发现,\(\texttt{110}\leftrightarrow\texttt{011}\)这个操作比较有意思,它相当于将这个唯一的\(\texttt{0}\)向左/右推了\(2\)位。由于这是个01串,非\(\texttt0\)即\(\texttt1\),于是我们将所有\(\texttt0\)的位置揪出来,其他位置自然是\(\texttt1\)。
不难发现,01串中所有\(\texttt0\)对的相对位置都不会改变。证明:若\(2\)个\(\texttt0\)想要交换位置,那么交换前最后一刻的状态一定是距离差\(\leq2\),此时左边的\(\texttt0\)不能通过\(\texttt{011}\to\texttt{110}\)往右再移\(2\)格,因为它右边\(1\sim2\)格是右边的\(\texttt0\),以它开头的长度为\(3\)的子串一定不为\(\texttt{011}\)。类似地,右边的\(\texttt0\)也不能往左移\(2\)格。得证。
于是考虑将\(2\)个01串中的所有\(\texttt0\)按出现次序一一对应。显然,第\(1\)个01串中的某个\(\texttt0\)能够与第\(2\)个01串中的某个\(\texttt0\)到同一位置上当且仅当它们在所在串中的位置之差为偶数,即奇偶性相等。所以我们猜测:\(2\)个01串中的所有\(\texttt0\)按出现次序一一对应后,每对\(\texttt0\)在所在串中的位置奇偶性相等,是这\(2\)个01串能通过若干次操作变得相等的充要条件。证明:
- 充分性证明:数学归纳法。
- 当\(2\)个串都不存在\(\texttt0\)时,充分性显然;
- 假设当\(2\)个串都存在\(x-1(x\geq1)\)个\(\texttt0\)时,满足充分性。此时若要将\(2\)个存在\(x\)个\(\texttt0\)的01串的所有\(\texttt0\)对一一对齐,可以将左数第\(1\)对\(\texttt0\)中较右的那个\(\texttt0\)通过若干次操作与较左的对齐,问题转化为将剩下\(x-1\)对\(\texttt0\)一一对齐,根据假设,存在方案。所以若当\(2\)个串都存在\(x-1\)个\(\texttt0\)时,满足充分性,那么当\(2\)个串都存在\(x\)个\(\texttt0\)时,满足充分性。
- 必要性显然。
综上,得证。
接下来问题就变成了比较裸的序列哈希:每次给定\(2\)个子串,问这\(2\)个子串中\(\texttt0\)的位置奇偶性组成的序列是否相等。注意:这里的位置奇偶性指的是相对于\(l1/l2\)的位置奇偶性,而不是相对于\(1\),所以要记录\(2\)个每项对应相反的\(\texttt0\)的位置奇偶性序列。子串中包含的\(\texttt0\)的位置奇偶性序列的子序列可以二分查找找到。
下面是AC代码:
#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
const int N=200000;
int n/*01串长度*/,qu/*询问次数*/;
char a[N+5];//01串
vector<int> pos;//'0'的位置序列
const int hbase1=131,hmod1=998244353,hbase2=13331,hmod2=1000000007;//哈希参数
int Hsh1[N+1],Rhsh1[N+1],hpw1[N+1],Hsh2[N+1],Rhsh2[N+1],hpw2[N+1];//Hsh:相对于1的'0'的位置奇偶性序列的前缀哈希,Rhsh:相对于2的……
void hsh_init(){//哈希预处理
hpw1[0]=hpw2[0]=1;
for(int i=1;i<=pos.size();i++)//为了前缀运算方便,哈希数组们1-indexed
Hsh1[i]=(1ll*Hsh1[i-1]*hbase1+pos[i-1]%2+1)%hmod1,
Rhsh1[i]=(1ll*Rhsh1[i-1]*hbase1+!(pos[i-1]%2)+1)%hmod1,
hpw1[i]=1ll*hpw1[i-1]*hbase1%hmod1,
Hsh2[i]=(1ll*Hsh2[i-1]*hbase2+pos[i-1]%2+1)%hmod2,
Rhsh2[i]=(1ll*Rhsh2[i-1]*hbase2+!(pos[i-1]%2)+1)%hmod2,
hpw2[i]=1ll*hpw2[i-1]*hbase2%hmod2;
}
pair<int,int> hsh(int l,int r){//pos[l-1~r-1]相对于1的奇偶性序列的哈希值
return mp(((Hsh1[r]-1ll*Hsh1[l-1]*hpw1[r-l+1]%hmod1)+hmod1)%hmod1,
((Hsh2[r]-1ll*Hsh2[l-1]*hpw2[r-l+1]%hmod2)+hmod2)%hmod2);
}
pair<int,int> rhsh(int l,int r){//pos[l-1~r-1]相对于2的奇偶性序列的哈希值
return mp(((Rhsh1[r]-1ll*Rhsh1[l-1]*hpw1[r-l+1]%hmod1)+hmod1)%hmod1,
((Rhsh2[r]-1ll*Rhsh2[l-1]*hpw2[r-l+1]%hmod2)+hmod2)%hmod2);
}
int main(){
cin>>n>>a+1>>qu;
for(int i=1;i<=n;i++)if(a[i]=='0')pos.pb(i);//预处理pos
hsh_init();//预处理哈希
while(qu--){
int l1,l2,len;
scanf("%d%d%d",&l1,&l2,&len);
int l1_0=lower_bound(pos.begin(),pos.end(),l1)-pos.begin()+1,//a[l1~l1+len-1]包含的'0'的位置奇偶性序列的左端点
r1_0=lower_bound(pos.begin(),pos.end(),l1+len)-pos.begin(),//a[l1~l1+len-1]包含的'0'的位置奇偶性序列的右端点
l2_0=lower_bound(pos.begin(),pos.end(),l2)-pos.begin()+1,//a[l2~l2+len-1]包含的'0'的位置奇偶性序列的左端点
r2_0=lower_bound(pos.begin(),pos.end(),l2+len)-pos.begin();//a[l2~l2+len-1]包含的'0'的位置奇偶性序列的右端点
pair<int,int> hsh1=l1%2?hsh(l1_0,r1_0):rhsh(l1_0,r1_0),hsh2=l2%2?hsh(l2_0,r2_0):rhsh(l2_0,r2_0);//计算哈希值
puts(hsh1==hsh2?"Yes":"No");//判断相等
}
return 0;
}
原文链接:https://www.cnblogs.com/ycx-akioi/p/CodeForces-1320D.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- CodeForces 1326E - Bombs 2020-03-25
- 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
- CodeForces 1313E Concatenation with intersection 2020-03-02
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