CF578F Mirror Box
CodeforcesLuogu分析我们把顶点黑白染色，那么一面镜子就可以看成是连接同色点的一条边。接下来给出一个结论：一个方案合法当且仅当黑点连成了一棵树或者白点连成了一棵树。（比较感性理解的）证明：首先，当黑点连边确定时白点连边一定唯一确定，所以我们只考虑黑边确定的情况。先证必要性：先考虑后面那个限制。如果连成了环，则环内部的边一定没有光线会穿过，所以不能有环。再考虑前面那个限制。我们需要...
标签 并查集 下的文章
- 首页
- 并查集
JOISC2019 简要题解
官网AtCoderLOJ試験 / Examination三维偏序板子，CDQ 即可。代码ビーバーの会合 / Meetings首先有一个结论：Query(x,y,z) 返回的是三个点两两之间 LCA 中最深的那个。我们先在 $[1,n)$ 中随机一个点 $y$，然后询问 $(0,y,z)$，即可求出 $0\to y$ 链上的点以及其它点在链上那个点的子树中。那么直接递归处理链上每个点剩下的子树...
LOJ2865 「IOI2018」狼人
LOJUOJLuogu分析以端点的 $\min$ 为边权建一棵 Kruskal 重构树，以端点的 $\max$ 为边权建一棵 Kruskal 重构树。那么我们在第一棵树上从 $s$ 向上跳到最浅的 $\geq l$ 的点，其子树就是人类状态下从起点出发能走到的点；在第二课树上从 $t$ 向上跳到最浅的 $\geq r$ 的点，其子树就是狼人状态下能走到终点的点。那么我们只需要求这两棵子树中的...
AtCoder Regular Contest 065 简要题解
比赛地址白昼夢 / Daydream如果当前字母是 d 则依次匹配 dreameraser、dreamerase、dreamer、dream，如果当前字母是 e 则依次匹配 eraser、erase。不如直接倒着做代码連結 / Connectivity开两个并查集，然后开个 map 维护一下 [find1(i),find2(i)] 即可。代码へんなコンパス / Manhattan Compa...
CF156D Clues
CodeforcesLuogu分析我们把每个连通块看成一个点，然后用 Prufer 序列计数。那么方案数为用并查集求出连通块个数及每个连通块的大小即可。代码// ==================================== // author: M_sea // website: https://m-sea-blog.com/ // ===================...
CF908H New Year and Boolean Bridges
CodeforcesLuogu分析显然满足 $G_{i,j}=\mathsf{A}$ 的 $i,j$ 在同一个强连通分量内，所以先把这些点并起来。那么如果一个强连通分量内有 XOR 边就是不合法的。显然每个强连通分量内成环最优，那么答案等于 $n-1+$点数 $\geq 2$ 的强连通分量个数，则应最小化后面那个东西，即把一些强连通分量在满足条件的情况下合并成一个大环。因为点数 $\geq ...
ARC098F Donation
AtCoderLuogu分析设 $c_i=\max\left\{0,a_i-b_i\right\}$，则相当于要求任意在 $u$ 点的时刻手中都有至少 $c_u$ 円。然后可以发现两个结论：每个点只会在最后一次访问时被捐赠。$c_i$ 大的会优先捐赠。那么我们大概是这样捐赠的：首先选一个点 $u$，假设删掉 $u$ 后形成了 $tot$ 个连通块，则先捐赠掉 $tot-1$ 个，然后捐赠 $...
POI2012 简要题解
Festival考虑差分约束。设 $dis_{i,j}$ 表示 $X_i$ 至多比 $X_j$ 大多少，则若 $X_i+1=X_j$，则 $dis_{i,j}=-1,dis_{j,i}=1$，连边 $(i,j,-1)$ 和 $(j,i,1)$。若 $X_i\leq X_j$，则 $dis_{i,j}=0$，连边 $(i,j,0)$。考虑无解的情况。一种情况是出现负环，另一种情况是出现一个全是...
洛谷4119 [Ynoi2018]未来日记
Luogu分析先考虑没有修改怎么用分块做。一个想法是将序列分块，然后维护 $s_{i,j}$ 表示前 $i$ 块中 $j$ 的数量，然而这样子查询是 $\mathcal{O}(n)$ 的。因此我们再对值域分块，并再维护 $s'_{i,j}$ 表示前 $i$ 块中值在第 $j$ 块中的数的数量，询问时先把所求在值域的哪一块中求出来，再在这一块中求，复杂度 $\mathcal{O}(\sqrt{...
洛谷4117 [Ynoi2018]五彩斑斓的世界
Luogu分析考虑分块。对于每一块，维护它的最大值 $mx$。可以发现 $\sum mx$ 是 $\mathcal{O}(n\sqrt{n})$ 级别的，因此每一块如果能够 $\mathcal{O}(x)$ 修改的话复杂度就是 $\mathcal{O}(n\sqrt{n})$。可以想到这样的修改方式如果 $2x\geq mx$，则直接将所有 $>x$ 的数减去 $mx$。这样子是 $\...