ZigZagK的博客
[离散+线段树分治+并查集按秩合并]2020 ICPC 小米 网络选拔赛热身赛 E【Explorer】题解
题目概述有 $m$ 条边,每条双向边 $(x_i,y_i)$ 只有人数在 $[l_i,r_i]$ 时才能通过,如果人数 $x$ 能够从 $1$ 到 $n$ 则可行,求可行的 $x$ 的数量。解题...
[并查集]洛谷6786【GCDs & LCMs】题解
题目概述洛谷6786解题报告假设 $(b_i,b_j)=A,b_i=BA,b_j=CA(C>B)$ ,然后推式子:$$ BA+CA+A={BA\cdot CA\over A}\\ BA+C...
[离线+并查集按秩合并+平衡树启发式合并]Codeforces1417F【Graph and Queries】题解
题目概述CF1417F解题报告超级套路题……任意无向图删边是很麻烦的,所以肯定考虑离线转换成加边然后回退。加边就可以利用并查集来进行合并,考虑用set维护一个块的最大值,并查集合并的时候set启...
数据结构水题选讲(By AwD)部分题解
课件链接Problem A考虑莫队之后在移动指针时怎么维护第 $K$ 大值。带 $log$ 大概会GG。由于答案在 $[1,n+K]$ 范围内,所以可以把值域也分块,这样移动指针就不需要带 $l...
[倍增+并查集+贪心]Codeforces1059E【Split the Tree】题解
题目概述把一棵有权值的树分成若干条儿子到祖先的路径,每条路径节点个数不能超过 $L$ ,节点权值和不能超过 $S$ ,问最少分成多少路径。解题报告一个不知道正确性的解法,大佬可以来证明或者证伪一...
[思维+并查集]Codeforces1013D【Chemical table】题解
题目概述如果存在 $(r_1,c_1),(r_2,c_2),(r_2,c_1),r_1\not=r_2,c_1\not=c_2$ 那么就可以不消耗费用添加 $(r_2,c_2)$ 。现在 $n\...
[转化+并查集]Codeforces1027F【Session in BSU】题解
题目概述有 $n$ 场考试,第 $i$ 场考试可以在 $a_i,b_i$ 两天中的一天完成,问至少什么时候能考完所有试,无解输出 $-1$ 。解题报告我图样图森破,以为是神仙贪心,结果是转化思维...