【牛客练习赛22 C】

https://www.nowcoder.com/acm/contest/132/C

题目大意:在n个区间中取出n个数,相加的和一共会出现多少种结果。

题目分析:对于这种挑选数字相加,由于每一步不同的选择都会影响结果,并且会出现重复的结果,所以很自然地想到使用bitset进行解决..

    【基本操作:使用<<a给每个结果加上a,使用 | (1<<a) 添加一个结果】

【注意使用bitset不会爆位数..而使用(1<<a)的过程可能爆掉..在该题中就爆掉了..可以使用构建新的bitset先 << 再与 原 bitset进行 | 操作】

 #include<bits/stdc++.h>
using namespace std;
int main()
{
bitset<>fo();
bitset<>fo1();
bitset<>fo2();
bitset<>fo3();
int n;
scanf("%d",&n);
int tot=;
for(int i = ; i < n ; i++){
int qwq1,qwq2;
scanf("%d%d",&qwq1,&qwq2);
fo2=fo1;
fo1=fo3;
for(int j = qwq1 ; j <= qwq2 ; j++){
fo=fo2;
bitset<>fo4();
if(i)
fo<<=(j*j);
else{
fo4<<=(j*j);
fo|=fo4;
}
fo1|=fo; } /*for(int k = 0 ; k <= 1000000 ; k++){
if((fo1[k])&(1)){tot++;cout << k <<endl;}*/ } for(int i = ; i <= ; i++){
if(fo1[i]&){tot++;}
}
cout << tot << endl;
return ;
}
上一篇:webapi中使用Route标签


下一篇:AcWing250 磁力块(分块)