在刷题的单身狗很开心

题解

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

/ 注册

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

题解 | #胖胖的牛牛#

因为正在练习图论，所以建图来做吧。可以假设某个各种的上下左右方向都有一个点，那么这些点的道路里面方向改变的，也就是某个格子上下左右相邻直接的道路的长度是1，其余是0。那么就可以转化成起点的四个方向点到终点的四个方向点的求解。那么直接套Dijkstra算法即可。就是建图有那么亿...

C++ 深度优先搜索图论迪杰斯特拉算法

2023-11-06

1 293

题解 | #[CQOI2007]矩形RECT#

本题需要去到矩阵里面进行dfs来求出所有的情况。当在矩阵里面走到边界的时候就是剪切结束的时候。那么剪切开始的时候就是在边界上。简单的来看就是从上下左右四个边上的点都走一遍且将走过的排除掉就是答案（定点当然不算）。这种简单粗暴地方式确实可以解，我也确实写了一遍。。。。。但是会超时。我们垃圾代码...

C++ 深度优先搜索

2023-10-23

1 296

题解 | #宝藏猎人#

本题直接使用dfs，然后配合剪枝去接最好。直接dfs的去进行每一步当递归到最大的拥有宝藏的岛屿的下一个就可以宣布结束返回了。如何剪枝：本题中dfs是从前向后的传参形的记录当前的宝藏数量，那么如果某个岛屿第二遍被递归到的时候如果当前的宝藏数还没有之前的大。那么再递归下去就没有意义了。这...

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

2023-10-18

0 331

题解|#可爱の星空#

对于某个数量的星星来说，它的连同的最小代价应该是将其折半后拼接，那么折半后折半下来的其余部分也按照这样折半的思路去，之后全部相加就是最小的代价。 //以星星为第一维，那么每加入一个星星能够得到的代价作为二维。 #include <bits/stdc++.h> using&...

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

2023-10-10

0 567

题解 | #滑雪#

本题设dp[i][j]代表从(i,j)这个点出发能够走到的最大距离。但是由于他的上下左右其实也没有被确定，在这里使用记忆化搜索如果上下左右某处没有被确定的话就递归去搜索，如果搜索到的某处为其上下左右的最小值的话就直接返回，如果已经搜索过了也直接返回。此外还要做边界的判断。将每一个点都进行一次...

C++ 动态规划深度优先搜索记忆化搜索

2023-10-06

2 325

题解 | #[NOIP2003]数字游戏#

本题应该用动态规划才方便，但这里先介绍一种深搜的用法。既然他将一个圆形的分成几部分，为了表示这个圆形我们可以开一个二倍的数组去保存两个相同的序列，这样就可以将首尾给衔接上。那么如何表示圆形序列的分隔呢？在这里可以使用一个now表示当前部分的开头坐标，然后向后去枚举这个部分的末尾下标，...

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

2023-10-05

2 397

题解 | #[USACO 2010 Mar G]Great Cow Gathering#

由于有N-1条路，所以最终是一个双端的树形结构。那么可以任意选择一个点作为根节点。那么深搜的话每向下走一步的话该节点以及子节点的的距离就会减去这一段距离，其余节点会加上这一距离。也就是说只要顺便选定一个根节点接着向下进行深搜就可以快速得到接下来其他农场的数值。在这里使用邻接表去存储。...

C++ 深度优先搜索

2023-10-04

2 297

题解 | #[NOIP2009]靶形数独#

和之前做过的填数独的题目相似，要想DFS的去填写数独的话最关键之处就在于如何进行行与不行的判断。根据游戏规则如果一个数可填那么就需要横和竖以及所在的宫格里面没有相同的数。那么就得采用HASH散列的方式去记录下某一行，某一列以及某一个宫格里面有哪些数。在这里为了方便使用宫格与每一个之间的映射所以提前打...

C++ 深度优先搜索

2023-10-03

2 421

题解 | #孙悟空救师傅#

将二维地图加上一个钥匙编号变成三维。这样在得到钥匙之后还能去广搜得到下一个钥匙或者救到师父。在这里面没有明确的结束条件，要保证不走回路就是不能走比他小得路。 #include <bits/stdc++.h> using namespace st...

C++ 深度优先搜索

2023-10-02

1 518

题解 | #[SCOI2010]游戏#

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

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

2023-10-01

1 406