洛谷題目頁面傳送門 & 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.uj5u.com/houduan/52942.html
標籤：C++