牛客 132C 简单瞎搞题 (bitset)

大意: 给定序列$a$的第$i$个元素的取值范围$[L_i,R_i]$, 求$a$的平方和的种类数.

用bitset优化, 复杂度$O(\frac{n^5}{\omega})$

#include <iostream>

#include <algorithm>

#include <cstdio>

#include <bitset>

#define REP(i,a,n) for(int i=a;i<=n;++i)

using namespace std;

const int N = 1e6+10;

int n, a[N];

bitset<N> ans, t;

int main() {

	scanf("%d", &n);

	ans[0] = 1;

	REP(i,1,n) {

		int l, r;

		scanf("%d%d", &l, &r);

		t.reset();

		REP(j,l,r) t |= ans<<(j*j);

		ans = t;

	}

	printf("%d\n", (int)ans.count());

}

巴特西

牛客 132C 简单瞎搞题 (bitset)

最新文章

热门文章