题目大意

给定一个01序列的生产方法。给定一个长度为的01序列,问能够在A序列中匹配多少次。

题解

因为,所以一一对应。
根据给定的01序列第位的情况,我们可以容易推知第1位需要落在那个区间内才能保证第位匹配。这样能得到个非法的开头区间。
同时序列的位开始无法长度不够,也无法作为开头。
得到所有的非法区间,用扫描线得到答案即可。

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#define LL long long
using namespace std;

const int Maxn=1e6;

int N,A,B,P;
char str[Maxn+5];
int len;

struct Segment{
    int l,r;
    Segment(){}
    Segment(int l0,int r0):l(l0),r(r0){}
}s[Maxn*4+5];
int tot;

void plusSegment(int l,int r){
    //printf("%d %d\n",l,r);
    if (l>r){
        s[++tot]=Segment(0,r);
        s[++tot]=Segment(l,N-1);
    }else s[++tot]=Segment(l,r);
}

int read(char str[]){
    int len=0;
    char x=getchar();
    while(!('0'<=x && x<='1')) x=getchar();
    while('0'<=x && x<='1'){
        str[len++]=x;
        x=getchar();
    }
    return len;
}

inline bool cmp(Segment a,Segment b){
    if (a.l!=b.l) return a.l<b.l;
    return a.r>b.r;
}

int main(){
    //freopen("in.txt","r",stdin);

    scanf("%d%d%d%d%d",&N,&A,&B,&P,&len);
    len=read(str);

    tot=0;
    for (int i=0,now=0;i<len;i++){
        //printf("%c\n",str[i]);
        if (str[i]=='1'){
            plusSegment(now,(now+P-1)%N);
        }else plusSegment((now+P)%N,(now-1+N)%N);
        if (now-A<0) now=now-A+N; else now-=A;
    }
    for (int i=N-len+1,now=((LL)i*A+B)%N;i<N;i++){
        plusSegment(now,now);
        if (now+A>=N) now=now+A-N; else now+=A;
    }

    sort(s+1,s+tot+1,cmp);

    int ans=0;
    for (int i=1,now,lim;i<=tot;i++){
        now=s[i].l; lim=s[i].r;
        while((i+1)<=tot && s[i+1].l<=lim){
            i++;
            lim=max(lim,s[i].r);
        }
        //printf("%d %d\n",now,lim);
        ans+=lim-now+1;
    }


    printf("%d\n",N-ans);
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注