GoldenPotato137的小屋

并查集
并查集

[BZOJ 4025] 二分图

题面 4025: 二分图 Solution 这种每条边出现在一段区间的题,我们可以先考虑使用线段树分治来搞。 这题我们考虑离线下来搞。离线之后,我们会发现,某条边会在某些询问区间中出现。 考虑以询问的编号为下标建线段树,我们把每一条边出现的时间段全部加到线段树里面去。 接下来,我们考虑如何维护一个图是否为二分图的问题。我们知道,一个图是二分图当且仅当这个图上所有的环的长度(点的个数)均为偶数。 知道这一点之后,我们考虑用并查集处理这个问题。对于没有环的时候,我们直接连上就好。对于有环的时候,我们就需要知道这两个点的…

2019年3月25日 0条评论 648点热度 0人点赞 GoldenPotato137 阅读全文
并查集

[Luogu P4246] [SHOI2008]堵塞的交通

题面 P4246 [SHOI2008]堵塞的交通 Solution 这题的确是有线段树上大分类讨论的在线做法,但是本菜鸡还是想主要讲一下离线暴力做法。 这题我们考虑离线下来搞。离线之后,我们会发现,某条边会在某些询问区间中出现。 考虑以询问的编号为下标建线段树,我们把每一条边出现的时间段全部加到线段树里面去。 接下来,直接在线段树上跑dfs,每到一个区间,就把这个区间里面存的边通通在并查集中连上;每完成一个区间,就把这个区间连上的边通通取消(类似于回溯)。 这样搞,我们每次到一个叶子节点的时候,这个叶子节点代表的询…

2019年3月22日 0条评论 1042点热度 0人点赞 GoldenPotato137 阅读全文
并查集

[Luogu P5227] [AHOI2013] 连通图

题面 P5227 [AHOI2013]连通图 Solution 这题可以离线,因此我们可以考虑用线段树分治维护动态图连通性来搞。 这题我们考虑离线下来搞。离线之后,我们会发现,某条边会在某些询问区间中出现。 考虑以询问的编号为下标建线段树,我们把每一条边出现的时间段全部加到线段树里面去。 接下来,直接在线段树上跑dfs,每到一个区间,就把这个区间里面存的边通通在并查集中连上;每完成一个区间,就把这个区间连上的边通通取消(类似于回溯)。 这样搞,我们每次到一个叶子节点的时候,这个叶子节点代表的询问上所要连的边一定已经…

2019年3月22日 0条评论 898点热度 2人点赞 GoldenPotato137 阅读全文
并查集

[LOJ 121] 「离线可过」动态图连通性

题面 #121. 「离线可过」动态图连通性 Solution 这题我们考虑离线下来搞。离线之后,我们会发现,某条边会在某些询问区间中出现。 考虑以询问的编号为下标建线段树,我们把每一条边出现的时间段全部加到线段树里面去。 接下来,直接在线段树上跑dfs,每到一个区间,就把这个区间里面存的边通通在并查集中连上;每完成一个区间,就把这个区间连上的边通通取消(类似于回溯)。 这样搞,我们每次到一个叶子节点的时候,这个叶子节点代表的询问上所要连的边一定已经全部连上了,直接在并查集中查询即可。 因为我们这里有撤销(回溯)操作…

2019年3月22日 0条评论 951点热度 2人点赞 GoldenPotato137 阅读全文
分块

[Luogu P3247] [HNOI2016]最小公倍数

题面 P3247 [HNOI2016]最小公倍数 Solution 这是一道妙题。 首先,根据常识,题面要我们求的是找一条从s,t的路径,使得路径上$max\ a=a,max\ b=b$。 这咋求呢?我们会发现,我们要求的路径本质上是一个连通块,连通块可以考虑用并查集处理。 接下来考虑对a分块,先把所有的边按照$a$来排序,再分块,每个块里连的所有边保证$<=a_{[size*x]}$,如下图所示: 接下来,我们考虑把所有询问按照b从小到大排序去一个个计算,每计算一个询问之前,把$b<=q[i].b$的…

2019年3月19日 0条评论 580点热度 1人点赞 GoldenPotato137 阅读全文

GoldenPotato137

LLer/ACMer/HITer/数院菜鸡/ECS折磨中

最近评论
hilaolu 发布于 1 年前(03月16日) 球球屑gp翻我展示一下ua屑屑
Guava 发布于 2 年前(11月30日) @GoldenPotato137 暂时是 guavaoj.tk
碱式碳酸希 发布于 2 年前(11月30日) 可以先不要告诉老师们吗(偷偷搞的
碱式碳酸希 发布于 2 年前(11月04日) %%%%Tql 请求搬运至NNEZ校内OJ公告中。 展示链接: 请在启天楼内网中访问! :razz:...
630分苦苦挣扎的菜鸡土豆 发布于 2 年前(05月01日) 肥肠抱歉,刚刚看见呢。 那个发送留言不能立刻看见源于我站挂了个腾讯云cdn,默认会返缓存的内容qwq...
分类
  • CDQ分治
  • DAG DP
  • DP+DP
  • FFT/NTT
  • Kruskal重构树
  • LCT
  • LUCAS
  • NNEZ
  • set
  • splay
  • 主席树
  • 二分/二分答案
  • 位运算
  • 倍增
  • 其他
  • 分块
  • 动态规划
  • 卷积
  • 反演
  • 同余
  • 后缀数组
  • 后缀自动机
  • 哈希
  • 图论
  • 圆方树
  • 堆
  • 多项式
  • 字符串
  • 学习笔记
  • 容斥
  • 容斥
  • 左偏树
  • 并查集
  • 数位DP
  • 数学
  • 数据结构
  • 整体二分
  • 斯特林数
  • 最小割
  • 最短路径
  • 未分类
  • 树套树
  • 树形DP
  • 模拟
  • 深度学习
  • 游记/自闭记/滚粗记
  • 点分治
  • 状压DP
  • 生涯纪录
  • 线段树
  • 组合数学
  • 缩点/强连通分量
  • 网格DP
  • 网络最大流
  • 网络流
  • 背包DP
  • 虚树
  • 贪心
  • 边双/点双
归档
  • 2022年1月
  • 2021年9月
  • 2021年3月
  • 2021年2月
  • 2019年11月
  • 2019年4月
  • 2019年3月
  • 2019年2月

COPYRIGHT © 2022 GoldenPotato137的小屋. ALL RIGHTS RESERVED.

Theme Kratos Made By Seaton Jiang

桂ICP备20002051号