sunny_forever

分类

题解(57)

/ 注册

全部文章（共9篇）

题解 | #程序自动分析#

并查集 + 离散化思路离散化之后，先执行 op = 1 的，再执行 op = 0 的执行 op = 1 的时：直接合并执行 op = 0 的时：进行判断Code #include <bits/stdc++.h> using namespace std; const int N...

并查集离散化

2021-08-08

0 715

题解 | #[JSOI2008]星球大战STARWAR#

并查集 + 邻接表 + 逆向思维逆向思维: 原题意：共要删除 k 个点，问：每次删除过后，连通块个数是多少？逆向思维：删点 ==> 加点、连边对！没错，变成了加点与连边所以最开始，我们只对 n-k 个点进行合并操作就行，然后枚举每个要删除的点（注意是从后向前枚举）对于每个枚举到...

并查集邻接表

2021-08-07

3 579

题解 | #食物链#

法1：三倍空间，种类并查集类似于：https://ac.nowcoder.com/acm/problem/16591 Code #include <bits/stdc++.h> using namespace std; const int N = 3e5; int fa[N]; ...

并查集

2021-08-06

4 458

题解 | #[USACO 2018 Jan G]MooTube#

并查集思路：对于每次询问，我们找出所有边权 >=k 的边，对于每个找出的边，对其两端的点进行合并操作，最后 v点所在联通块所含的点的数目减一(减去自身) 就是本次询问的答案但因为数据过大，每次询问我们都将所有边权>=k 的边找出来对其两端点进行合并操作的话，会超时而且还会有...

并查集

2021-08-06

1 480

题解 | #[NOIP2010]关押罪犯#

思路 M 对互相仇恨的罪犯，我们按仇恨值从大到小排序，对于每一对互相仇恨的罪犯，我们要设法将他们分配在不同的监狱里，反正不能在同一监狱里如果不可避免的在同一监狱了也就是与我们的策略发生冲突了，那么此时的仇恨值就是答案如果到最后都不曾发生冲突，那么答案是 0，因为此时：任意一对会冲突的罪犯都...

并查集

2021-08-06

2 821

题解 | #DongDong认亲戚#

并查集 + map Code #include <bits/stdc++.h> using namespace std; const int N = 20010; unordered_map<string,string>fa; int n,m; string find...

map 并查集

2021-08-05

5 428

题解 | #B-经商#

思路 01 背包 + 并查集 Code #include <bits/stdc++.h> using namespace std; const int N = 10010; int p[N]; int fa[N]; int f[N],v[N],w[N]; int n,m,c; i...

并查集 01背包

2021-08-03

2 567

题解 | #Forsaken喜欢独一无二的树#

题意删除一些边，使得最小生成树唯一，问删除的边的权值和最小是多少？思路为什么最小生成树不唯一：因为连接相同两个集合的边，权值相同的可能有多个所以，我们只需要删除权重相同的且连接同两个集合的那些边即可：这些边中留一个用于维持最小生成树，其余的均删掉。因为是稀疏图，所以使用 Kru...

最小生成树并查集

2021-07-08

1 536

题解 | #银河英雄传说#

思路并查集即可 .问题在于如何求两个战舰之间的战舰数目 ? 我们使用 d[ ] 和 num[ ]来辅助我们解决上面的问题d[i]：i 距离根节点（队头）的距离num[i]：i 所在的连通块有多少个元素（ i 所在那一列的战舰数目） Code #include <bits/stdc+...

并查集

2021-07-08

2 499