AtCoder Grand Contest 002 简要题解
比赛地址Range Product简单讨论一下即可。代码Box and Ball简单模拟一下即可。注意盒子里仅有一个球的情况。代码Knot Puzzle能全部解开当且仅当存在两条相邻的绳子满足长度之和 $\geq L$。正确性显然。代码Stamp Rally先考虑怎么算从 $x,y$ 出发最多能到达的点数。显然，如果 $x,y$ 连通，则为 $sz_x$，否则为 $sz_x+sz_y$。这里...
标签 并查集 下的文章
- 首页
- 并查集
CF915F Imbalance Value of a Tree
CodeforcesLuogu分析容易发现，我们仅需要计算出每条链的最大值之和和最小值之和即可。而最小值之和可以通过把所有权值取相反数得到，因此我们只考虑求每条链的最大值之和。容易发现，这个东西等价于求每个点是多少条路径上的最大值。我们将所有点按权值从小到大排序并依次加入。加入点 $u$ 时，假设 $v$ 和 $u$ 相连且 $v$ 已被加入（即 $w_v\leq w_u$），则 $u$ 会...
洛谷5631 最小mex生成树
Luogu分析枚举一个答案 $ans$，那么我们相当于要求在删去边权为 $ans$ 的边后图是否存在一棵生成树，即图是否连通。显然可以考虑线段树分治。具体的，建一棵以边权为下标的线段树，对于每条边权为 $w$ 的边将其放到 $[0,w-1]$ 和 $[w+1,10^5]$ 上。然后在线段树上遍历，遍历到一个节点就将它上面挂着的边连上，这样子到叶结点时就连上了所有不包含该边权的边，判断图是否连...
BZOJ3712 [PA2014]Fiolki
BZOJ分析容易看出整个过程构成一棵二叉树，那么两种物质一定在 LCA 处发生反应。考虑反应发生的顺序。显然 LCA 深度大的反应先发生；如果 LCA 的深度相同，那么优先级高的先发生。因此建树后排个序模拟一下就好了。建议写树剖 LCA，这题树剖 LCA 的时间是倍增 LCA 的 1/2。代码// =================================== // author...
洛谷1525 关押罪犯
Luogu分析二分答案，问题变为是否存在一种方案使得任意一对怨气值 $>mid$ 的罪犯不在一个监狱里。我们把所有怨气值 $>mid$ 的罪犯拿出来连边，然后判断图是否为二分图即可。代码// =================================== // author: M_sea // website: http://m-sea-blog.com/ // ...
洛谷3457 [POI2007]POW-The Flood
Luogu分析首先你要看懂题。然后可以发现一个事实：如果 $(x,y)$ 有一个相邻格子 $(x',y')$ 满足 $h_{x,y}\geq h_{x',y'}$，则如果 $(x',y')$ 被抽完了，那么 $(x,y)$ 一定也被抽完了。因此我们把所有格子按高度从小到大排序，对于每个格子遍历相邻的格子，如果相邻的格子高度不大于它就用并查集合并起来。然后如果当前这个格子是城市并且连通块内没有...
LOJ121 「离线可过」动态图连通性
LOJ分析线段树分治板子题？考虑每条边出现的时间都是若干段区间。我们以时间为下标建一棵线段树，然后在每条边出现的区间挂上这条边。然后我们把询问挂在叶节点上。DFS 这棵线段树，每次到一个节点后就把这个节点上挂的所有边连上。这样子到叶节点时该时间点所有的边都已经连上了，直接询问是否连通即可。这个过程中用一个可撤销并查集维护连通性即可。代码// =========================...
CF650E Clockwork Bomb
CodeforcesLuogu分析设 $fa_1[u]$ 表示 $u$ 在第一棵树上的父亲，$fa_2[u]$ 表示 $u$ 在第二棵树上的父亲。现在在第一棵树上 DFS。假设现在在 $u$，如果 $(fa_1[u],u)$ 没有在第二棵树上出现过，那么就把它换成 $(fa_2[u],u)$。这样子会有一个问题，就是可能 $(fa_2[u],u)$ 已经被连上了。这种情况只要往上跳 $fa_...
BZOJ3714 [PA2014]Kuglarz
BZOJ分析感觉这题的建模好妙啊...设 $sum_i$ 表示 $\sum_{j=1}^i[i\text{中有球}]$。显然我们只需要知道所有的 $sum_i$ 就可以知道每个杯子中是否有球了。考虑到如果询问了 $[i,j]$，那么一旦知道 $sum_{i-1}$ 或 $sum_j$ 中的一个就可以知道另一个。因此考虑这样一个模型：对于每个区间 $[i,j]$ ，在 $i-1$ 和 $j$ ...
CF859E Desk Disorder
CodeforcesLuogu分析把每个座位看作点，每个人现在的座位向想去的座位连边，那么每个点的出度至多为 $1$。显然我们应该每个连通分量分开计算方案数，再全部乘起来。每个连通分量内部只会有 $3$ 种情况：包含自环，方案数显然为 $1$。包含不是自环的环，方案数显然为 $2$。是一棵树，画一画图可以发现方案数为 $sz$。用并查集维护一下连通块的 $sz$、是否有环、是否有自环即可。代...