题解 | #简单瞎搞题#

思路：
因为数据量小，我们可以利用桶取储存每个数最终能不能被选出的方案
那么可以采用dp的方法,f[i][j]中的i表示第i层（输入给的第i行)j表示Σ(xi×xi)，我们看f[i][j]是否等于1判断j是否是存在于答案之中的
那么如果我们设l<=k<=r，状态转移方程就是f[i][j]=f[i-1][j+k×k]表示在下一层当中，上一层1的位置再加上k×k就是下一层新的1的位置
但这么做 j 是从1到1e6循环的，很明显会超时
这时候因为采取的是01串，我们可以利用bitset进行优化
因为f[i][j]=f[i-1][j+k×k]
就相当于f[i]|=f[i-1]<<(k×k)（或运算是因为之前的1也要保留，我们是利用桶存储答案，对于每个1的位置都有一个Σ(xi*xi)，最后输出最后一层的1的个数即可
AC代码:

#include <bits/stdc++.h>

using namespace std;
bitset<1000010>f[110];//桶存储方案的形式
int main()
{
    int n;
    cin>>n;
    f[0]=1;
    for(int i=1;i<=n;i++){
        int l,r;
        cin>>l>>r;
        for(int k=l;k<=r;k++){
            f[i]|=f[i-1]<<(k*k);//之前的1也要保留，新的1是前面的数加上k*k得到的数的下标的值
        }
    }
    cout<<f[n].count()<<endl;
    return 0;
}