每日一题：简单瞎搞题 （STL）

题意

一共有 $n$ 个数，第 $i$ 个数是 $x_i$ 可以取 $[l_i , r_i]$ 中任意的一个值。设 $S = \sum{ {x_i}^2}$，求 $S$ 种类数。（0 ~ n,l,r ~ 100）

Solution

$dp[i][j]$ 表示前 $i$ 个数能不能组成 $j$，可以得到转移方程：$dp[i][j]=dp[i-1][j-x^2]$，最后统计 $dp[n]$ 层组成的 $j$ 的数量即可。因为 dp 的值只有 0 和 1 ，因此使用 bitset 优化，把第二维看成二进制位，这样就可以用位移的形式来表示加法运算，得到转移方程：dp[i]=dp[i-1] << (j*j)，复杂度 $10^{10}/64$。

Code

#include <bits/stdc++.h>
using namespace std;
bitset<1000005> dp[105];
int main() {
  int n, l, r;
  scanf("%d", &n);
  dp[0][0] = 1;
  for (int i = 1; i <= n; i++) {
    scanf("%d%d", &l, &r);
    for (int j = l; j <= r; j++) dp[i] |= dp[i - 1] << (j * j);
  }
  printf("%lu\n", dp[n].count());
  return 0;
}