diyiti.cpp

diyiti.cpp/c/pas diyiti.in diyiti.out 2s/256MB

给定两个01串，S,T(下标从0开始）。

支持如下3种操作：

1. 修改S第i位的字符，即0->1,1->0.

2. 修改T第i位的字符，即0->1,1->0.

3. 查询S[a..a+l-1],T[b..b+l-1]的相似度。

相似度定义如下:

s,t两个字符串的相似度=sigma_{i=0}^{|s|-1} sim(s[i],t[i])

sim(a,b) 有四个参数p_{0,0},p_{0,1},p_{1,0},p_{1,1}。 sim(a,b)的返回值为p_{a,b}。

input

第一行一个非空字符串S

第二行一个非空字符串T

第三行一个操作个数Q

接下来Q行，每行为"1 i","2 i"或"3 a b l p_{0,0} p_{0,1} p_{1,0} p_{1,1}"

output

若干行，每行对应每个3操作的答案。

sample in

sample out

10%, |S|,|T|<=1000,Q<=1000
10%, |S|,|T|<=50000,Q<=50000,3操作的p值都为1
10%, |S|,|T|<=50000,Q<=50000,所有操作为3操作且a,b,l相同
20%, |S|,|T|<=50000,Q<=50000,3操作的a,b值为0
50%, |S|,|T|<=100000,Q<=100000,0<=p<=50,由于数据随机生成，可以默认3操作l的期望为|S|/6

压位。。

# include <iostream>

# include <cstdio>

# include <iostream>

# include <cstring>

using namespace std;

const int MAXN=,bit=;

typedef long long ll;

ll a[MAXN],b[MAXN],f1[MAXN],f2[MAXN],f[MAXN];

int len1,len2;

char s[MAXN],pp[MAXN];

void work1()

{

    int x; scanf("%d",&x); x++;

    a[x]=a[x] ^ ;

    for (int i=max(,x-bit);i<=min(x,len1-bit);i++)

        f1[i]=f1[i] ^ (<<(x-i));

}

void work2()

{

    int x; scanf("%d",&x); x++;

    b[x]=b[x] ^ ;

    for (int i=max(,x-bit);i<=min(x,len2-bit);i++)

        f2[i]=f2[i] ^ (<<(x-i));

}

void work3()

{

    int al,bl,len,p1,p2,p3,p4;

    scanf("%d%d%d%d%d%d%d",&al,&bl,&len,&p1,&p2,&p3,&p4);

    int ans=;

    al++; bl++;

    for (int i=;i<=len/(bit+);i++) {

      ans=ans+f[(f1[al] ^ ((<<(bit+))-))&(f2[bl] ^ ((<<(bit+))-))]*p1;//0 0

      ans=ans+f[(f1[al] ^ ((<<(bit+))-))&f2[bl]]*p2; //0 1

      ans=ans+f[f1[al] & (f2[bl] ^ ((<<(bit+))-))]*p3;// 1 0

      ans=ans+f[f1[al] & f2[bl]]*p4;// 1 1

      al=al+(bit+); bl=bl+(bit+);

    }

    //最后一个压位后的数

    for (int i=;i<=len%(bit+)-;i++) {

      if ((a[i+al]==)&&(b[i+bl]==)) ans=ans+p1;

      if ((a[i+al]==)&&(b[i+bl]==)) ans=ans+p2;

      if ((a[i+al]==)&&(b[i+bl]==)) ans=ans+p3;

      if ((a[i+al]==)&&(b[i+bl]==)) ans=ans+p4;

    }

    printf("%d\n",ans);

}

int main()

{

    freopen("diyiti.in","r",stdin);

    freopen("diyiti.out","w",stdout);

    for (int i=;i<=<<(bit+)-;i++)

    {

        int x=i;

        while(x>) {

            f[i]=f[i]+;//数i有几个1

            x=x & (x-);

        }

    }

    //for (int i=0;i<=20;i++) printf("%d %d\n",i,f[i]);

    cin>>s;

    for (int i=;i<=strlen(s);i++) pp[i+]=s[i];

    len1=strlen(s);

    for (int i=;i<=len1;i++) s[i]=pp[i];

    for (int i=;i<=len1;i++) a[i]=s[i]-''; //a表示一个大二进制数A

    cin>>s;

    for (int i=;i<=strlen(s);i++) pp[i+]=s[i];

    len2=strlen(s);

    for (int i=;i<=len2;i++) s[i]=pp[i];

    for (int i=;i<=len2;i++) b[i]=s[i]-'';  //b表示一个大二进制数B

    for (int i=;i<=len1-bit;i++)

     for (int j=;j<=bit;j++)

      f1[i]=f1[i]+a[i+j]<<j; //A每bit位压成一个整数 f1

    for (int i=;i<=len2-bit;i++)

     for (int j=;j<=bit;j++)

      f2[i]=f2[i]+b[i+j]<<j; //B每bit位压成一个整数 f2

    int q;  scanf("%d",&q);

    while (q)

    {

        int ch; scanf("%d",&ch);

        if (ch==) work1();

        else if (ch==) work2();

        else if (ch==) work3();

        q--;

    }

    return ;

    fclose(stdin); fclose(stdout);

}