【牛客网71E】 组一组(差分约束,拆位)
2024-10-18 00:53:36
传送门
Solution
考虑一下看到这种区间或与区间与的关系,拆一下位。
令\(s_i\)表示前缀和,则:
那么如果现在考虑到了第\(i\)为,有如下4种可能:
- \(opt=1\),\(x\)在\(i\)这位有值,那么就有\(s_r-s_{l-1} \ge 1\)
- \(opt=1\),\(x\)在\(i\)这位没值,那么就有\(s_r-s_{l-1} = 0\)
- \(opt=2\),\(x\)在\(i\)这位有值,那么就有\(s_r-s_{l-1} = r-l+1\)
- \(opt=2\),\(x\)在\(i\)这位没值,那么就有\(s_r-s_{l-1} \leq r-l\)
- \(s_i>=s_{i-1}\),因为值只有\(0,1\),所以前缀和一定会有这个性质。
所以发现这个就可以差分约束,然后随便搞一下你就发现,只有80pts!!!
80pts代码实现
咦,这是为什么啊?
然后考虑如果一段区间的&
是1,显然这一段都是1,所以就可以快速差分然后连边了,这样子,据\(yyb\)说可以加快...
代码实现
最新文章
- Java界面设计 Swing(1)
- iOS 私有变量 私有方法
- 树链剖分+线段树 HDOJ 4897 Little Devil I(小恶魔)
- ASP.NET MVC3的学习
- centos 6 cglib
- Zxing兼容2.3等低版本
- android自定义控件(2)-拖拽实现开关切换
- FIFO跨时钟域读写
- Ul li 横排 菜单
- IIS提示Server Application Unavailable
- codevs 1519 过路费 最小生成树+倍增
- java编译期优化与执行期优化技术浅析
- ansible 判断和循环
- NancyFX 第八章 内容协商
- JDBC学习笔记 day1
- python3 员工信息表
- 非阻塞读和写:str_cli函数
- java集合的复习
- CISCO 关闭4786端口解决方法
- Netty 核心组件笔记