简单瞎搞题

题目描述

一共有 n个数，第 i 个数是 xi
xi 可以取 [li , ri] 中任意的一个值。，求 S 种类数。
0<=li<=ri<=100

思路

由于li,ri，n范围只有100 显然可以暴力扫描所有区间中的每个值 然后dp
dp[i][S] 表示 1~i个数能否组成S，但是我们发现这样的复杂度为 100100100*100 = 1e8 似乎时间有点紧张。
在仔细想想其实发现dp数组只表示 0 / 1 两种状态，那么直接 利用 bitset类似状压优化就可以了

代码

#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define ls rt<<1
#define rs rt<<1|1
#define fi first
#define se second
#define pb push_back
using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const  ll inf  = 0x3f3f3f3f;
const int mod  = 1e9 + 7;
const int maxn = 1e6 + 6;
const int N    = 5e3 + 4;
const double eps = 1e-6;
ll qpow(ll x,ll y){ll ans=1;x%=mod; while(y){ if(y&1) ans=ans*x%mod; x=x*x%mod; y>>=1;}return ans;}

int n,ans,l[maxn],r[maxn];
bitset<maxn>bt;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d%d",&l[i],&r[i]);
    bt[0]=1;
    for(int i=1;i<=n;i++){
        bitset<maxn> bb;bb.reset();
        for(int j=r[i];j>=l[i];j--){
            bb|=(bt<<(j*j));
        }
        bt=bb;
    }
    printf("%d\n",bt.count());
}