在刷题的单身狗很开心

题解

2023河南萌新联赛第（八）场(3) c++(1) 动态规划(5) 差分与前缀和(4) 洪水填法(1) 牛客小白月赛78(4) 牛客练习赛115(2) 牛客练习赛116(2) 算法(1) 算法刷题(2)

/ 注册

全部文章 / 题解（共7篇）

题解 | #[SCOI2010]游戏#

本题将每件装备的两个点连成线，变成图。如果某个区域里面的图是一个树的话证明有一个是取不到的数，这时候必然将最大的去掉才为最好啊。如果不是一个数，也就是有一个或多个回路的话证明每个数都可以取到。那么最后取组成为数里面的最大数，取最大数里面的最小的那个数就是最早阶段的地方，这个地方就是答案。 ...

C++ 深度优先搜索并查集

2023-10-01

1 407

题解 | #Lake Counting#

可用DFS,BFS,并查集。在这里使用DFS，将所以为W的点记录下来，然后遍历这些点，在遍历某一个点的时候使用深度优先遍历将其相邻的所以池塘全部标记下来，这样在遍历W的时候可以将其跳过。 #include <bits/stdc++.h> using names...

C++ 广度优先搜索深度优先搜索并查集递归

2023-09-26

1 370

题解 | #[NOIP2017]奶酪#

想过使用深度优先遍历，但是用优先遍历每次遍历都需要遍历每一个洞去查看是否存在与其相切或者相交的洞，付出的时间复杂度也挺大的。后来也可以想到使用并查集去求解，但遍历总是逃不掉的。又看到n的范围是1 ≤ n ≤ 1,000，所以两种方法都行。并查集：将所有能都通过的洞组合到一个树里面，保持树的根...

C++ 广度优先搜索深度优先搜索并查集

2023-09-26

2 386

题解 | #Parity game#

将区间x~y中1个数是偶数还是奇数转变成1~x-1和1~y两个区间里面的奇偶性相反的问题。然后通过扩展域并查集求解。 #include <bits/stdc++.h> using namespace std; unordered_map<in...

C++ 并查集

2023-09-22

2 258

题解 | #食物链#

扩展域并查集解决了有多种相互关系的问题。这题如果单纯的去判断是不是同类就是用普通的并查集就可以了。但由于有想吃的关系，所以得使用扩展域并查集，有三种动物，将并查集的数组扩大三倍。对于某x,y两个动物是同类的情况这两个动物可能是A,B,C任意一种。那么将x,y合并。x+n,y+n合并。y+2*n,x+...

C++ 并查集

2023-09-21

1 351

题解 | #叠积木#

一个需要维护附加信息的并查集。需要维护的信息为某编号为 x 的积木下方有多少块积木。直接维护需要更新一棵树的所有节点，这显然是不方便的。在这里我们选择让根节点保存某个编号下的箱子总数，然后下面被连接的根节点保存其下方有多少箱子。这样查询某个编号的箱子下面的箱子个数只需要向...

C++ 并查集维护附加信息的并查集

2023-09-17

1 458

题解 | #DongDong认亲戚#

//并查集的模板题，写个并查集完事 #include <bits/stdc++.h> using namespace std; map<string , string> mp; string fin...

C 并查集

2023-09-15

2 275