简单瞎搞题（biset优化+滚动数组）
简单瞎搞题
https://ac.nowcoder.com/acm/problem/17193
up
5
1 2
2 3
3 4
4 5
5 6
down
26
此题用到了biset，简单提一下吧：
bitset<4> bitset1; //无参构造，长度为４，默认每一位为０ bitset<8> bitset2(12); //长度为８，二进制保存，前面用０补充 string s = "100101"; bitset<10> bitset3(s); //长度为10，前面用０补充 char s2[] = "10101"; bitset<13> bitset4(s2); //长度为13，前面用０补充 cout << bitset1 << endl; //0000 cout << bitset2 << endl; //00001100 cout << bitset3 << endl; //0000100101 cout << bitset4 << endl; //0000000010101
0<=n,l,r<=100; 所以biset要开到1e6，因为n个区间里面的值会有大量重复，暴力的话必然会超时，这时就用betset加一个数就相当于左移该数几位，然后与运算最后求biset中的1个数就ok啦，下面看代码吧：
#include<queue>
#include<bitset>
using namespace std;
int a[500],b[500];
int dp[500][500];
const int MAXN=1e6+10;
bitset<MAXN> ans,tmp; //tmp用作存储中间状态的值
int main()
{
int n;
cin>>n;
for(int i=0;i<n;i++){
cin>>a[i]>>b[i];
}
ans[0]=1;//ans0位为1
for(int j=0;j<n;j++){
tmp.reset(); //把tmp中所有位清0
for(int i=a[j];i<=b[j];i++){
tmp|=ans<<(i*i); //左移i*i位
}
ans=tmp;
}
cout<<ans.count()<<endl;//计算ans中1的位数
return 0;
}
查看30道真题和解析