LOJ#515. 「LibreOJ β Round #2」贪心只能过样例(bitset)
LOJ#515. 「LibreOJ β Round #2」贪心只能过样例(bitset)
attack
发布于 2018-07-27 15:20:52
发布于 2018-07-27 15:20:52
内存限制：256 MiB时间限制：1000 ms标准输入输出
题目类型：传统评测方式：文本比较
上传者： nzhtl1477
题目描述
一共有 nnn个数，第 iii 个数 xix_ixi 可以取 [ai,bi][a_i , b_i][ai,bi] 中任意值。 设 S=∑xi2S = \sum{{x_i}^2}S=∑xi2，求 SSS 种类数。
输入格式
第一行一个数 nnn。 然后 nnn 行，每行两个数表示 ai,bia_i,b_iai,bi。
输出格式
输出一行一个数表示答案。
样例
样例输入
5
1 2
2 3
3 4
4 5
5 6样例输出
26数据范围与提示
1≤n,ai,bi≤1001 \le n , a_i , b_i \le 1001≤n,ai,bi≤100
臭名昭著的巧合
考场上只想到了暴力，完全没想到bitset优化qwq。
考虑的$\sum_1^100 100 * 100 = 1e6$
然后开个bitset每次暴力合并就行了
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<bitset>
#define rg register
using namespace std;
const int MAXN = 1e6 + 10001, mod = 19650827;
inline int read() {
char c = getchar();int x = 0,f = 1;
while(c < '0' || c > '9'){if(c == '-')f = -1;c = getchar();}
while(c >= '0' && c <= '9'){x = x * 10 + c - '0',c = getchar();}
return x * f;
}
int N;
bitset<MAXN> pre, nxt;
int main() {
N = read();N--;
int l = read(), r = read();
for(rg int i = l; i <= r; i++) pre[i * i] = 1;
for(rg int i = 1; i <= N; i++) {
int l = read(), r = read();
nxt.reset();
for(rg int k = l; k <= r; k++)
nxt |= pre << (k * k);
pre = nxt;
}
printf("%d", nxt.count());
return 0;
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2018-07-13 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录