最新要闻
- 最新消息:你看过几场?2022年国内电影总票房超300亿
- 即时焦点:必囤:百草味年货坚果大礼包1370g/8袋仅49元
- 微速讯:特斯拉拼了:其他品牌车辆置换特斯拉 3.2万元功能免费用90天
- 全球首架国产大飞机C919新年首飞:验证飞行将达100小时
- 每日快看:全球最大第三方Android系统!基于Android 13的LineageOS 20正式发布
- 全球今头条!联想新款迷你主机M60Q官宣:厚度仅3.4厘米 可选12代i5
- 当前简讯:2023大事前瞻:杭州亚运会9月举办 首次纳入电竞比赛项目
- 热头条丨日本外卖小哥晒收入:月入合人民币5.5万元
- 全球焦点!80秒看全球跨年烟火秀:用璀璨夜空迎接2023 你那能放烟花吗
- 【天天热闻】中国汽车保有量超3亿辆 千人拥有量达220辆 已成普通家庭消费品
- 搜索页上全是广告和推荐?用这插件一键去除
- 播报:新规即日起开始执行!手机预装App终于可以卸载了
- 苹果4GB内存为何能击败安卓12GB?历代iPhone内存容量公布:最大不过6GB
- 每日热议!铁路新规今日起施行:实名制儿童火车票将按照年龄购买 不看身高
- 每日资讯:Intel带着56核心再次发烧!新座驾降临 能插16条内存
- 环球头条:大批192号段诈骗电话出现!中国广电发布提醒:电商客服不会用192
手机
iphone11大小尺寸是多少?苹果iPhone11和iPhone13的区别是什么?
警方通报辅警执法直播中被撞飞:犯罪嫌疑人已投案
- iphone11大小尺寸是多少?苹果iPhone11和iPhone13的区别是什么?
- 警方通报辅警执法直播中被撞飞:犯罪嫌疑人已投案
- 男子被关545天申国赔:获赔18万多 驳回精神抚慰金
- 3天内26名本土感染者,辽宁确诊人数已超安徽
- 广西柳州一男子因纠纷杀害三人后自首
- 洱海坠机4名机组人员被批准为烈士 数千干部群众悼念
家电
AcWing362. 区间
(相关资料图)
题目描述
给定 \(n\) 个区间 \([a_i,b_i]\) 和 \(n\) 个整数 \(c_i\)。
你需要构造一个整数集合 \(Z\),使得 \(\forall i \in [1,n]\),\(Z\) 中满足 \(a_i \le x \le b_i\) 的整数 \(x\) 不少于 \(c_i\) 个。
求这样的整数集合 \(Z\) 最少包含多少个数。
解题思路
\(\qquad\) 根据前缀和思想,我们用\(s[k]\)表示最好选法中,整数集合\(Z\)包含了\(0\sim k\)中的\(s[k]\)个数,那在整数集合中\(a_i\le x\le b_i\)的数也就是\(s[b_i]-s[a_i-1]\ge c_i\),那我们就可以看出一个差分约束系统
,将\(a_i-1\)向\(b_i\)连一条权重为\(1\)的有向边。
\(\qquad\)但是如果要求解,那这一个差分约束的条件不够,应该再找几个:
\(\qquad\qquad\Large a.\)由于\(0\sim k\)中间选的数不会\(0\sim k - 1\)的少,所以\(s[k] - s[k-1]\ge 0\)
\(\qquad\qquad\Large b.\)由于一个数至多只能选一次,所以\(s[k]-s[k-1] \le 1\),转化成\(s[k-1]-s[k]\ge -1\)
整理上式我们可以得到一个差分约束系统
\[\left \{\begin{array}cs[b_i]-s[a_i-1]\ge c_i\\s[k] - s[k-1]\ge 0\\s[k-1]-s[k]\ge -1\end{array}\right.\]然后就是求一个\(-1\)到\(50001\)的最长路,为了方便可以把所有下标\(+1\)
代码
#include #include using namespace std;const int N = 5e4 + 10, M = 3 * N;int dist[M], st[M], q[M], hh = 0, tt = 1;int h[M], e[M], ne[M], w[M], idx;int n, a, b, c;int spfa() { memset(dist, 0xcf, sizeof dist); q[0] = dist[0] = 0, st[0] = true; while (hh != tt) { int t = q[hh ++ ]; st[t] = 0; if (hh == N) hh = 0; for (int i = h[t]; ~i; i = ne[i]) { int j = e[i]; if (dist[j] < dist[t] + w[i]) { dist[j] = dist[t] + w[i]; if (!st[j]) { q[tt ++ ] = j, st[j] = 1; if (tt == N) tt = 0; } } } } return dist[50001];}void add(int a, int b, int c) { e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx ++ ;}int main() { scanf("%d", &n); memset(h, -1, sizeof h); for (int i = 1; i <= 50001; i ++ ) add(i - 1, i, 0), add(i, i - 1, -1); for (int i = 1; i <= n; i ++ ) { scanf("%d%d%d", &a, &b, &c); add(a, b + 1, c); } printf("%d\n", spfa()); return 0;}
关键词: 约束系统
-
AcWing362. 区间
题目描述给定$n$个区间$[a_i,b_i]$和$n$个整数$c_i$。你需要构造一个整数集合$Z$,使得$ foralli in[1,n]$,$Z$中满足$a_i
来源: AcWing362. 区间
最新消息:你看过几场?2022年国内电影总票房超300亿
即时焦点:必囤:百草味年货坚果大礼包1370g/8袋仅49元
微速讯:特斯拉拼了:其他品牌车辆置换特斯拉 3.2万元功能免费用90天
全球首架国产大飞机C919新年首飞:验证飞行将达100小时
每日快看:全球最大第三方Android系统!基于Android 13的LineageOS 20正式发布
全球今头条!联想新款迷你主机M60Q官宣:厚度仅3.4厘米 可选12代i5
当前简讯:2023大事前瞻:杭州亚运会9月举办 首次纳入电竞比赛项目
热头条丨日本外卖小哥晒收入:月入合人民币5.5万元
观察:MYSQL安装教程及sqlyog初次使用
全球焦点!80秒看全球跨年烟火秀:用璀璨夜空迎接2023 你那能放烟花吗
【天天热闻】中国汽车保有量超3亿辆 千人拥有量达220辆 已成普通家庭消费品
搜索页上全是广告和推荐?用这插件一键去除
播报:新规即日起开始执行!手机预装App终于可以卸载了
苹果4GB内存为何能击败安卓12GB?历代iPhone内存容量公布:最大不过6GB
每日热议!铁路新规今日起施行:实名制儿童火车票将按照年龄购买 不看身高
焦点热讯:MAUI新生6.5-导航路由Navigation
每日资讯:Intel带着56核心再次发烧!新座驾降临 能插16条内存
环球头条:大批192号段诈骗电话出现!中国广电发布提醒:电商客服不会用192
热文:一项大奖的所有得主:都没有后代 为什么呢?
动态焦点:SpaceX预告2023年第一发:一箭114星!超越印度新纪录
要再见了!《魔兽世界》临时充值渠道将于1月1日0点正式关闭
詹姆斯生日夜狂砍47分!杜兰特盛赞其表现:神迹!
第119篇: JavaScript 类
天天速递!仅仅10年 中国在西部修了2.5万公里铁路
【天天聚看点】直播央视2023跨年晚会:明星阵容豪华、两大运动员登台
3999元 LG新款27英寸显示器开售:搭载4K Nano IPS Black屏
2423公里!曾经的中国西部最长铁路 开通60年了
焦点热门:妈妈给儿子读英语 发音如原声磁带!6岁孩子开口惊人
玩家吐槽《塞尔达传说:王国之泪》NS限定机太丑:希望不是真的
报道:屏幕碾压iPhone 14 Pro!红魔8 Pro系列20点开售:3999元起
今日快看!男子上公厕10分钟门自动打开:装了定时器 网友吐槽不合理
36个月流畅不卡顿!卢伟冰:Redmi 12C满足低预算人群核心需求
手工耿又出大作 自制小黄人悬空火炉 网友:有用、想要
世界微资讯!AcWing 1359. 洛谷P1457 城堡
LaTeX快速入门
【天天聚看点】早餐来一盒 伊利高端品牌金典纯牛奶24盒到手76元
世界报道:28年再温经典!周星驰电影《大话西游》元旦抖音全网独播
当前热讯:Python类的多态和多态性
当前观点:红绿灯倒计时覆盖量破百万 百度地图:全国3000县市只差1个没有
世界新消息丨“流氓软件”拜拜!手机预装App终于要能卸载了:新规明天执行
长城大气!魏牌官宣:国补取消后插混车型不涨价
马斯克疯狂省钱:断供厕纸、辞退保洁、退租办公室
Codeforces Good Bye 2022 CF 1770 A~E 题解
世界观天下!上调幅度2000到6000元!比亚迪宣布调整相关车型官方指导价
【环球热闻】今晚20点播出!央视跨年晚会阵容官宣:短道速滑运动员武大靖加盟
每日简讯:分布式排队叫号系统源码出售
口碑崩盘豆瓣评分跌至5.4!《三体》动画第五集上线你还追吗?
WPF 实现通知属性的N种方式
P3Depth: Monocular Depth Estimation with a Piecewise Planarity Prior
全球滚动:从USB存储设备启动树莓派
全球快看:满满维生素!可口可乐innocent果汁大促:三瓶券后不到15元
天天热门:长绒棉亲肤透气 浪莎男士中筒袜子5双21.55元
每日讯息!2023元旦档预售总票房破1亿元:《阿凡达2:水之道》第一
《王者荣耀》铠荣耀典藏皮肤今晚上线!三形态特效帅炸
头条:游戏火爆全球 海外营收过半!米哈游获评全国文化企业30强
快播:Unreal学习笔记1-打印输出
环球速读:史上财富损失第一人:马斯克财产缩水破人类记录
即时:官旗抄底:新疆大红乌苏啤酒500ml*12罐整箱59.9元
环球即时:沙特球队官宣C罗加盟 本人回应:是时候来亚洲分享经验了
一加11R外观泄露:双曲面屏、后置三摄
MySQL报错解决
当前观点:联想YOGA新款笔记本曝光:双屏显示、支持360度翻转
天天快资讯:0糖、0脂肪!Nevercoffee咖啡:10盒到手16.41元
天天快资讯丨兴泉铁路全线开通:8个老区终于坐上火车
【世界报资讯】电脑上没有“锤子大爆炸”:自己做一个!
环球快播:辽宁吉林多地现不明飞行物:外星飞船?还是韩国制造?
天天速讯:女子因上厕所未在工位被领导打:网友集体愤怒
天天日报丨知情人士:李子柒短期内或不考虑复出 业内看好重回顶流
速递!奥迪最帅量产电车!RS e-tron GT上市:146.88万秒杀保时捷
网友在苹果官方旗舰店买iPhone 13:取消订单却不给退款
快讯:三大件不再是重点 调查显示:84.5%消费者更看重汽车智能化
环球微动态丨ColorOS 13 2023年Q1适配计划出炉:10款机型喜提正式版
环球新动态:2022年总结与反思
全球热文:显卡清库存告一段落 价格已经到底:AMD、NVIDIA不会再便宜
【全球新要闻】RTX 4090游戏本狂野!一脚踢翻桌面RTX 3090
有你吗?我国千兆宽带用户达到8707万户 同比增长157%
全球最新:联想SmartPaper墨水平板曝光:10.3寸大屏、23ms低延迟
天天即时:国产游戏《大多数》称《九霄大陆》是盗版 把自己破解了
【天天时快讯】HDU 6801 Game on a Circle 题解 (推式子,多项式)
LeetCode-400. 第N位数字
全球观热点:红黑树起源以及插入解析
世界简讯:“最牛00后”:成都122岁长寿老人朱郑氏去世 家人100多名
全球快看点丨女子圣诞节送男友PS5:送礼前先把自己感动哭了
【全球速看料】比亚迪发布公告:终止拆分半导体业务上市
世界热门:新能源车国补即将取消 零跑表态:零跑C01不涨价
【全球独家】复习Stream流,函数式接口,方法引用
【天天新视野】最贵国产电动车高合HiPHi X宣发闹乌龙:零百加速45分钟
全球信息:杀死110公斤牛 北半球最凶猛的鸟金雕复仇人类:缝了40针
热资讯!软嫩多汁 拒绝合成肉:大希地整切牛排55.8元/斤好价
新能源车二手车:又红火起来了
全球热消息:腾讯今年股价曾腰斩 累计回购超9000万股 耗资超337亿港元
环球快消息!特色功能(锐捷智慧教室)
RX 7900 XTX温度烧到110度 AMD终于回应了:请联系客服支持
全球热议:盗版电影画质越发高得可怕 英国正版组织怒出手:嫌疑人落网
苹果允许安装第三方商店 但用户愿意吗?
【独家】RTX 4070 Ti官方偷跑!跑分都亮出来了
东方甄选直播一周年:股价翻800% 腾讯亏惨了
Android Emulator Container 配置
京东自营次日达 抗原检测试剂盒4.9元/份:15分钟出值