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

内存限制：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。

输出格式

输出一行一个数表示答案。

样例

样例输入

样例输出

数据范围与提示

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 + , mod = ;

inline int read() {

    char c = getchar();int x = ,f = ;

    while(c < '' || c > ''){if(c == '-')f = -;c = getchar();}

    while(c >= '' && c <= ''){x = x *  + c - '',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] = ;

    for(rg int i = ; 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 ;

}

巴特西