vectorwyx 的博客

vectorwyx 的博客

My left brain has nothing right, my right brain has nothing left.

题解 CF1320D 【Reachable Strings】

posted on 2021-01-01 21:29:35 | under 题解 |

相当不错的思维题。

注意到 $110→011$ 和 $011→110$ 相当于把 $0$ 左移或右移两位,且移动的过程中不能跨越某个 $0$。(关键点 $1$

这意味着 $0$ 的相对方位不会发生改变(关键点 $2$),两个子串 $s1$ 和 $s2$ 如果相互可达,那么 $s1$ 里的 $0$ 与 $s2$ 里的 $0$ 的对应关系一定是唯一确定的—— $s1$ 的第一个 $0$ 与 $s2$ 的第一个 $0$ 对应, $s1$ 的第二个 $0$ 与 $s2$ 的第二个 $0$ 对应……所以 $s1$ 与 $s2$ 是否相互可达也就只与它们所含的 $0$ 的数量和 $0$ 的下标的奇偶性有关(关键点 $3$)。

首先,如果 $0$ 的数量不一致,那么答案肯定为no。其次,如果 $s1$ 和 $s2$ 中所对应的 $0$ 的下标的奇偶性不同,那么答案肯定也为no,因为每个 $0$ 的下标的变化量只能为偶数(关键点 $4$)。故而,我们可以将给定的字符串 $s$ 所含的所有 $0$ 的下标都放到一个单独的字符串 $a$ 里,把奇数赋为 $1$,偶数赋为 $0$。那么问题就变成了判断 $a$ 中的两个子串是否相等,这个过程可以用哈希来实现(关键点 $5$)。

注意,由于得到的 $a$ 数组中存储的01值是由相对于原字符串 $s$ 而言的“绝对下标”得到的,而我们实际上要判断的是相对于所询问子串的“相对下标”,因此询问时的某段子串的01值可能会与 $a$ 中的01值截然相反,处理一下就好了(关键点 $6$)。


代码如下qwq:

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#define mod1 998244353
#define mod2 1000000007
#define base1 3
#define base2 101
#define ll long long
#define fo(i,x,y) for(int i=x;i<=y;++i)
#define go(i,x,y) for(int i=x;i>=y;--i)
using namespace std;
inline int read(){ int x=0,fh=1; char ch=getchar(); while(!isdigit(ch)){ if(ch=='-') fh=-1; ch=getchar(); } while(isdigit(ch)){ x=(x<<1)+(x<<3)+ch-'0'; ch=getchar(); } return x*fh; }

const int N=2e5+5;
char s[N];
int n,pw1[N],pw2[N],hx1[N],hx2[N],a[N],top,_hx1[N],_hx2[N];

void hash_(){
    pw1[0]=pw2[0]=1;
    fo(i,1,top) pw1[i]=1ll*pw1[i-1]*base1%mod1,pw2[i]=1ll*pw2[i-1]*base2%mod2;
    fo(i,1,top){
        hx1[i]=hx1[i-1];hx2[i]=hx2[i-1];_hx1[i]=_hx1[i-1];_hx2[i]=_hx2[i-1];
        if(a[i]&1) hx1[i]=(hx1[i]+pw1[i-1])%mod1,hx2[i]=(hx2[i]+pw2[i-1])%mod2;
        else _hx1[i]=(_hx1[i-1]+pw1[i-1])%mod1,_hx2[i]=(_hx2[i]+pw2[i-1])%mod2;
    }
}

bool check(){
    int l1=read(),l2=read(),len=read();
    bool flag=(l1&1)^(l2&1);
    if(l1>l2) swap(l1,l2);
    int r1=l1+len-1,r2=l2+len-1;
    int L1=lower_bound(a+1,a+1+top,l1)-a,R1=upper_bound(a+1,a+1+top,r1)-a-1;
    int L2=lower_bound(a+1,a+1+top,l2)-a,R2=upper_bound(a+1,a+1+top,r2)-a-1;
    if(R1-L1!=R2-L2) return 0;
    if(R1-L1==-1) return 1;
    int v1,v2;
    if(flag) v1=(0ll+_hx1[R1]+mod1-_hx1[L1-1])*pw1[L2-L1]%mod1;
    else v1=(0ll+hx1[R1]+mod1-hx1[L1-1])*pw1[L2-L1]%mod1;
    v2=(0ll+hx1[R2]+mod1-hx1[L2-1])%mod1;
    if(v1!=v2) return 0;
    if(flag) v1=(0ll+_hx2[R1]+mod2-_hx2[L1-1])*pw2[L2-L1]%mod2;
    else v1=(0ll+hx2[R1]+mod2-hx2[L1-1])*pw2[L2-L1]%mod2;
    v2=(0ll+hx2[R2]+mod2-hx2[L2-1])%mod2;
    return v1==v2;
}

int main(){
    n=read();
    scanf("%s",s+1);
    fo(i,1,n) if(s[i]=='0') a[++top]=i;
    hash_();
    int q=read();
    while(q--) puts(check()?"Yes":"No");
    return 0;
}

点个赞再走呗/kel