solution
用表示前k个区间能(1)不能(0)组成这个数字。然后枚举一下第个区间所选的数字x,就有转移
最后数一下有多少数字可以被组成就行了。
但是这样复杂度爆炸,发现f的值只有和所以可以用进行优化,复杂度
code
/* * @Author: wxyww * @Date: 2020-05-19 14:37:41 * @Last Modified time: 2020-05-19 14:46:32 */ #include<cstdio> #include<iostream> #include<cstdlib> #include<cstring> #include<algorithm> #include<queue> #include<vector> #include<ctime> #include<cmath> #include<bitset> using namespace std; typedef long long ll; bitset<1000010>B,tmp,k; ll read() { ll x = 0,f = 1;char c = getchar(); while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar(); } while(c >= '0' && c <= '9') { x = x * 10 + c - '0'; c = getchar(); } return x * f; } int main() { int n = read(); B[0] = 1; for(int i = 1;i <= n;++i) { int l = read(),r = read(); tmp = B; B = k; for(int j = l;j <= r;++j) { B |= tmp << (j * j); } } int cnt = 0; for(int i = 0;i <= 1000000;++i) if(B[i]) cnt++; cout<<cnt; return 0; }