Question

一共有个数，第 个数是 ，可以取 中任意的一个值。设 ，求 种类数。

Soltuion

分组背包一共有组，这道题难点在于数据的压缩要用到bitset，这是我第一次接触bitset，推荐一篇介绍bitset的博客。

表示可以被构造出来，表示可以被构造出来，最后可以构造的种类就是中1的个数。

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
const double eps = 1e-8;
const int NINF = 0xc0c0c0c0;
const int INF  = 0x3f3f3f3f;
const ll  mod  = 1e9 + 7;
const ll  maxn = 1e6 + 5;
const int N = 100 +5;

int n,L,R;
bitset<maxn>a,b;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n;
    b[0]=1;
    for(int i=1;i<=n;i++){
        cin>>L>>R;
        for(int j=L;j<=R;j++) a|=b<<(j*j);
        b=a;
        a.reset();
    }
    cout<<b.count()<<'\n';
    return 0;
}