在刷题的单身狗很开心

题解

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

/ 注册

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

题解 | #洋流#

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

C++ 广度优先搜索

2023-09-30

2 315

题解 | #Jelly#

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

C++ 广度优先搜索

2023-09-27

1 399

题解 | #迷宫#

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

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

2023-09-27

1 369

题解 | #Lake Counting#

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

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

2023-09-26

1 369

题解 | #wyh的迷宫#

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

C++ 深度优先搜索

2023-09-26

1 255

题解 | #[NOIP2017]奶酪#

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

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

2023-09-26

2 385

题解 | #幸运数字Ⅱ#

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

C++ 深度优先搜索打表

2023-09-25

3 418

题解 | #数独挑战#

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

C++ 深度优先搜索打表

2023-09-24

1 353

题解|#指纹锁#

用set保存，set有内部默认从小到大排序的特性还有自动去重的特性。在进行检测的时候使用set的lower_bound函数，这个函数对找到最近的插入位置，如果存在该数就返回第一个数的下标。如果不存在就返回第一个大于该数的下标，所以是否有符合要求的数只需要看返回的迭代器对应的数以及前一个数是否...

C++ 二分查找 set

2023-09-24

2 457

题解|#小A与任务#

首先最任务进行排序，首先按截止时间进行排序然后按z的值从大到小进行排序。按截止时间进行排序是因为如果过了截止时间那就相当于没完成，所以比较优先，那之后为什么按照z的值进行排序呢？因为z的值大能耗费更小的钱去买。在做任务的过程中如果前面任务的时间相加超过当前任务的截止时间了，就得需要向前面的任务以及他...

C++ 堆(优先队列) 贪心

2023-09-24

1 423