并查集 - hzwer.com

2017ACM萧山训练第4场(CTUO 2015)
D.FalconDive计算左下角的像素移动的距离，直接模拟[crayon-5d35c8848a7a5102205696/]F.TheFoxandtheOwl贪心如果n是负数，找n最低的非9的位加1考虑在n的某一个高位减1，在之后的低位中加2如果存在多个满足的高位，取最低的一个若不存在，构造一个绝对值最小的负数[crayon-5d35c8848a7b6738889418/]J.JumpingYoshi两个点连边的条件是\(d_y-d_x=a_y+a_x,y>x\)由于点对不超过10^6，扫一遍用map维护，把所有的边用并查集连...
02017年8月10日3,108模拟,贪心,STL,构造,并查集

FJ2016集训 day5
打了个酱油，身败名裂0。01冷战1.1题目大意给定一副N个点的图。动态的往图中加边，并且询问某两个点最早什么时候联通。1.2题解考虑并查集。并查集实际上维护了一棵树。那么假如我们按秩合并，这棵树的深度是O(logn)的。我们将一个点连向其父亲的边权设为这条边加入的时间，那么每次询问时，暴力查询树上从u到v所经过边权的最大值即可。时间复杂度为O(nlogn)，常数较小。假如写了常数较大的可以得到80分。[crayon-5d35c8848bc658...
42016年7月7日2,118并查集
NOI2008假面舞会
Description一年一度的假面舞会又开始了，栋栋也兴致勃勃的参加了今年的舞会。今年的面具都是主办方特别定制的。每个参加舞会的人都可以在入场时选择一个自己喜欢的面具。每个面具都有一个编号，主办方会把此编号告诉拿该面具的人。为了使舞会更有神秘感，主办方把面具分为k(k≥3)类，并使用特殊的技术将每个面具的编号标在了面具上，只有戴第i类面具的人才能看到戴第i+1类面具的人的编号，戴第k类面具的人能看到戴第1类面具的人的...
12015年6月29日2,407深度搜索,并查集
「CF325X」MemSQL start[c] up Round 1
A.SquareandRectangles模拟题[crayon-5d35c8848cd49299098401/]B.StadiumandGames\[(2^k-1)m+m(m-1)/2=n\]枚举k二分得出m[crayon-5d35c8848cd52259813278/]C.MonstersandDiamonds此题比较恶心QAQ求最短用个类似dijkstra的东西，如果一种u->{v}的转移所有mn[v]都确定了，把这个转移放进堆或者是某个转移的代价被更新了求最长用记忆化搜索，走出环就是inf[crayon-5d35c8848cd57988125309/]D.Reclamation把图扩展成r...
12015年6月16日1,595STL,深度搜索,并查集,二分法,记忆化搜索
POJ训练记录2
3613.CowRelays求经过n条边的最短路，floyd+倍增QAQ[crayon-5d35c8848d736275769758/]2728.DesertKing最优比率生成树分数规划[crayon-5d35c8848d749411007388/]1639.PicnicPlanning带度数限制的最小生成树http://wenku.baidu.com/link?url=UKcnK1pZvaVwypQOrIFRTOPzM4edIlBmqvnZjZipGf2o_6u-aB1F2tFsMGdUQbA1O-96menmbgyxNoSoWKWBeJnr-RJKuG2yM4b6Jf7IvR3[crayon-5d35c8848d7...
02015年5月17日2,519STL,贪心,prim,二分法,floyd,树形动规,并查集,2-SAT
PKUSC 2013 #1
poj2245.Lotto裸搜索[crayon-5d35c8848defa225383845/]poj2601.Simplecalculations推公式麻烦。。直接二分[crayon-5d35c8848df04228652187/]poj1635.Subwaytreesystems树的同构，哈希[crayon-5d35c8848df09363291439/]poj2419.Forests暴力即可[crayon-5d35c8848df11211631069/]poj1717.Dominoesdp水题[crayon-5d35c8848df1c432242267/]poj2949.WordRings建图+分数规划[crayon-5d35c8848df27536817549/] ...
02015年5月14日1,638递推与动规,spfa,深度搜索,二分法,并查集,哈希表
「BZOJ3624」[Apio2008] 免费道路
DescriptionInputOutputSampleInput572130451320531430121421 SampleOutput320430531121题解优先加1做生成树，得出必须添加的0的边反过来，将0的边加至K条，再放1的边[crayon-5d35c8848e556795819671/] ...
02015年4月24日3,013贪心,并查集
「BZOJ2303」[Apio2011] 方格染色
DescriptionSam和他的妹妹Sara有一个包含n×m个方格的表格。她们想要将其的每个方格都染成红色或蓝色。出于个人喜好，他们想要表格中每个2× 2的方形区域都包含奇数个（1个或3个）红色方格。例如，右图是一个合法的表格染色方案（在打印稿中，深色代表蓝色，浅色代表红色）。可是昨天晚上，有人已经给表格中的一些方格染上了颜色！现在Sam和Sara非常生气。不过，他们想要知道是否可能给剩下的方格染上颜色，使得整个表格仍...
12015年4月14日3,319并查集
UOJ Easy Round #1
http://vfleaking.blog.uoj.ac/blog/15uoj题解写的太好了。。。「UER#1」猜数[crayon-5d35c8848f047293564747/]「UER#1」跳蚤OS[crayon-5d35c8848f059293877891/]「UER#1」DZYLovesGraph[crayon-5d35c8848f064368575053/] ...
02015年4月13日2,990并查集,AC自动机
「codechef」April Challenge 2015
BROKPHON模拟[crayon-5d35c8848f68a158702618/]CHEFLCM所有约数和[crayon-5d35c8848f693331864894/]PIANO1暴力TT[crayon-5d35c8848f698338028692/]CSEQl~r之间每个数的使用次数当作一个变量。。那么就相当于求方程组sigma(xi)(l<=i<=r)=n的非负整数解数。。然后就是排列组合求和[crayon-5d35c8848f69b489365495/]CARLOS先用并查集将能够相互转化的并在一起dpf(i,j)表示前i个末尾为j的最小改...
22015年4月12日1,760递推与动规,模拟,ST表,并查集,排列组合,乘法逆元
「codechef」March Challenge 2015
只做了前6题弃疗了感觉codechef写题解也没啥人看……「codechefCNOTE」ChefandNotebooks纯模拟[crayon-5d35c8849c047900130372/]「codechefSIGNWAVE」SignWave听说此题打表可以找规律。。引用zld神犇的话吧。。。就是若干个余弦函数的零点均不同。。然后sin函数的分布就十分奇怪了。。比如s=3的时候就是312131213，忽略两端的情况。。就变成非常规则的1213121然后我们再考虑余弦函数当c=2的时候分布就是011101110...
02015年3月17日1,530模拟,二分法,并查集,离线处理
「BZOJ1998」[HNOI2010] Fsk物品调度
Description现在找工作不容易，Lostmonkey费了好大劲才得到fsk公司基层流水线操作员的职位。流水线上有n个位置，从0到n-1依次编号，一开始0号位置空，其它的位置i上有编号为i的盒子。Lostmonkey要按照以下规则重新排列这些盒子。规则由5个数描述，q，p，m，d，s，s表示空位的最终位置。首先生成一个序列c，c0=0，ci+1=(ci*q+p)modm。接下来从第一个盒子开始依次生成每个盒子的最终位置posi，posi=(ci+d*xi+yi)modn，xi,yi是为了...
02015年1月31日2,334并查集,置换