[JOI2017春季合宿]Port Facility[set、二分图]
2024-10-19 06:19:55
题意
你有两个栈，有 \(n\) 个货物，每个货物有一个进栈时间和出栈时间（所有时间的并集是1~2n），问有多少种不同的入栈方案。
\(n\le 10^6\)
分析
- 把每个货物的存在看成区间，相交的区间不能在同一个栈中。这样就有了 \(O(n^2)\) 连边的方式，再用二分图染色判断一下是否合法即可。合法方案数就是 \(2^{连通块个数}\)。
- 考虑将所有区间按照左端点排序，用一个 set 维护和当前区间相交的区间。由于不能出现三元环所以所有和当前区间相交的区间都是包含关系，这种包含区间之间形成了树形结构，每个区间记录其父亲。只需要保留右端点最小的那一个(可能之后会变成其父亲)，剩余的用另一种边表示这些区间的颜色相同。保留的区间在之后的包含关系中一定作为最大的出现。
- 复杂度 \(O(nlogn)\)
代码
最新文章
- 11-JS基础
- Linux网络编程-SIGPIPE信号导致的程序退出问题
- Activity之间的数据传递
- yum.pid 已被锁定
- MVC三个IOC注入点之Ninject使用示例
- Java 四种线程池的用法分析
- 《java.util.concurrent 包源码阅读》27 Phaser 第一部分
- kubernetes调度pod运行于master节点上
- 【转】详解web.xml中元素的加载顺序
- Linux第四节课学习笔记
- 洛谷P2866 [USACO06NOV]糟糕的一天Bad Hair Day(单调栈)
- u-boot(二)makefile
- 弱符号__attribute__((weak))
- java用poi读取Excel表格中的数据
- Android 音视频深入 五 完美的录视频(附源码下载)
- oracle导入大sql文件
- ES版本控制
- [leetcode]Symmetric Tree @ Python
- android(二) SurfaceView
- div内容过长自动省略号