在刷题的单身狗很开心

题解

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

/ 注册

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

题解 | #新集合#

遍历1-n的每一个元素，深搜的关键点在于选与不选，在选择的时候检查是否有限制里面的元素，该跳过跳过. /** * struct Point { * int x; * int y; * Point(i...

C++ 深度优先搜索

2023-10-01

0 335

题解 | #单词接龙#

使用BFS去搜索每一个可以添加的单词，然后将所有的可能性搜索一遍之后取最大的。关键点：如何进行字符串的匹配：将s1从后向前遍历，如果与s2的第一个匹配上了就接着向前走，如果知道s1的末尾都通过的话就证明可以匹配上。不用真的拼接上去，只需要记录拼接后的长度就行。拼接后的长度：两个字符串...

C++ 深度优先搜索

2023-09-30

2 389

题解 | #小木棍#

采用DFS，每一层递归都是去选择某个木棍去组成一个长木棍。如果能够将小木棍全部用完而且长木棍也正好拼凑成整数的话就可以。这时候可以从小到大进行验证如果某个长木棍的长度可以满足条件那么就是答案。但是直接进行DFS会超时需要进行剪枝。先将木棍从大到小排序，让每一个长木棍里面的小木棍都从大到小排序...

C++ 深度优先搜索

2023-09-30

1 444

题解 | #迷宫#

本题使用BFS去求解，在写BFS的过程中要多保留步骤和是否捡到钥匙这两个信息。因为BFS并不是一个路径遍历的最后的（DFS），所以在每一个循环里面加步骤必然是不对的。所以需要在其结构体里面保存。还有就是这题独特之处在于钥匙和门的限制，也就是会出现捡到钥匙后还需要回头的情况和不需要钥匙直接到达重点两种...

C++ 深度优先搜索广度优先搜索

2023-09-27

1 370

题解 | #Lake Counting#

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

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

2023-09-26

1 370

题解 | #wyh的迷宫#

深搜即可。 #include <bits/stdc++.h> using namespace std; const int maxn = 500+10; char a[maxn][maxn]; int...

C++ 深度优先搜索

2023-09-26

1 257

题解 | #[NOIP2017]奶酪#

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

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

2023-09-26

2 386

题解 | #幸运数字Ⅱ#

本题通过对所有位数的符合的数进行深度优先遍历，从而得到所有符合的数（提前打表）。在打完表之后只需要进行排序后使用lower_bound和upper_bound就可以找个最近和最远的范围。然后在遍历这个范围的时候还需要根据没加上的数和当前遍历到的数的差值进行相乘，这样可以节省不停二分寻找的造成...

C++ 深度优先搜索打表

2023-09-25

3 419

题解 | #数独挑战#

这道题不难，但是打表这个小技巧让我眼前一亮。通过打表可以判断某个取余里面是否有某个数字。 #include <bits/stdc++.h> using namespace std; const int maxn =&n...

C++ 深度优先搜索打表

2023-09-24

1 353

题解 | #N皇后问题#

深度优先遍历加剪枝的经典问题。在递归过程中按行去递归保证了不在同一行，然后使用结构体数组来保存前面行已选定的坐标，在每一行都循环的去选择是哪一列。然后判断和之前的是否在同一列或同一对角线。如果递归到N次了，那么就证明可以有一个方案了。如何判断在同一对角线：abs(y-y`)==abs(x-x...

C++ 深度优先搜索

2023-09-20

2 330