题解-Reachable Strings

前置知识：

\(\texttt{Hash}\)

Reachable Strings

给一个长度为 \(n\) 的 \(\texttt{01}\) 串 \(s\)，可以让 \(s\) 中的 \(\texttt{110}\) 和 \(\texttt{011}\) 互相转换。\(q\) 次询问，每次给定两个 \(s\) 的子串 \(s_{l_1\sim l_1+len-1}\) 和 \(s_{l_2\sim l_2+len-1}\)，问两个串是否可以互相变换得到。

数据范围：\(1\le n,q\le 10^5\)。

哈希萌新觉得这是哈希好题。

很容易注意到 \(\texttt{11}\color{#9c3}{\texttt{0}}\leftrightarrow\color{#9c3}{\texttt{0}}\texttt{11}\) 就是 \(\texttt{0}\) 左右移动两个位置。

但是不可以 \(\texttt{10}\color{#9c3}{\texttt{0}}\leftrightarrow\color{#9c3}{\texttt{0}}\texttt{01}\) 或 \(\texttt{01}\color{#9c3}{\texttt{0}}\leftrightarrow\color{#9c3}{\texttt{0}}\texttt{10}\)，说明 \(\texttt{0}\) 移动时不能跨越别的 \(\texttt{0}\)。

综上，所有 \(\texttt{0}\) 的位置（从左往右第几个 \(\texttt{0}\)） 不会发生改变，并且下标的奇偶性不会变。

所以可以把所有 \(\texttt{0}\) 按序记录下标奇偶性生成序列，然后判断两个子序列是否可以互相变换得到可以用序列哈希对比看是否相等。

重点是因为每个子序列的起点奇偶性不都相同，所以每个 \(0\) 有两种奇偶性可能，所以用两个哈希数组。

具体实现哈希时可以用一个质数进制数来表示一个序列。

如果从高到低第 \(i\) 位为 \(1\)，就表示原字符串从左到右第 \(i\) 个 \(\texttt{0}\) 的下标为奇数；如果为 \(2\)，就表示原字符串从左到右第 \(i\) 个 \(\texttt{0}\) 的下标为偶数。

然后开前缀 \(\texttt{0}\) 序列数组 \(h\)，\(h_n\) 表示原字符串前 \(n\) 个 \(\texttt{0}\) 哈希得的质数进制数。

因为子序列的起点奇偶性不同，所以有两个 \(h\)，分别表示以起点为奇数和偶数为标准时哈希得的前缀 \(\texttt{0}\) 序列数组。

子串可以由前缀 \(\texttt{0}\) 序列数组推得，看是否可以互相变换得到只需直接比较子串。

但是有个问题：\(0\) 那么多，形成的质数进制数太大怎么办（远爆 \(\texttt{long long}\)）？

解决方法是模某个大质数（如 \(998244353\)）。虽然这样可能会把两个不同的序列哈希得一样，但这正是哈希的精髓。没有绝对正确的哈希，能解决问题的就是好哈希。

Code

#include <bits/stdc++.h>

using namespace std;

//&Start

#define inf 0x3f3f3f3f

#define re register

#define il inline

#define hash unorded_map

typedef long long lng;

typedef unsigned long long ulng;

typedef vector<int> veci;

#define fo(i,st,xb,y) for(re int i=st;i xb;i y)

//&Data

#define N 200000

#define mod 998244353 //模数为998244353

#define base 5119 //5119进制

char s[N+10];

int n,m,h[N+10][2],bs[N+10]={1},ze[N+10];

//两个h，进制前缀积，零数量前缀和

//&Main

il int Hash(re int l,re int r,re int o){return (-1ll*h[l-1][o]*bs[ze[r]-ze[l-1]]%mod+h[r][o]+mod)%mod;} //子序列哈希值

int main(){

	scanf("%d%s",&n,s+1);

	fo(i,1,<=n,++)

		if(s[i]=='1') h[i][0]=h[i-1][0],h[i][1]=h[i-1][1],ze[i]=ze[i-1];

		else h[i][0]=(1ll*h[i-1][0]*base%mod+1+(i&1))%mod,

			h[i][1]=(1ll*h[i-1][1]*base%mod+1+((i&1)^1))%mod,ze[i]=ze[i-1]+1;

	fo(i,1,<=n,++) bs[i]=1ll*bs[i-1]*base%mod;

	scanf("%d",&m); fo(i,1,<=m,++){

		re int l1,l2,len; scanf("%d%d%d",&l1,&l2,&len);

		(Hash(l1,l1+len-1,l1&1)==Hash(l2,l2+len-1,l2&1)?puts("Yes"):puts("No"));

	}

	return 0;

}

祝大家学习愉快！

巴特西

题解-Reachable Strings

题解-Reachable Strings

Code

最新文章

热门文章