【每日一题】简单瞎搞题

心态炸了不小心关掉又要重新写

Description

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

Solution

这个问题的难点在于如何统计出所有和可能出现的情况，并且不能重复。
很容易想到用桶去存储每一个数，即某个和能够组合出来则为1，否则为0
不妨令 $dp[i][j]$ 表示为第 $i$ 次选择时，和为 $j$ 的情况是否出现过
但是内存方面需要 $1e8$ 的 $int$ 内存，显然是不可接受的
那么我们考虑用 $bitset$ 优化一下，有递推方程 $dp[i] = (dp[i] |= (dp[i - 1] << (j * j))$
代表第 $i$ 次选择的时候是否能从当前状态转移到和为 $j$ 的状态

Code

#include<bits/stdc++.h>

typedef long long ll;

using namespace std;

const ll mod = 1e9 + 7;
const int N = 2e5 + 5;
bitset<100 * 100 * 100 + 5> dp[105];
int main() {
  int n;
  cin >> n;
  dp[0][0] = 1;
  for(int i = 1; i <= n; i++) {
    int l, r;
    cin >> l >> r;
    for(int j = l; j <= r; j++) {
      dp[i] |= (dp[i - 1] << (j * j));
    }
  }
  cout << dp[n].count() << "\n";
  return 0;
}

当然, 我们发现, $dp[i]$ 只会和 $dp[i - 1]$ 有关, 可以用滚动数组继续优化一些内存

Code

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

const long long inf = 1e18;
const int N = 1e5 + 5;
const double eps = 1e-10;
const ll mod = 1e9 + 7;

int a[N];
bitset<1000005> now, nxt;
int main() {
  ios::sync_with_stdio(false), cin.tie(nullptr);
  now[0] = 1;
  int n;
  cin >> n;
  for(int i = 1; i <= n; i++) {
    int l, r;
    cin >> l >> r;
    for(int j = l; j <= r; j++) {
      if(j == l) nxt = (now << (j * j));
      else nxt |= (now << (j * j));
    }
    now = nxt;
  }
  cout << now.count() << "\n";
}
// 2 3 1 5 4