[原创]「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

题目描述

一共有nn个数,第ii 个数xix_i可以取[ai,bi][a_i , b_i]中任意值。
S=xi2S = \sum{ {x_i}^2},求SS 种类数。

输入格式
第一行一个数nn
然后nn 行,每行两个数表示ai,bia_i,b_i

输出格式
输出一行一个数表示答案。
样例
样例输入

5
1 2
2 3
3 4
4 5
5 6
样例输出

26
数据范围与提示
1n,ai,bi1001 \le n , a_i , b_i \le 100
——————————————————————————————————
其实这个题目很好想,

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

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

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

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

写了一发但是还是TLE了

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

bitset

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

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

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

支持整形位运算符


本题就一样
x2x^21<<(x2)1<<(x^2)来标记

x2+y2x^2+y^21<<(x2+y2)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;
}