题意

• 有n个区间，从每个区间中取一个值求 的种数

思路

• 分组背包，考虑前i组能不能凑出j，，其中k属于a[i]
• 双层枚举i,j,对于每一个j枚举区间，O(100*1000000*100)=O(1e10),过不了一点

   for(int i=1;i<=n;i++){
       for(int j=1;j<1e6;j++){
           for(int k=a[i].first;k<=a[i].second;k++){
               dp[i][j]=dp[i-1][j-k*k]
           }
       }
   }

• 使用bitset优化

bitset

• 定义：bitset<大小>

• 方法：

  count():返回其中1的个数

  all():是否全1

  none():是否空

  any()：是否有

  reset():给某一位赋0,如果不填参数就是清空

  set(pos,val):给某一位赋val,如果不填参数就是全赋1

  flip():取反某一位，如果不填参数就是对整个串取反

  to_ullong():转ull

  to_string():转string

AC代码

#include<bits/stdc++.h>
#define pii pair<int,int>
using namespace std;
const int N = 1e6+10;
pii a[120];
bitset<N> dp[120];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    for(int i=1;i<=n;i++){
        cin >> a[i].first >>a[i].second;
    }
    dp[0][0]=1;
    for(int i=1;i<=n;i++){
        for(int j=a[i].first;j<=a[i].second;j++){
            dp[i]|=(dp[i-1]<<(j*j));
        }
    }
    cout << dp[n].count() << '\n';
    return 0;
}