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

Tabris

CSDNSTL思维

发布于：2017年7月3日

次浏览

[原创]「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)$ 来标记

很容易证明它的正确性

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

# 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;
}

本页文档最后更新于：2021年5月16日

CSDN

stl

bitset