在刷题的单身狗很开心

题解

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

/ 注册

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

题解|#「木」迷雾森林#

某一个位置上的途径数其实源于左边和下面，也就是说某一个位置只来自左边和下边。那么动态方程就可以出来了。又有可以使用BFS来走这个地图所以在BFS的过程中加入动态规划记录累计的途径数就可以了。 #include <bits/stdc++.h> using ...

C++ 动态规划广度优先搜索

2023-10-11

1 357

题解 | #Sramoc问题#

使用广搜，每一位都是0~k-1的数，使用广搜去每一层遍历每一位在搜索过程中会出现位数很大的数字，所以使用字符串去拼接保存，但每变化一次都要记录相应字符串的余数，在这里使用余数分配率进行计算。在使用一个vis数组去记录哪些余数已经出现过了，因为如果余数已经出现过了那么根据取余运算的分配率这个数...

C++ 广度优先搜索

2023-10-02

1 441

题解 | #魔法数字#

使用BFS搜索每一次操作后的数字以及操作数即可。要注意这道题截止卡的比较死，如果num>m+(abs(m-n))就没有操作的价值了，因为还不如从n一步一步加或减到m。 class Solution { public: /*...

C++ 广度优先搜索

2023-10-01

2 348

题解 | #洋流#

本题才是用BFS进行求解，但是单纯的使用BFS会出现错误，因为并不是每一步都是相同的消耗，如果让消耗多的先进入了那么该点就不是最小的消耗。可以使用一个优先队列来维护，每次都让最小的消耗去走，这样可以保持没一点都是由最小的来进入。但在本题当中，由于是01之间的消耗。所以可以使用一个双端队列，如果是...

C++ 广度优先搜索

2023-09-30

2 316

题解 | #Jelly#

BFS模板题。 #include <bits/stdc++.h> using namespace std; struct Node { int x, y, ...

C++ 广度优先搜索

2023-09-27

1 400

题解 | #迷宫#

本题使用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

题解 | #[NOIP2017]奶酪#

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

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

2023-09-26

2 386