简单瞎搞题

思路

简单瞎搞题就瞎搞就好了
看到这题我是想dp的，很明显 dp[ i ]表示 能不能加到i这个值
状态转移方程就是

    dp[0] = true;
    for(int i = 0 ; i < n ; ++i){
        srt<int> q;
        for(int j = l[i] ; j <= r[i] ; ++j){
                int tmp = j*j;
            for(int k = tmp ; k <= maxn ; ++k){
                if(dp[k - tmp]) q.insert(k);//用一个变量存前i个数能到达的位置，防止多计算
            }
        }
        auto it = q.begin();
        while(it != q.end()){
            dp[*it] = true;
            ++it;
        }
    }

代码很好理解我就不多说了
来算算复杂度吧，maxn的最大值是 n * r[i]^2 = 100 * 100 * 100 = 1e6
所以总的复杂度就是1e6 * 100 * 100 = 1e10肯定是超时的。

那肯定是要换一种办法，因为这里知道dp只有两种状态，0 or 1 一般情况这种单一状态状态压缩动态规划的可以通过STL中的bitset去优化。
比如 11001 表示 1 4 5 可以用加法得到，因为 位置1 4 5上的数为1
总结一下，bitset的第X位为1表示整数X可以通过加法得到。
同时这里需要一个额外的变量保存上一个xi加完后能到达的值，不然会出现一些不能到达的值。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

inline ll read(){
    ll s = 0, w = 1; char ch = getchar();
    while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); }
    while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s * w;
}
bitset<1000005>q,tmp;
int main(){
    int n = read();
    int l = read(),r = read();
    for(int i = l ; i <= r ; ++i) q[i*i]=1;
    while(--n){
        l = read();r = read();
        tmp.reset();
        for(int i = l; i <= r; ++i) tmp |= q<<(i*i);
        q = tmp;
    }
    int ans = 0;
    for(int i = 1; i <= 1000000;i++)
        if(q[i]) ++ans;
    printf("%d\n",ans);
    return 0;
}