标签 - 并查集

? 解题记录 ? ? 洛谷 ? ? 并查集 ?    2018-10-21 15:05:05    461    0    0
题目描述lxhgww最近迷上了一款游戏,在游戏里,他拥有很多的装备,每种装备都有2个属性,这些属性的值用[1,10000]之间的数表示。当他使用某种装备时,他只能使用该装备的某一个属性。并且每种装备最多只能使用一次。游戏进行到最后,lxhgww遇到了终极boss,这个终极boss很奇怪,攻击他的装备所使用的属性值必须从1开始连续递增地攻击,才能对boss产生伤害。也就是说一开始的时候,lxhgww只能使用某个属性值为1的装备攻击boss,然后只能使用某个属性值为2的装备攻击boss,然后只能使用某个属性值为3的装备攻击boss……以此类推。现在lxhgww想知道他最多能连续攻击boss多少次?
? 解题记录 ? ? BZOJ ? ? 并查集 ? ? 线段树 ? ? Kruscal ?    2018-09-25 08:06:17    338    0    0
Description在Byteland一共有n个城市,编号依次为1到n,它们之间计划修建m条双向道路,其中修建第i条道路的费用为ci。B yteasar作为Byteland公路建设项目的总工程师,他决定选定一个区间[l,r],仅使用编号在该区间内的道路。他希 望选择一些道路去修建,使得连通块的个数尽量少,同时,他不喜欢修建多余的道路,因此每个连通块都可以看成 一棵树的结构。为了选出最佳的区间, Byteasar会不断选择 q个区间,请写一个程序,帮助 Byteasar计算每个区 间内修建公路的最小总费用。  Input第一行包含三个正整数n; m; q,表示城市数、道路数和询问数
? 解题记录 ? ? Atcoder ? ? 堆 ? ? 贪心 ? ? 并查集 ?    2018-07-15 10:47:36    1100    0    0
Problem StatementSnuke has a rooted tree with N vertices, numbered 1 through N. Vertex 1 is the root of the tree, and the parent of Vertex i ( 2≤i≤N ) is Vertex Pi ( Pi<i ). There is a number, 0 or 1, writte
? 解题记录 ? ? Codeforces ? ? 并查集 ?    2018-07-10 17:52:07    414    0    0
For long time scientists study the behavior of sharks. Sharks, as many other species, alternate short movements in a certain location and long movements between locations. Max is a young biologist. For n" data-mce-tabindex="0">nn days he watched a specific shark, and now he knows the di
? 解题记录 ? ? BZOJ ? ? 并查集 ? ? 分治 ? ? 线段树分治 ?    2018-05-21 18:10:14    706    0    0
【题目描述】神犇有一个n个节点的图。因为神犇是神犇,所以在T时间内一些边会出现后消失。神犇要求出每一时间段内这个图是否是二分图。这么简单的问题神犇当然会做了,于是他想考考你。   【输入】输入数据的第一行是三个整数n,m,T。 第2行到第m+1行,每行4个整数u,v,start,end。第i+1行的四个整数表示第i条边连接u,v两个点,这条边在start时刻出现,在第end时刻消失。     【输出】输出包含T行。在第i行中,如果第i时间段内这个图是二分图,那么输出“Yes”,否则输出“No”,不含引号。     【输入样例】3 3&
? 解题记录 ? ? 洛谷 ? ? 线段树 ? ? 并查集 ?    2018-05-04 19:06:46    396    1    1
题目描述佳佳有一个 n 行 n 列的黑白棋盘,每个格子都有两面,一面白色,一面黑色。佳佳把棋盘平放在桌子上,因此每个格子恰好一面朝上,如下图所示: 我们把每行从上到下编号为 1 , 2 , 3 ,……, n ,各列从左到右编号为 1 , 2 , 3 ,……, n ,则每个格子可以用棋盘坐标 (x, y)表示。在上图中,有 8 个格子黑色朝上,另外 17&n
? 解题记录 ? ? HDU ? ? 并查集 ? ? 倍增 ? ? 补档计划第一期 ?    2018-01-28 11:12:33    360    0    0
  After World War X, a lot of cities have been seriously damaged, and we need to rebuild those cities. However, some materials needed can only be produced in certain places. So we need to transport these materials from city to city. For most of roads had been totally destroyed during the war, t
? 解题记录 ? ? BZOJ ? ? 并查集 ? ? 贪心 ? ? 补档计划第一期 ?    2018-01-28 10:59:43    442    0    0
Description聪聪研究发现,荒岛野人总是过着群居的生活,但是,并不是整个荒岛上的所有野人都属于同一个部落,野人们总是拉帮结派形成属于自己的部落,不同的部落之间则经常发生争斗。只是,这一切都成为谜团了——聪聪根本就不知道部落究竟是如何分布的。 不过好消息是,聪聪得到了一份荒岛的地图。地图上标注了N个野人居住的地点(可以看作是平面上的坐标)。我们知道,同一个部落的野人总是生活在附近。我们把两个部落的距离,定义为部落中距离最近的那两个居住点的距离。聪聪还获得了一个有意义的信息——这些野人总共被分为了K个部落!这真是个好消息。聪聪希望从这些信息里挖掘出所有部落的详细信息。他正在尝试这样一种算法
? 解题记录 ? ? 洛谷 ? ? 并查集 ?    2017-10-30 23:25:42    209    0    0
题目描述很久以前,在一个遥远的星系,一个黑暗的帝国靠着它的超级武器统治者整个星系。某一天,凭着一个偶然的机遇,一支反抗军摧毁了帝国的超级武器,并攻下了星系中几乎所有的星球。这些星球通过特殊的以太隧道互相直接或间接地连接。 但好景不长,很快帝国又重新造出了他的超级武器。凭借这超级武器的力量,帝国开始有计划地摧毁反抗军占领的星球。由于星球的不断被摧毁,两个星球之间的通讯通道也开始不可靠起来。现在,反抗军首领交给你一个任务:给出原来两个星球之间的以太隧道连通情况以及帝国打击的星球顺序,以尽量快的速度求出每一次打击之后反抗军占据的星球的连通快的个数。(如果两个星球可以通过现存的以太通道直接或间接地连通
? 解题记录 ? ? 洛谷 ? ? 并查集 ?    2017-07-25 17:24:39    458    0    0
题目描述S 城现有两座监狱,一共关押着N 名罪犯,编号分别为1~N。他们之间的关系自然也极不和谐。很多罪犯之间甚至积怨已久,如果客观条件具备则随时可能爆发冲突。我们用“怨气值”(一个正整数值)来表示某两名罪犯之间的仇恨程度,怨气值越大,则这两名罪犯之间的积怨越多。如果两名怨气值为c 的罪犯被关押在同一监狱,他们俩之间会发生摩擦,并造成影响力为c 的冲突事件。 每年年末,警察局会将本年内监狱中的所有冲突事件按影响力从大到小排成一个列表,然后上报到S 城Z 市长那里。公务繁忙的Z 市长只会去看列表中的第一个事件的影响力,如果影响很坏,他就会考虑撤换警察局长。 在详细考察了N 名罪犯间的矛盾关系后,