洛谷4117 [Ynoi2018]五彩斑斓的世界
Luogu分析考虑分块。对于每一块，维护它的最大值 $mx$。可以发现 $\sum mx$ 是 $\mathcal{O}(n\sqrt{n})$ 级别的，因此每一块如果能够 $\mathcal{O}(x)$ 修改的话复杂度就是 $\mathcal{O}(n\sqrt{n})$。可以想到这样的修改方式如果 $2x\geq mx$，则直接将所有 $>x$ 的数减去 $mx$。这样子是 $\...
标签 并查集 下的文章
- 首页
- 并查集
洛谷2178 [NOI2015]品酒大会
Luogu[LOJ](https://loj.ac/problem/2133）分析如果两个位置是 $r$ 相似的，则它们也是 $k\in[0,r)$ 相似的。我们可以只求出 LCP 为 $r$ 时的答案，再求一遍后缀和/后缀 max 即可得到答案。考虑两个位置的 LCP 实际上是一段区间的 $height$ 的最小值。我们可以将 $height_i$ 从大到小排序，每次加入一个 $heigh...
洛谷3826 [NOI2017]蔬菜
LuoguLOJ分析考虑求出卖了 $i$ 个蔬菜时的最大收益 $ans_i$。容易想到，我们要先卖贵的菜，且要尽量靠后卖。用一个堆维护所有还有存货的蔬菜，然后每次选一个收益最大的放在能放的最后的一天。通过并查集维护每一天往前到哪一天才有没有用掉卖的额度即可求出这一天。假设最多能卖 $cnt$ 个蔬菜，则前 $i$ 天的答案为 $ans_{\min\left\{cnt,m\times i\ri...
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 这棵线段树，每次到一个节点后就把这个节点上挂的所有边连上。这样子到叶节点时该时间点所有的边都已经连上了，直接询问是否连通即可。这个过程中用一个可撤销并查集维护连通性即可。代码// =========================...