在刷题的单身狗很开心

题解

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

/ 注册

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

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

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

C++ 深度优先搜索

2023-10-04

2 305

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

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

C++ 深度优先搜索

2023-10-03

2 411

题解 | #孙悟空救师傅#

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

C++ 深度优先搜索

2023-10-02

1 518

题解 | #Tree Decoration#

利用题目中的数据构造出来一个向下的树。然后如果是在叶子节点的话毫无疑问就得叶子节点独自承受所需要的灯笼，如果不是叶子节点的话就得是递归回去的时候带来子树挂上了多少灯笼以及最小时间花费的节点是多少。这样如果叶子节点不够挂的时候就直接去挂那个最小的时间花费即可。 #include <...

C++ 思维递归

2023-10-02

1 360

题解 | #Sramoc问题#

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

C++ 广度优先搜索

2023-10-02

1 438

题解 | #[SCOI2010]游戏#

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

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

2023-10-01

1 408

题解 | #新集合#

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

C++ 深度优先搜索

2023-10-01

0 334

题解 | #魔法数字#

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

C++ 广度优先搜索

2023-10-01

2 338

题解 | #单词接龙#

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

C++ 深度优先搜索

2023-09-30

2 398

题解 | #小木棍#

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

C++ 深度优先搜索

2023-09-30

1 449