[LOJ#515]「LibreOJ β Round #2」贪心只能过样例

试题描述

一共有 \(n\) 个数，第 \(i\) 个数 \(x_i\) 可以取 \([a_i , b_i]\) 中任意值。

设 \(S=\sum{x_i^2}​​\) ，求 \(S\) 种类数。

输入

第一行一个数 \(n\)。

然后 \(n\) 行，每行两个数表示 \(a_i, b_i\)。

输出

输出一行一个数表示答案。

输入示例

5

1 2

2 3

3 4

4 5

5 6

输出示例

26

数据规模及约定

\(1 \leq n, a_i, b_i \leq 100\)

题解

分析一下复杂度发现可以上 bitset。。。

偶然发现这是博客中第一道 bitset 的题。。。

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <algorithm>

#include <bitset>

using namespace std;

int read() {

	int x = 0, f = 1; char c = getchar();

	while(!isdigit(c)){ if(c == '-') f = -1; c = getchar(); }

	while(isdigit(c)){ x = x * 10 + c - '0'; c = getchar(); }

	return x * f;

}

#define maxn 1000001

bitset <maxn> f, g;

int main() {

	f[0] = 1;

	int q = read();

	while(q--) {

		int l = read(), r = read();

		for(int i = l; i <= r; i++)

			if(i == l) g = f << i * i;

			else g |= f << i * i;

		f = g;

	}

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

	return 0;

}