A.数字
-
第一眼以为是数论，第二眼是 \(\mathtt{DP}\)；
-
本题又名
卡常技术综合运用，如何将 30s 的大样例卡进 10s；
Solution
-
\(\mathtt{DP+BitSet}\)；
-
如果直接 \(\mathtt{DP}\)，时间复杂度最坏会到 \(10^{10}\)，肯定过不了。这时就需要请出我们的 \(\mathtt{BitSet}\)了；
-
开一个 \(\mathtt{BitSet}\) 数组，用每一个二进制位的 \(0/1\) 来表示这个位数表示的数字能否凑出，加法用 \(\mathtt{<<}\) 可以直接解决，复杂度将原来值域的 \(10^6\) 这一层大大优化；
AC code
#include<bits/stdc++.h>
using namespace std;
inline int read(){
int s=0,f=1;
char ch=getchar();
while(!isdigit(ch)){
if(ch=='-') f=-1;
ch=getchar();
}
while(isdigit(ch)){
s=s*10+int(ch-'0');
ch=getchar();
}
return s*f;
}
const int N=105;
const int M=1e6+10;
#define re register
int n;
bitset<M>f[N];
int main(){
freopen("number.in","r",stdin);
// freopen("number.out","w",stdout);
n=read();
int a,b;
f[0].set(0);
for(int i=1;i<=n;++i){
a=read(),b=read();
for(int j=a;j<=b;++j)
f[i]|=f[i-1]<<(j*j);
}
printf("%d",f[n].count());
return 0;
}