CF1033E 题解
2024-10-21 18:32:32
题意
交互题,给定一个简单连通图,你可以询问一个点集 \(s\),返回其导出子图的边数。判断此图是否为二分图:若是,输出其中一部点的集合;否则输出任一个奇环。最多询问 \(20000\) 次。
\(1 \le n \le 600\)。
题解
对原图建立生成树,判断深度奇偶性相同的点是否有连边。
但建树的复杂度已经是 \(O(n^2)\),且难以优化。注意到条件仅对深度有要求,那么尝试忽略树的形态,仅找出所有点的深度。
可以得出这样一个算法:先找到深度为 \(0\) 的点集(即 \(\{1\}\)),然后找出所有与其有连边的点,即为深度为 \(2\) 的点集。依次类推。
考虑一下 “找出 \(S\) 中与 \(T\) 有连边的所有点“ 的复杂度。显然有一个 \(O(|S|)\) 的做法,但不够。我们需要其与答案个数有关,便于均摊。那么考虑分治。判断 \(S\) 与 \(T\) 是否有连边,可以通过 \(ask(S\cup T)-ask(S)-ask(T)\)。
那么就通过 \(O(n\log n)\) 得出了所有点的深度。于是可以判断二分图。还有一个问题是,若不是二分图,怎么找到奇环?
不妨设 \(S\) 为所有偶深度点的集合,且 \(ask(S)>0\)。那么通过枚举所有 \(x\in S\),可以找出一个与 \(S\setminus\{x\}\) 有连边的点。再枚举一遍,就找到一条边 \((x,y)\)。那么再找到它们到根的路径上的所有点即可,也就是找父亲。这显然可以通过二分。于是此题得解。
最新文章
- spring mvc 和spring security配置 web.xml设置
- Java8新特性——接口的默认方法和类方法
- oracle 10g 学习之多表查询、分组函数(6)
- 九度oj 1349 数字在排序数组中出现的次数
- Objective C静态代码扫描和代码质量管理 OClint + SonarQube
- 鼠标键盘无法进入:(EE) config/hal: couldn’t initialise context: (null)
- [Leetcode][Python]48: Rotate Image
- css的一些问题
- JSP 学习笔记
- ORA-00984: 列在此处不允许 SQL parse error location
- bzoj1977次小生成树(重要)
- instanceof详解
- C# show和showdialog区别
- C++11 并发指南四(<;future>; 详解三 std::future &; std::shared_future)
- Extjs4.2 Grid搜索Ext.ux.grid.feature.Searching的使用
- 阿里春招Android面经
- Linux中利用LVM实现分区动态扩容
- Android四种跨进程通信
- spring表单—乱码解决方案
- css工具类封装