[Contest on 2022.5.6] 手写 bitset 模板

\(\cal T_1\)

\(\mathbb{D}\rm escription\)

\(\mathbb{S}\rm olution\)

$\mathbb{C}\rm ode $

\(\cal T_2\) 基因切割

\(\mathbb{D}\rm escription\)

\(\mathbf{namespace\_std}\) 乘坐戴夫的时光机器穿越回了现代，成为了?名医学生。

这天，医院新进了一些 \(\rm dna\) 切割机，这些机器可以识别输入的 \(\rm dna\) 串中的某些子串，并将它们切割下来。

具体地，从右至左第 \(i\) 台机器上有?个识别串，右端是输入端，左端是输出端。每当在输入端投入?个碱基的时候，机器中的所有碱基会向左移动?格，若机器已满，最左侧的碱基会从机器的输出端弹出，进入左侧机器的输入端，或者完成处理后的结果池。

特别地，若?个机器内的碱基序列恰好为它的识别串，这台机器会立即把这段序列保留下来，并将自身清空。

他有?个 \(\rm dna\) 串，他将这个串放入了机器。由于整段放入机器后机器内可能会有残留的内容，所以他会在放入之后从右到左依次将每台机器残余的内容投入左侧的机器，并将最左侧机器的输出投入结果池。由于 \(\rm dna\) 切割机的运?速度很慢，他想让你写?个程序模拟切割的结果，即最终输出到结果池的 \(\rm dna\) 串。

\(|S|,m,\sum|T_i|\le 10^5\).

\(\mathbb{S}\rm olution\)

对于字符串 \(S\) 包含且仅包含字符 AT，特征串均为 AT，且将 AT 分别视为左右括号字符串 \(S\) 为合法括号序列的情况：此时可以建出括号树，那么一个节点的子树深度就代表自己在第几台机器上被剪切，所以删除所有子树深度小于等于 \(m\) 的点再进行还原就是答案。

这题可以用 \(\rm bitset\) 来做：考虑对每种字符开一个 \(\rm bitset\)，那么判断识别串的方法就是右移 \(i\) 位再取并。用 \(\text{find_next()}\) 函数找到所有的 \(1\) 的位置（识别串的开头），再依次删除即可。

原理很简单，但是我真的写了很久。

$\mathbb{C}\rm ode $

# pragma GCC optimize("Ofast")
# include 
# include 
# define print(x,y) write(x), putchar(y)

template 
inline T read(const T sample) {
    T x=0; char s; bool f=0;
    while(!isdigit(s=getchar())) f|=(s=='-');
    for(; isdigit(s); s=getchar()) x=(x<<1)+(x<<3)+(s^48);
    return f? -x: x;
}
template 
inline void write(T x) {
    static int writ[50], w_tp=0;
    if(x<0) putchar('-'), x=-x;
    do writ[++w_tp] = x-x/10*10, x/=10; while(x);
    while(putchar(writ[w_tp--]^48), w_tp);
}

# include 
using namespace std;

const int maxn = 1e5+5;

int n,m;
char str[maxn];

struct my_bitset {
    typedef unsigned int u32;
    typedef unsigned long long u64;
    const static u32 BLOCK = 64;
    const static u32 SIZE = maxn/BLOCK+((maxn%BLOCK)>0);
    u64 v[SIZE];
    inline void reset() { memset(v,0,sizeof(u64)*SIZE); }
    inline bool test(const u32& x) const {
        return v[x>>6]>>(x&63)&1;
    }
    inline void set(const u32& x) { v[x>>6] |= 1ull<<(x&63); }
    inline u32 _find_after_block(const u32& x) const {
        for(u32 i=x;i>6]>>(x&63)>>1; if(cur) 
            return u32(__builtin_ctzll(cur))+x+1;
        return _find_after_block((x>>6)+1);
    }
    inline u32 _find_first() const {
        return _find_after_block(0);
    }
    inline void operator &= (const my_bitset& rhs) {
        for(u32 i=0;i>6, z = x&63;
        if(z) for(u32 i=SIZE-1;i>y;--i)
            v[i] = (v[i-y]<>(BLOCK-z));
        else for(u32 i=SIZE-1;i>y;--i)
            v[i] = v[i-y];
        v[y] = v[0]<>= (const u32& x) {
        u32 y = x>>6, z = x&63;
        if(z) for(u32 i=0;i>z)|(v[i+y+1]<<(BLOCK-z));
        else for(u32 i=0;i>z;
        for(u32 i=SIZE-y;i>=i;
            cur &= now;
        } 
        for(int i=cur._find_first(); i^maxn; i=cur._find_next(i+len-1)) {
            now = all; now >>= (N-i+bas);
            for(int j=0;j<4;++j) {
                omg=ty[j], omg>>=i+len-bas, omg<<=i-bas;
                ty[j] &= now, ty[j] |= omg;
            }
            n -= len, bas += len;
        }
    }
    for(int i=0;i

\(\cal T_3\)

\(\mathbb{D}\rm escription\)

\(\mathbb{S}\rm olution\)

$\mathbb{C}\rm ode $
分治分块技巧-bitset

相关

标签