4465

myee · 2021-05-01 12:53:50 · 题解

引言

这题是Claris教的，说：我两三年前在bzoj做这题时，只有两个提交，一个是出题人自己交的，还有一个是交出题人代码的。

然后这道原来正解是块状链表+后缀自动机的题目被Claris用bitset暴力匹配吊打了标算。sro Claris！

shift-and算法

由于懒，用的是C++自带的std::bitset。这是道黑题，其具体用法就挂个链接了。

记 m=10。考虑到字符集只有 10 位，开 m 个bitset储存各个位置，即 std::bitset<1000005>B[10];

对于 0,1 修改操作利用位运算暴力改，复杂度大约是 O(\frac{nm} w) 的。但 0 操作还涉及增加串长度，不过这可以用插入总长度复杂度抛掉。

对于 2 查询操作则用shift-and算法，对长度为 l 的模式串C，设答案可取位对应的bitset初值为 00011111000 式的（仅对答案可能存在的 [x,y) 赋一）的p，则反复 p=(p<<1)&B[C[j]-'0'] 即可。把p左移就相当于把文本串右移。注意第一次不必左移。复杂度大约是 O(\frac{nl}w)。

Code

人傻常数大，开了O2才过。

代码轻微压行，不到1KB，比较短。

#include <bitset>
#include <stdio.h>
typedef long long llt;
typedef unsigned uint;typedef unsigned long long ullt;
typedef bool bol;typedef char chr;typedef void voi;
typedef double dbl;
std::bitset<1000005>B[10],p;chr C[1919810];
int main()
{
    uint q=0,op,num1,num2,f;scanf("%u",&q);
    while(q--)
    {
        scanf("%u%u",&op,&num1);
        if(op)
            if(op==1)
            {
                scanf("%u",&num2);
                for(uint i=0;i<10;i++)p=(B[i]>>num2)<<num2,B[i]^=((B[i]>>num1)<<num1)^(p>>(num2-num1));
            }
            else
            {
                scanf("%u%s",&num2,C),p=std::bitset<1000005>();
                for(f=0;C[f];f++);
                p=((~p)<<num1)^((~p)<<(num2-f+1));
                for(uint j=0;j<f;j++)p=(j?(p<<1):p)&B[C[j]-'0'];
                printf("%d\n",(int)p.count());
            }
        else
        {
            scanf("%s",C);
            for(f=0;C[f];f++);
            for(uint i=0;i<10;i++)p=(B[i]>>num1)<<num1,B[i]^=p^(p<<f);
            for(uint i=0;i<f;i++)B[C[i]-'0'][num1+i]=true;
        }
    }
    return 0;
}

后记

第一次写黑题题解，有所勘误恳请指出。

bitset在字符串匹配上有所应用，一般不超过 100000 且字符集较小的可以代替kmp。

Claris：这题究竟没有躲过暴力。

还是sro Claris！

END