并查集 - Page 2

「codechef」April Challenge 2015
BROKPHON模拟[crayon-6628418629b1d577970430/]CHEFLCM所有约数和[crayon-6628418629b27904410242/]PIANO1暴力TT[crayon-6628418629b2a092789966/]CSEQl~r之间每个数的使用次数当作一个变量。。那么就相当于求方程组sigma(xi)(l<=i<=r)=n的非负整数解数。。然后就是排列组合求和[crayon-6628418629b2f388674921/]CARLOS先用并查集将能够相互转化的并在一起dpf(i,j)表示前i个末尾为j的最小改...
22015年4月12日4,475模拟,递推与动规,ST表,并查集,排列组合,乘法逆元

「codechef」March Challenge 2015
只做了前6题弃疗了感觉codechef写题解也没啥人看……「codechefCNOTE」ChefandNotebooks纯模拟[crayon-662841862a455809373414/]「codechefSIGNWAVE」SignWave听说此题打表可以找规律。。引用zld神犇的话吧。。。就是若干个余弦函数的零点均不同。。然后sin函数的分布就十分奇怪了。。比如s=3的时候就是312131213，忽略两端的情况。。就变成非常规则的1213121然后我们再考虑余弦函数当c=2的时候分布就是011101110...
02015年3月17日3,219模拟,并查集,二分法,离线处理
「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日4,292并查集,置换
「BZOJ1370」[Baltic2003] Gang团伙
Description在某城市里住着n个人，任何两个认识的人不是朋友就是敌人，而且满足：1、我朋友的朋友是我的朋友；2、我敌人的敌人是我的朋友；所有是朋友的人组成一个团伙。告诉你关于这n个人的m条信息，即某两个人是朋友，或者某两个人是敌人，请你编写一个程序，计算出这个城市最多可能有多少个团伙？Input第1行为n和m，N小于1000,M小于5000；以下m行，每行为pxy，p的值为0或1，p为0时，表示x和y是朋友，p为1时，表示x和y是敌人...
22015年1月20日5,698并查集
「CF506B」Mr. Kitayuta’s Technology
ShusekiKingdomistheworld'sleadingnationforinnovationandtechnology.Therearencitiesinthekingdom,numberedfrom1ton.ThankstoMr.Kitayuta'sresearch,ithasfinallybecomepossibletoconstructteleportationpipesbetweentwocities.Ateleportationpipewillconnecttwocitiesunidirectionally,thatis,ateleportationpipefromcityxtocityycannotbeusedtotravelfromcityytocityx.Thetransportationwithineachcityisextremelydeve...
02015年1月19日4,911并查集,图的连通
「CF500E」New Year Domino
Celebratingthenewyear,manypeoplepostvideosoffallingdominoes;Here'salistofthem:https://www.youtube.com/results?search_query=New+Years+DominosUserainta,wholivesina2Dworld,isgoingtopostavideoaswell.Therearendominoesona2DCartesianplane.i-thdomino(1 ≤ i ≤ n)canberepresentedasalinesegmentwhichisparalleltothey-axisandwhoselengthisli.Thelowerpointofthedominoisonthex-axis.Let'sdenotethex-...
02014年12月31日4,954并查集
「CF500B」New Year Permutation
Useraintahasapermutationp1, p2, ..., pn.AstheNewYeariscoming,hewantstomakehispermutationasprettyaspossible.Permutationa1, a2, ..., anisprettierthanpermutationb1, b2, ..., bn,ifandonlyifthereexistsanintegerk(1 ≤ k ≤ n)wherea1 = b1, a2 = b2, ..., ak - 1 = bk - 1andak < bkallholds.Asknown,permutationpissosensitivethatitcouldbeonlymodifiedbyswappingtwodistinctele...
02014年12月31日3,400贪心,并查集
「泉七培训 – 刘定峰」链型网络
题意给定一张无重边，自环的无向图每次可以加边，或者询问有多少个点满足将该点删除后，原图的每个连通块都为一条链数据范围30%的数据n<=100m<=2n100%的数据n<=100000,m<=2n 题解30分很简单对于每次询问枚举删去每一个点，然后再用O（n）的时间在图上判环以及度数是否都小等于2 然后正解。。。考虑以下一些简单的情况原图为若干条链，则答案为点数N原图为单个简单环加若干条链，则答案为环大小原图中...
02014年12月26日4,360深度搜索,并查集
「NOIP模拟赛」感冒病毒
「题目描述」一种感冒病毒正在学校里传播，这所学校有n个学生，m个学生社团，每个学生可能参加了多个社团，因为同一个社团的学生交流较多，所以如果一个学生感染上感冒病毒，那么他所在的社团里的所有学生都会感染上感冒病毒，现在已知0号学生感染上感冒病毒，问现在有多少人会感染上感冒病毒。「输入」输入文件：suspects.in输入的第一行是两个整数n和m，表示学生的数目和社团的数目,学生的编号为0到n-1。接下来m行，每行首先是一...
02014年11月4日2,518并查集
「NOIP模拟赛」Hzwer的陨石
题目描述：经过不懈的努力，Hzwer召唤了很多陨石。已知Hzwer的地图上共有n个区域，且一开始的时候第i个陨石掉在了第i个区域。有电力喷射背包的ndsf很自豪，他认为搬陨石很容易，所以他将一些区域的陨石全搬到了另外一些区域。在ndsf愉快的搬运过程中，Hzwer想知道一些陨石的信息。对于Hzwer询问的每个陨石i，你必须告诉他，在当前这个时候，i号陨石在所在区域x、x区域共有的陨石数y、以及i号陨石被搬运的次数z。输入描述：输入...
02014年10月31日2,598并查集
「泉七培训 – 郑予凡」雷神领域
此题数据水，各种骗分。。。二维偏序最长链，两个方向最小值40分。。。直接统计不同的x，y坐标个数输出最小值70分。。。正解似乎比较奇怪。。。懒得解释了[crayon-6628418644978019331508/] ...
12014年6月21日2,633并查集
「codechefCHSEQ22」Chef and Favourite Sequence
Allsubmissionsforthisproblemareavailable.Readproblemsstatementsin MandarinChinese and Russian.Chefhasanintegersequence a1, a2,..., aN ofsize N,wherealltheelementsofthesequenceare 0initially.Chefalsohas M segments,herethe ith oneis [Li,Ri].Hewantstocreatenewsequencesusingthefollowingoperation:Inasingleoperation,hepicksasegmentfromthe M segments.Letthechosensegmentbe ...
02014年6月13日826并查集