专栏首页数据结构与算法LOJ#515. 「LibreOJ β Round #2」贪心只能过样例(bitset)

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

内存限制:256 MiB时间限制:1000 ms标准输入输出

题目类型:传统评测方式:文本比较

上传者: nzhtl1477

提交提交记录统计讨论测试数据

题目描述

一共有 nnn个数,第 iii 个数 xix_ix​i​​ 可以取 [ai,bi][a_i , b_i][a​i​​,b​i​​] 中任意值。 设 S=∑xi2S = \sum{{x_i}^2}S=∑x​i​​​2​​,求 SSS 种类数。

输入格式

第一行一个数 nnn。 然后 nnn 行,每行两个数表示 ai,bia_i,b_ia​i​​,b​i​​。

输出格式

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

样例

样例输入

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,a​i​​,b​i​​≤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;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 洛谷P3201 [HNOI2009]梦幻布丁

    题目描述 N个布丁摆成一行,进行M次操作.每次将某个颜色的布丁全部变成另一种颜色的,然后再询问当前一共有多少段颜色.例如颜色分别为1,2,2,1的四个布丁一共有...

    attack
  • UOJ#386. 【UNR #3】鸽子固定器(链表)

    如果我们按$s$排序后,我们就可以枚举$max  \ s_i$和$min \ s_i$

    attack
  • P1801 黑匣子_NOI导刊2010提高(06)

    题目描述 Black Box是一种原始的数据库。它可以储存一个整数数组,还有一个特别的变量i。最开始的时候Black Box是空的.而i等于0。这个Black ...

    attack
  • POJ-2329 Nearest number - 2(BFS)

    Nearest number - 2 Time Limit: 5000MS Memory Limit: 65536K Total Submis...

    ShenduCC
  • HDU 3368 Reversi

    http://acm.hdu.edu.cn/showproblem.php?pid=3368 题意:模拟黑白棋,下一步黑手最大可以转化多少个白旗 分析:暴力  ...

    用户1624346
  • POJ-3461-Oulipo

    ACM模版 描述 ? 题解 KMPKMP 入门级题目,模板题。 代码 #include <iostream> const int MAXN = 1e4 + 1...

    f_zyj
  • 指针(一)

    什么是野指针?野指针就是指针指向的位置是不可知的(随机的、不正确的、没有明确限制的)

    DeROy
  • hdu1016

    @坤的
  • 1216 跳马问题

    1216 跳马问题 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 黄金 Gold 题目描述 Description 题目 ? ...

    attack
  • 【编程基础】C++比C牛逼的七个点

    1. 函数检测增强 ? 在C语言中,重复定义多个同名的全局变量是合法的,在C++中,不允许定义多个同名的全局变量。 C语言中多个同名的全局变量最终会被链接到全局...

    程序员互动联盟

扫码关注云+社区

领取腾讯云代金券