摸鱼学大师

题解

未归档(8)

/ 注册

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

题解 | #最多节点数# 来自专栏

思路：题目的主要信息： n个节点n-1条边的无向连通图，即一棵无向树两个节点a与b，其中a在节点1，b在节点x，两点移动速度相同，求a和b移动到同一节点所需的最多节点数，需要包括1号节点在内方法一：dfs具体做法：我们可以使用两次dfs分别求得树中每个节点到节点1和节点x的距离，然后遍历找...

bfs dfs 递归队列

2021-09-12

0 636

题解 | #路径数目# 来自专栏

思路：题目的主要信息：一棵以1为根节点的树，节点值为0或者1 最多经过两个值为1的节点的情况下，求有多少条从根达到叶结点的路径方法一：dfs具体做法：我们首先根据题目给出的边信息构建邻接矩阵，可以访问某个节点的所有相邻节点。然后从根节点开始dfs递归，递归过程不断更新路径中1的数量coun...

bfs dfs 队列递归

2021-09-12

0 460

题解 | #两棵树的问题# 来自专栏

思路：题目的主要信息：有两个结点数都为n，根都是1的树，设根的深度为0 定义点对(x,y)的价值为树1中x和y的最近公共祖先的深度+树2中a[x]和a[y]的最近公共祖先的深度输出所有点对的最大值价值数组b与数组c分别记录树1与树2的各个节点的父节点方法一：暴力解法（超时）具体做法：我们...

树 LCA 倍增算法 dfs 集合

2021-09-03

0 563

题解 | #浅尝辄止# 来自专栏

思路：题目的主要信息：给定n，求，输出答案对998244353取模后的值运算表示向下取整方法一：暴力法（超时）具体做法：遍历1到n，暴力累加答案并取模 class Solution { public: int work(long long n) { long lo...

数学整除分块

2021-09-03

0 0

题解 | #牛妹的野菜（权值最大的路径）# 来自专栏

思路：题目的主要信息：一个有向无环图，路径是单向从小序号到大序号，每个节点有权值求图中一条权值和最大的路径，并以字符串输出这条路径方法一：动态规划具体做法：我们可以用动态规划的方式来解决。首先利用给出的路径数组构建一个邻接矩阵，我们以weigh数组表示从每个节点开始的最长路径的长度，pa...

空间记忆搜索递归动态规划 dfs 图

2021-09-03

0 660

题解 | #牛牛扔牌# 来自专栏

思路：题目的主要信息：一个长度为n的字符串，用数字表示牌的点数，字母'C''D''H''S'表示花色，同一牌这两部分相连，即长度为n的字符串有张牌如果还剩下素数张牌，则扔掉牌顶，如果还剩下非素数张牌则将牌底扔掉求扔掉全部牌的顺序，输出字符串方法一：暴力判断素数+字符串截取具体做法：对于...

素数双向队列字符串模拟

2021-09-02

0 388

题解 | #金字塔数组# 来自专栏

思路：题目的主要信息：对于一个数组，如果呈现先递增后递减的趋势，则称之为金字塔数组求连续数组num中的最长金字塔子数组长度，不存在输出0 方法一：动态规划具体做法：我们可以使用最长递增子序列的动态规划法来做这道题。准备两个数组，increase[i]表示到i为止的最长递增子序列长度，dec...

动态规划数组

2021-08-31

0 521

题解 | #树与序列问题# 来自专栏

思路：题目的主要信息：一棵树编号1到n，其中1为根，树的每条边有权值，其中为x节点到y节点经过的边的权值构造一个排列p，使得最大，且输出这个最大值树的边集不会直接给出，但会给出随机种子和构造方式，输入数据包含题干中的n和三个随机种子seed1，seed2，seed3. 构造方式如下 /...

树贪心数学

2021-08-31

0 559

题解 | #Fibonacci sSum# 来自专栏

思路：题目的主要信息：斐波那契数列，其中求方法一：暴力解法（超时）具体做法：使用动态规划求斐波那契数列前n项的值，然后三个循环按照公式相加。 class Solution { public: int mod = 1e9 + 7; int getSum(int n) { ...

矩阵快速幂斐波那契数列动态规划数列求和

2021-08-26

0 554

题解 | #回路# 来自专栏

题目的主要信息： n个节点，m条边，数组edge记录的是有边的两个节点判断这个图是否有从1号节点开始的回路方法一：dfs 具体做法：首先我们构建图。然后从节点1开始进行深度优先搜索，遍历与其相连的每一个节点，每到一个节点不能遍历前序节点或者已经访问过的，然后每次需要判断是否回到了节点1，如...

回路图 bfs dfs 递归队列

2021-08-26

0 711