原创 题目大意为给出n个人，编号为1-n，给出m对亲戚关系，然后指定两个人，问他们是否为亲戚。 若a和b是亲戚，b和c是亲戚，则a和c是亲戚；若a和b是亲戚，则a的亲戚和b的亲戚都互成为亲戚。 例如： 5 2 2 5（表明有5个人，存在如下2对亲戚关系，问2和5是否为亲戚） 1 3 2 4 输出 N ...

题目：分析：并查集。我用python写的，1.创建一个二维列表，然后每个列表中的元素都只有一个，为每个名字。2.查synonyms，匹配的名字对应的列表合并。3.排序，求和。竟然超时了，这道题拖了10天，答案也不好，放弃了。代码：def trulyMostPopular(self, names: List[str], synonyms: List[str]) -> List[str]: # 首先为每一个名字创建一个列表 m = {} l2 = [[]for

描述 布置宴席最微妙的事情，就是给前来参宴的各位宾客安排座位。无论如何，总不能把两个死对头排到同一张宴会桌旁！这个艰巨任务现在就交给你，对任何一对客人，请编写程序告诉主人他们是否能被安排同席。 布置宴席最微妙的事情，就是给前来参宴的各位宾客安排座位。无论如何，总不能把两个死对头排到同一张宴会桌旁！这 ...

内存限制：256 MiB 时间限制：2000 ms 标准输入输出 题目类型：传统 评测方式：文本比较 上传者： 匿名 【题目描述】 这是一道模板题。 维护一个 nnn 点的无向图，支持： 加入一条连接 uuu 和 vvv 的无向边 查询 uuu 和 vvv 的连通性 由于本题数据较大，因此输出的时候 ...

题意 题目链接 $n$个人，每个人可以在第$a_i$天或第$b_i$，一天最多考一场试，问在最优的情况下，最晚什么时候结束 Sol 自己只能想到暴力匈牙利二分图匹配，然而还是被构造数据卡了。。 标算很神奇。 同样考虑把题目中给出的模型建成二分图，左侧代表每个人，右侧代表每一天的考试 然后我们把右侧每 ...

题意 "题目链接" Sol 感觉自己已经老的爬不动了。。 想了一会儿，大概用个不删除莫队+带撤销并查集就能搞了吧，$n \sqrt{n} logn$应该卡的过去 不过不删除莫队咋写来着？。。。。跑去学。。 带撤销并查集咋写来着？。。。。跑去学。。。 发现自己的带撤销并查集是错的，，自己yy着调了1h ...

思路：注意，行数是无限的，因此，两个人可以同时都相距另一个人x远（相距x列， 不在同一行），也就是说， 出现矛盾的唯一地方就是在于， 现在说的两个人相距的距离和之前说的矛盾。 那么

题意 "题目链接" Sol 神仙题啊Orzzzzzz 考场上的时候直接把树扔了对着式子想，想1h都没得到啥有用的结论。 然后cf正解居然是网络流？？出给NOIP模拟赛T1？？？￥%……&（（……%&（（ 说一下非网络流解法吧。 首先题目中给出的$g(i, p_i)$我们可以认为是对于每个节点$i$， ...

题意 "题目链接" 给出一张带权无向图，每次询问$(u, v)$之间是否存在一条路径满足$max(a) = A, max(b) = B$ Sol 这题居然是分块。。想不到想不到。。做这题的心路历程大概可以写个800字的作文。 $warning:$下面的做法复杂度是错的。但是可以过 以下是attack ...

推荐题目： "P3367 【模板】并查集" 。 该题的缺点：~~数据不够水~~。 本蒟蒻实在是太弱了，不会！ 推荐一篇文章： "浅谈并查集优化" 。 Code： cpp include include include include include include using namespace s ...

D - Forest Time limit: 2sec /Memory limit: 256MB Score :600points Problem Statement You

题目背景 “柴门闻犬吠，风雪夜归人”，冬天，不期而至。千里冰封，万里雪飘。空中刮起了鸭毛大雪。雪花纷纷，降落人间。 美能量星球（pty 在 spore 上的一个殖民地）上的人们被这美景所震撼。但是 pty 却不高兴，他不喜欢白色的世界，他觉得这样太单调了。所以他想对雪花进行染色，让世界变得多彩些。 ...

题意 题目链接 一张图，n个点，m条边，每个点有个权值x，x

题目链接思路：按照权值从大到小排序，然后依次加入，并把全场的权值都减到当前权值。用并查集维护连通块的总个数即可。代码：#includeusing namespace std;#define int long long#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);const int N=1e5+7;const int M=4e5+8;const double eps=1

题意 给你一张无向图，保证从1号点到每个点的最短路唯一。对于每个点求出删掉号点到它的最短路上的最后一条边(就是这条路径上与他自己相连的那条边)后1号点到它的最短路的长度 Sol emmm，考场上想了个贪心开心的飞起然而只多得了10分qwq 正解比较神仙。 首先把最短路树建出来，考虑一条非树边$(u, ...

题意 有n次询问，给出a到b区间的总和，问这n次给出的总和中有几次是和前面已近给出的是矛盾的。 思路 sum[x]表示x到区间末尾的总和 则a到b的总和c 可以表示为sum[a]-sum[b+

之前在CSDN看到一篇很受欢迎的讲解并查集的博文，其中自然用到了路径压缩： 你也许会发现问题了，find函数的实现是： 首先找节点x的根节点root，再基于x进行向上的路径压缩。 这其实完全可以合为一个操作，用到了递归，效率相当高： OVER ...

Description 给你一个无向图，N(N