牛客 简单瞎搞题 bitset 01dp

牛客 简单瞎搞题 //bitsert 01dp

题目描述

一共有 n个数，第 i 个数是 xi 

xi 可以取 [li , ri] 中任意的一个值。

设 S=∑xi2S=∑xi2，求 S 种类数。

输入描述:

第一行一个数 n。  然后 n 行，每行两个数表示 li,ri。

输出描述:

输出一行一个数表示答案。

如果是dp，定义dp[i][j] 第n行，s为j是否有这个状态。以下超时代码：

#include<bits/stdc++.h> using namespace std; #define LL long long const LL mod = 1000000007; const int MX = 1e3+1; bool dp[101][100*100*100+1]; int main(){ int n;scanf("%d",&n); dp[0][0]=1; for(int i=1;i<=n;i++){ int l,r;scanf("%d%d",&l,&r); for(int j=l;j<=r;j++){ for(int k=0;k<=1e6;k++) if(k-j*j>=0) dp[i][k]|=dp[i-1][k-j*j]; } }int ans=0; for(int k=0;k<=1e6;k++) if(dp[n][k]) ans++; printf("%d",ans); return 0; }

biset类似01背包优化，复杂度/64，O(1e10/64)可过，

bitset用于优化dp一般存在于01dp，一般也可以用到滚动数组的思想，一位代表一个数（状态）是否存在，左右移即可加减。

correct代码：

#include<bits/stdc++.h> using namespace std; #define LL long long const LL mod = 1000000007; const int MX = 1e3+1; bitset<100*100*100+1>ans,t; int main(){ int n;scanf("%d",&n); ans[0]=1; while(n--){ t.reset(); int l,r;scanf("%d%d",&l,&r); while(l<=r){ t|=ans<<(l*l);l++; } ans=t; } printf("%d",ans.count()); return 0; }