欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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

程序员文章站 2022-06-20 14:42:43
内存限制:256 MiB时间限制:1000 ms标准输入输出 题目类型:传统评测方式:文本比较 上传者: nzhtl1477 内存限制:256 MiB时间限制:1000 ms标准输入输出 题目类型:传统评测方式:文本比较 上传者: nzhtl1477 提交提交记录统计讨论测试数据 题目描述 一共有  ......
内存限制:256 MiB时间限制:1000 ms标准输入输出
题目类型:传统评测方式:文本比较
上传者: 
 

题目描述

一共有 nnn个数,第 iii 个数 xix_ixi​​ 可以取 [ai,bi][a_i , b_i][ai​​,bi​​] 中任意值。
设 S=∑xi2S = \sum{{x_i}^2}S=xi​​2​​,求 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 1001n,ai​​,bi​​100

 

臭名昭著的巧合

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

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

考场上只想到了暴力,完全没想到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;
}