[原创]「LibreOJ β Round #2」贪心只能过样例 [bitset]【STL】

2017-07-03 14:51:58 Tabris_ 阅读数：987

博客爬取于2020-06-14 22:39:49
以下为正文

版权声明：本文为Tabris原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/74198393

题目链接:https://loj.ac/problem/515
——————————————————————————————————

515. 「LibreOJ β Round #2」贪心只能过样例

内存限制：256 MiB 时间限制：1000 ms
标准输入输出
题目类型：传统
评测方式：文本比较
上传者： nzhtl1477

题目描述

一共有 $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 \le n , a_i , b_i \le 100$
——————————————————————————————————
其实这个题目很好想,

显然S的范围在 $[1,10^6]$ ,

我们用一个数组标记一下那个位置的值存在,然后就好了

过程很简但维护一下即可,
但是复杂度是 $O(\sum_{i=1}^{n}\{b_i-a_i\}\times 10^6)$

然后当时采取了用两个栈+一个标记数组维护的想法应该能去掉很多空状态,

写了一发但是还是TLE了

最后听说是用bitset这种东西来维护

bitset

其实就是一个可定义长度的01集合

经过内部算法优化了时间和空间复杂度

可以当成一个可变长度的整形来用

支持整形位运算符

本题就一样
将 $x^2$ 用 $1<<(x^2)$ 来标记

将 $x^2+y^2$ 用 $1<<(x^2+y^2)$ 来标记

很容易证明它的正确性

附本题代码
——————————————————————————————————

# include <bits/stdc++.h>
typedef long long int LL;
using namespace std;
# define abs(x) ((x)>0?(x):-(x))
# define rep(x,a,b) for(int x=(a),end=(b);x<=end;x++)

const int N   = 1e4+7;
const int MOD = 1e9+7;
/*****************************************************************/
int n;

bitset<1010101>f[2];
int main(){
    scanf("%d",&n);
    f[0][0]=1;
    for(int i=1,l,r;i<=n;i++){
        scanf("%d%d",&l,&r);
        rep(j,l,r) f[i&1] |= f[!(i&1)] << (j*j);
        f[!(i&1)].reset();
    }
    printf("%d\n",f[(n&1)].count());
    return 0;
}