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

1010
0101
6
3 0 0 4 1 2 3 4
1 1
3 0 1 3 4 3 7 6
2 2
3 1 0 2 4 5 3 4
3 1 0 3 8 8 8 8

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=1000005,bit=15;
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] ^ 1;
    for (int i=max(1,x-bit);i<=min(x,len1-bit);i++) 
        f1[i]=f1[i] ^ (1<<(x-i)); 
}
void work2()
{
    int x; scanf("%d",&x); x++;
    b[x]=b[x] ^ 1;
    for (int i=max(1,x-bit);i<=min(x,len2-bit);i++) 
        f2[i]=f2[i] ^ (1<<(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=0;
    al++; bl++;
    for (int i=1;i<=len/(bit+1);i++) {
      ans=ans+f[(f1[al] ^ ((1<<(bit+1))-1))&(f2[bl] ^ ((1<<(bit+1))-1))]*p1;//0 0
      ans=ans+f[(f1[al] ^ ((1<<(bit+1))-1))&f2[bl]]*p2; //0 1
      ans=ans+f[f1[al] & (f2[bl] ^ ((1<<(bit+1))-1))]*p3;// 1 0
      ans=ans+f[f1[al] & f2[bl]]*p4;// 1 1
      al=al+(bit+1); bl=bl+(bit+1);
    }
    //最后一个压位后的数 
    for (int i=0;i<=len%(bit+1)-1;i++) {
      if ((a[i+al]==0)&&(b[i+bl]==0)) ans=ans+p1;
      if ((a[i+al]==0)&&(b[i+bl]==1)) ans=ans+p2;
      if ((a[i+al]==1)&&(b[i+bl]==0)) ans=ans+p3;
      if ((a[i+al]==1)&&(b[i+bl]==1)) ans=ans+p4;
    }
    printf("%d
",ans);
}
int main()
{
    freopen("diyiti.in","r",stdin);
    freopen("diyiti.out","w",stdout);
    for (int i=0;i<=1<<(bit+1)-1;i++)
    {
        int x=i;
        while(x>0) {
            f[i]=f[i]+1;//数i有几个1 
            x=x & (x-1);
        }
    }
    //for (int i=0;i<=20;i++) printf("%d %d
",i,f[i]);
    cin>>s;
    for (int i=0;i<=strlen(s);i++) pp[i+1]=s[i];    
    len1=strlen(s);
    for (int i=1;i<=len1;i++) s[i]=pp[i];
    for (int i=1;i<=len1;i++) a[i]=s[i]-'0'; //a表示一个大二进制数A 
    
    cin>>s;
    for (int i=0;i<=strlen(s);i++) pp[i+1]=s[i];    
    len2=strlen(s);
    for (int i=1;i<=len2;i++) s[i]=pp[i];
    for (int i=1;i<=len2;i++) b[i]=s[i]-'0';  //b表示一个大二进制数B 

    for (int i=1;i<=len1-bit;i++)
     for (int j=0;j<=bit;j++)
      f1[i]=f1[i]+a[i+j]<<j; //A每bit位压成一个整数 f1 
    for (int i=1;i<=len2-bit;i++)
     for (int j=0;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==1) work1();
        else if (ch==2) work2();
        else if (ch==3) work3();
        q--;
    }  
    return 0;
    fclose(stdin); fclose(stdout);
}