hdu6109(并查集+set/倍增)
2024-10-20 08:53:49
题目
http://acm.hdu.edu.cn/showproblem.php?pid=6109
分析
对于相同的条件，明显直接并查集
对于不同的条件，可以用set来保存，并查集合并的时候也要对set启发式合并
还有另一种很奇妙的做法
如果我们只考虑一段[l..r]是否可行，那么我们可以离线，先挑出相同的条件构出并查集，然后对所有的不同条件进行判断就行了
这样我们就可以写出一个时间复杂度为O(r-l)的check(l,r)
那我们怎么分段呢？
我们对于当前起点now，进行倍增寻找长度最小的L(L=2^k)使得[now...now+L]这一段不能构成一段
然后我们再对[now..now+L]进行二分寻找准确的分界点
时间复杂度O(nlogn)
最新文章
- 在MVC控制器里面使用dynamic和ExpandoObject，实现数据转义的输出
- this
- 《zw版·Halcon-delphi系列原创教程》 只有2行代码的超市收款单ocr脚本
- iOS中使用RSA对数据进行加密解密
- Solr学习笔记（一）
- Android应用加入微信分享
- Ext.Net学习笔记03：Ext.Net MessageBus用法
- [cocos2d-x] 让精灵响应触摸 并把方向旋转到相对应的角度
- Linux 使用 cp 命令强制覆盖功能
- 【原】用Java编写第一个区块链（二）
- 使用Nome监控服务器各项指标
- 002-golang安装配置
- background-position 的设置
- PHP 多态理解
- windows系统安装
- ubuntu 安装u盘恢复
- 记DateTime.Now.ToString()遇到的一个坑
- 关于Unity中的摄像机
- Mediainfo的编译安装（suse）
- 远程线程注入shellcode笔记