简单瞎搞题
题目描述
一共有 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()); }