简单瞎搞题题解

一.闲话

~~做题历程：点开题目->发现做过->点击提交->AC (/x)~~

二.题解

明显的一道bitset的题目/x

bitset是个高级的黑科技，支持各种操作，其中最有用处的，就是bitset支持位运算。

我曾经尝试模拟了一下，貌似挺简单的，就是开个int数组，值就是当前状态状压后的值，进位就是把值传个下一个下标，直接模拟即可。

如果使用long long模拟的话，可以做到单次操作 $O(\frac{n}{64})$ ，不过不知道bitset还有没有其它玄学操作。。。

来看这道题。

我们把一个bitset看做一个支持位运算的bool数组

那么，我们设s[i]表示我们是否可以做到和为i

如果，我们求出来了之前的所有数可以做出来的各种和，现在有个数x，我们把x放进去后，可以做出的和是多少？

我们想想，如果原来我们s[i]=1,即我们原来的集合中可以做出和为i，那么，加入x后，我们是不是就可以做出i+x了？

那么，我们把对于原来数组中所有值为1的下标i，我们把i+x再赋为1就好了

于是，我们想到了左移这个位运算，我们将s这个数组的所有值左移x位，就可以做出来上面的了，但是，需要注意的是，我们不一定非要加入x,我们可能加入的是x+1..x+k各个数，也就是说，我们应该将所有情况的bitset取或。

知道这个操作后，剩下的直接模拟即可

需要注意的是，bitset的位运算的复杂度为: $O({\frac{n}{32}})$
(n为bitset的大小)

所以总复杂度为: $O(\frac{n^5}{32})$ ，可以通过此题。(当然，你用long long/unsigned long long模拟一个bitset，复杂度会小一半)

代码:

#include<bits/stdc++.h>
using namespace std;
bitset<1000001>s,p;
int main(){
    int n;
    s[0]=1;
    scanf("%d",&n);
    for(int i=1;i<=n;++i){
        int l,r;
        scanf("%d%d",&l,&r);
        p.reset();//清空p
        for(int j=l;j<=r;++j){
            p|=(s<<(j*j));
        }
        s=p;
    }
    cout<<s.count();//输出bitset里面1的个数
    return 0;
}

下面是模拟bitset代码（复杂度小了一倍，但常数挺大的所以跑得并没有想象中的快qwq）

代码:

#include<bits/stdc++.h>
using namespace std;
const int N=15628,block=64;
unsigned long long w[block];//截位
struct my_bitset{
    unsigned long long a[N];unsigned int maxe;//maxe,当前最大有值块的编号，加速用
    inline void reset(){
        for(unsigned int i=0;i<=maxe;++i){
            a[i]=0;
        }
        maxe=0;
    }
    inline unsigned int count(){//直接暴力就行
        unsigned int res=0;
        for(unsigned int i=0;i<=maxe;++i){
            for(unsigned int j=0;j<block;++j){
                res+=((a[i]>>j)&1);
            }
        }
        return res;
    }
}s,p;
inline my_bitset operator<<(my_bitset x,unsigned int y){
    unsigned int k=(y/block);y&=63;
    //大移动
    if(k){
        for(int i=x.maxe;~i;--i){
            x.a[i+k]=x.a[i];
        }
        for(int i=k-1;~i;--i){
            x.a[i]=0;
        }
        x.maxe+=k;
    }
    //小移动
    for(int i=x.maxe;~i;--i){
        unsigned long long v=(x.a[i]&w[y]);
        x.a[i]<<=y;v>>=(block-y);x.a[i+1]|=v;//faster move
    }
    if(x.maxe+1<N&&x.a[x.maxe+1]){
        ++x.maxe;
    }
    return x;
}
inline void operator|=(my_bitset &x,my_bitset y){
    x.maxe=max(x.maxe,y.maxe);
    for(int i=x.maxe;~i;--i){
        x.a[i]|=y.a[i];
    }
    return;
}
int main(){
    unsigned long long k=1;
    for(unsigned int i=1;i<block;++i){
        k<<=1;
    }
    for(unsigned int i=1;i<block;++i){
        w[i]=(w[i-1]>>1)|k;
    }
    unsigned int n;
    s.a[0]=1;s.maxe=0;
    scanf("%d",&n);
    while(n--){
        unsigned int l,r;
        scanf("%d%d",&l,&r);
        p.reset();
        for(unsigned int j=l;j<=r;++j){
            p|=(s<<(j*j));
        }
        s=p;
    }
    cout<<s.count();
    return 0;
}

简单瞎搞题 题解

一.闲话

二.题解

简单瞎搞题题解