头部背景图片
Decaku 's Blog |
Decaku 's Blog |

牛客练习赛22-C简单瞎搞题 bitset+dp

描述:

给出$n$个区间,然后分别给出区间的左右边界,可以在每个区间中选择一个整数,问这$n$个整数的平方和有多少种不同的取值。


思路:

$ f_i $表示一个bitset,bitset里有几个1,就表示这i个区间所能得到的平方和的取值种数。

转移方程为 f[i]=f[i] | f[i-1]<<k^k (k from l to r)

状态转移的复杂度是n,每次操作对应的复杂度是l-r。


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <iostream>
#include<cstdio>
#include<stdio.h>
#include<bitset>

using namespace std;

bitset<1000000+10>f[105];

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

return 0;
}
avatar Decaku 很菜但也很想carry