并查集 - hzwer.com

PKU2019数据结构与算法实习期末考试
http://dapractise.openjudge.cn/2019finalexam2/排队[crayon-6767abf4c722c311323914/]树状数组过线段树不过[crayon-6767abf4c7238800488671/]线段树求最大数[crayon-6767abf4c723d675002360/]关键词搜索[crayon-6767abf4c7242692907869/]旅行最短路[crayon-6767abf4c7249286367467/]强连通分量[crayon-6767abf4c7250103920814/]统计不同子串[crayon-6767abf4c7257227736653/]匹配网络流模板[crayon-6767abf4c7263254132055/]线性...
02019年12月30日12,004凸包,dijkstra,线段树,并查集,树状数组,图的连通,网络流

PKU2019数据结构与算法实习模板
本文包括：并查集最短路强连通分量线段树AC自动机(Trie)网络流后缀数组POJ1182食物链如果并查集中X向Y连边长为1的边，代表X吃Y这题如果用按秩合并并查集比较好想，带路径压缩的话，需要考虑重新连边的时候，边权的设置[crayon-6767abf4c86ae867337563/]POJ1860CurrencyExchange最短路模板[crayon-6767abf4c86b9415986471/]POJ2186PopularCows如果X喜欢Y，Y向X连边。缩点以后，计算每个强连通块的入度，唯一...
02019年12月29日5,641spfa,STL,后缀数组,并查集,线段树,图的连通
「CF1209X」Codeforces Round #584
A.PainttheNumbers从小到大排序以后，每次贪心的把能被最小元素整除的划分到一起[crayon-6767abf4c8e19416682577/]B.KoalaandLights因为ab都很小，枚举时间，暴力模拟灯的开关[crayon-6767abf4c8e26817946658/]C.PainttheDigits枚举一下染色成1的最大值x，则比x小的都染色成1，再从右往左，直到第一个比x小的元素出现之前，把所有等于x的元素染色成1剩下的全染色成2，check一下是否合法[crayon-6767abf4c8e2e895799222/]D...
32019年9月16日3,926贪心,并查集
2017ACM萧山训练第4场(CTUO 2015)
D.FalconDive计算左下角的像素移动的距离，直接模拟[crayon-6767abf4c98f4881824780/]F.TheFoxandtheOwl贪心如果n是负数，找n最低的非9的位加1考虑在n的某一个高位减1，在之后的低位中加2如果存在多个满足的高位，取最低的一个若不存在，构造一个绝对值最小的负数[crayon-6767abf4c98ff843421953/]J.JumpingYoshi两个点连边的条件是\(d_y-d_x=a_y+a_x,y>x\)由于点对不超过10^6，扫一遍用map维护，把所有的边用并查集连...
02017年8月10日8,358模拟,STL,贪心,构造,并查集
FJ2016集训 day5
打了个酱油，身败名裂0。01冷战1.1题目大意给定一副N个点的图。动态的往图中加边，并且询问某两个点最早什么时候联通。1.2题解考虑并查集。并查集实际上维护了一棵树。那么假如我们按秩合并，这棵树的深度是O(logn)的。我们将一个点连向其父亲的边权设为这条边加入的时间，那么每次询问时，暴力查询树上从u到v所经过边权的最大值即可。时间复杂度为O(nlogn)，常数较小。假如写了常数较大的可以得到80分。[crayon-6767abf4c9ee07...
42016年7月7日4,803并查集
NOI2008假面舞会
Description一年一度的假面舞会又开始了，栋栋也兴致勃勃的参加了今年的舞会。今年的面具都是主办方特别定制的。每个参加舞会的人都可以在入场时选择一个自己喜欢的面具。每个面具都有一个编号，主办方会把此编号告诉拿该面具的人。为了使舞会更有神秘感，主办方把面具分为k(k≥3)类，并使用特殊的技术将每个面具的编号标在了面具上，只有戴第i类面具的人才能看到戴第i+1类面具的人的编号，戴第k类面具的人能看到戴第1类面具的人的...
12015年6月29日6,475深度搜索,并查集
「CF325X」MemSQL start[c] up Round 1
A.SquareandRectangles模拟题[crayon-6767abf4caeaa256090916/]B.StadiumandGames\[(2^k-1)m+m(m-1)/2=n\]枚举k二分得出m[crayon-6767abf4caeb3704855461/]C.MonstersandDiamonds此题比较恶心QAQ求最短用个类似dijkstra的东西，如果一种u->{v}的转移所有mn[v]都确定了，把这个转移放进堆或者是某个转移的代价被更新了求最长用记忆化搜索，走出环就是inf[crayon-6767abf4caeb8612202558/]D.Reclamation把图扩展成r...
12015年6月16日3,799STL,深度搜索,二分法,并查集,记忆化搜索
POJ训练记录2
3613.CowRelays求经过n条边的最短路，floyd+倍增QAQ[crayon-6767abf4cb9cb516183436/]2728.DesertKing最优比率生成树分数规划[crayon-6767abf4cb9dc482569569/]1639.PicnicPlanning带度数限制的最小生成树http://wenku.baidu.com/link?url=UKcnK1pZvaVwypQOrIFRTOPzM4edIlBmqvnZjZipGf2o_6u-aB1F2tFsMGdUQbA1O-96menmbgyxNoSoWKWBeJnr-RJKuG2yM4b6Jf7IvR3[crayon-6767abf4cb9...
02015年5月17日6,651STL,贪心,prim,树形动规,并查集,floyd,二分法,2-SAT
PKUSC 2013 #1
poj2245.Lotto裸搜索[crayon-6767abf4cc2b7602627408/]poj2601.Simplecalculations推公式麻烦。。直接二分[crayon-6767abf4cc2c6254859778/]poj1635.Subwaytreesystems树的同构，哈希[crayon-6767abf4cc2cf186538557/]poj2419.Forests暴力即可[crayon-6767abf4cc2d8244231337/]poj1717.Dominoesdp水题[crayon-6767abf4cc2e3600482198/]poj2949.WordRings建图+分数规划[crayon-6767abf4cc2ef784498181/] ...
02015年5月14日4,058递推与动规,spfa,深度搜索,并查集,二分法,哈希表
「BZOJ3624」[Apio2008] 免费道路
DescriptionInputOutputSampleInput572130451320531430121421 SampleOutput320430531121题解优先加1做生成树，得出必须添加的0的边反过来，将0的边加至K条，再放1的边[crayon-6767abf4cc8cd517582381/] ...
02015年4月24日5,383贪心,并查集
「BZOJ2303」[Apio2011] 方格染色
DescriptionSam和他的妹妹Sara有一个包含n×m个方格的表格。她们想要将其的每个方格都染成红色或蓝色。出于个人喜好，他们想要表格中每个2× 2的方形区域都包含奇数个（1个或3个）红色方格。例如，右图是一个合法的表格染色方案（在打印稿中，深色代表蓝色，浅色代表红色）。可是昨天晚上，有人已经给表格中的一些方格染上了颜色！现在Sam和Sara非常生气。不过，他们想要知道是否可能给剩下的方格染上颜色，使得整个表格仍...
12015年4月14日7,472并查集
UOJ Easy Round #1
http://vfleaking.blog.uoj.ac/blog/15uoj题解写的太好了。。。「UER#1」猜数[crayon-6767abf4e6b87467491267/]「UER#1」跳蚤OS[crayon-6767abf4e6b8f372176436/]「UER#1」DZYLovesGraph[crayon-6767abf4e6b95899939565/] ...
02015年4月13日6,793并查集,AC自动机