洛谷题目页面传送门 & codeforces题目页面传送门
有一个01串(a,|a|=n)。(q)次询问,每次给出(l1,l2,len),问(a_{l1sim l1+len-1},a_{l2sim l2+len-1})这(2)个01串是否能通过若干次操作变得相等,其中一次操作指的是将任意一个01串的任意一个等于(texttt{110})的子串变成(texttt{011})或将(texttt{011})变成(texttt{110})。
(n,qinleft[1,2times10^5right])。
考虑分析能通过若干次操作变得相等的充要条件。
不难发现,每次操作都不可能改变01串中(texttt0)和(texttt1)分别的数量,所以(2)个01串中(texttt0)和(texttt1)的数量分别相等是能通过若干次操作变得相等的必要条件,但充分性还远远不够。
又发现,(texttt{110}leftrightarrowtexttt{011})这个操作比较有意思,它相当于将这个唯一的(texttt{0})向左/右推了(2)位。由于这是个01串,非(texttt0)即(texttt1),于是我们将所有(texttt0)的位置揪出来,其他位置自然是(texttt1)。
不难发现,01串中所有(texttt0)对的相对位置都不会改变。证明:若(2)个(texttt0)想要交换位置,那么交换前最后一刻的状态一定是距离差(leq2),此时左边的(texttt0)不能通过(texttt{011}totexttt{110})往右再移(2)格,因为它右边(1sim2)格是右边的(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(xgeq1))个(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; }
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/600150.html