[LOJ#515]「LibreOJ β Round #2」贪心只能过样例
2024-09-05 18:55:39
[LOJ#515]「LibreOJ β Round #2」贪心只能过样例
试题描述
一共有 \(n\) 个数,第 \(i\) 个数 \(x_i\) 可以取 \([a_i , b_i]\) 中任意值。
设 \(S=\sum{x_i^2}\) ,求 \(S\) 种类数。
输入
第一行一个数 \(n\)。
然后 \(n\) 行,每行两个数表示 \(a_i, b_i\)。
输出
输出一行一个数表示答案。
输入示例
5
1 2
2 3
3 4
4 5
5 6
输出示例
26
数据规模及约定
\(1 \leq n, a_i, b_i \leq 100\)
题解
分析一下复杂度发现可以上 bitset。。。
偶然发现这是博客中第一道 bitset 的题。。。
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <algorithm>
#include <bitset>
using namespace std;
int read() {
int x = 0, f = 1; char c = getchar();
while(!isdigit(c)){ if(c == '-') f = -1; c = getchar(); }
while(isdigit(c)){ x = x * 10 + c - '0'; c = getchar(); }
return x * f;
}
#define maxn 1000001
bitset <maxn> f, g;
int main() {
f[0] = 1;
int q = read();
while(q--) {
int l = read(), r = read();
for(int i = l; i <= r; i++)
if(i == l) g = f << i * i;
else g |= f << i * i;
f = g;
}
printf("%d\n", f.count());
return 0;
}
最新文章
- ANDROID开发实用小工具
- Python Set Literals
- Logback日志系统配置攻略
- class中new与未new的区别 类对象占用空间--转载
- /var/spool/postfix/maildrop 占用inode索引及磁盘空间解决办法
- Gap
- wxPython_Phoenix在线安装
- URL路由规则实例
- crud springmvc
- python爬爬(网友提供学习)
- ubuntu安装 cober 笔记
- 简单介绍如何使用robotium进行自动化测试
- 痞子衡嵌入式:ARM Cortex-M文件那些事(7)- 反汇编文件(.s/.lst/.dump)
- python,关于用户登录与注册问题
- P2512 [HAOI2008]糖果传递
- lucene随笔 IKAnalyzer StandardAnalyzer
- Docker学习计划三:Dockerfile 使用
- L3-021 神坛 (30 分)
- Zookeeper服务器集群的搭建与操作
- SPOJ VLATTICE Visible Lattice Points 莫比乌斯反演 难度:3
热门文章
- mvc的help和functions语法
- Python01 VSCode开发环境和入门程序
- JQuery EasyUI学习记录(二)
- 2019.05.26 周日--《阿里巴巴 Java 开发手册》精华摘要
- RabbitMQ 学习资料
- 03_10_Object类的toString equals等方法
- Java基础面试操作题: 线程问题,写一个死锁(原理:只有互相都等待对方放弃资源才会产生死锁)
- Eclipse+Tomcat搭建jsp服务器
- cocos2dx for iOS fmod的音效引擎接入
- VS2013连接SQL Server 2008 R2测试