摸鱼学大师

题解

未归档(8)

/ 注册

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

题解 | #最长公共子串# 来自专栏

题目的主要信息：查找两个字符串str1，str2中的最长的公共子串保证str1和str2的最长公共子串存在且唯一进阶要求：时间复杂度：O(n2)O(n^2)O(n2)，空间复杂度：O(n2)O(n^2)O(n2) 方法一：暴力枚举具体做法：遍历str1每个字符作为起点，然后遍历以其为起...

C++ 动态规划

2021-12-02

1 623

题解 | #跳台阶扩展问题# 来自专栏

题目的主要信息：对于n阶台阶，青蛙每次可以选择跳1到n中任意一个数的阶梯数 n为正整数，求青蛙跳上n级台阶的方案数方法一：暴力解法具体做法：对于n个阶梯，如果青蛙第一次选择跳1阶，那么它有还剩下n-1阶，如果选择跳2阶，那么它还剩下n-2阶以此类推，后面剩下的都是子问题，则数学化公式即为...

C++ 动态规划

2021-11-30

0 352

题解 | #Redraiment的走法# 来自专栏

题目的主要信息：对于一个数组，从前往后，每次只能从小到大，问最多经过多少数字即寻找最长递增子序列的长度方法一：暴力动态规划具体做法：要找到最长的递增子序列长度，常用方法是动态规划，dp[i]dp[i]dp[i]表示到元素iii结尾时，最长的子序列的长度，初始化全部为1。遍历两层，前...

C++ 动态规划二分法

2021-11-02

17 1639

题解 | #[ZJOI2010]COUNT 数字计数# 来自专栏

题目的主要信息：求在[a,b][a,b][a,b]中的所有十进制整数中，数字0-9各出现了多少次 30%的数据中，a<=b<=106a<=b<=10^6a<=b<=106，100%的数据中，a<=b<=1012a<=b<=10^12a&...

C++ 动态规划

2021-11-02

0 553

题解 | #串# 来自专栏

题目的主要信息：长度不超过nnn，且包含子序列“us”的、只由小写字母构成的字符串有多少个答案对109+710^9+7109+7取模子序列指必须u在s前，中间可以有间隔具体做法：我们可以对这个分情况讨论： dp[i][0]dp[i][0]dp[i][0]表示字符串长度为iii，但是...

C++ 动态规划

2021-11-01

1 560

题解 | #郊区春游# 来自专栏

题目的主要信息：一共nnn个点，mmm条道路连接，每条道路花费会随着道路连接情况给出给出RRR个要前往的点，前往顺序不定，问什么路线花费最少下面解法中我们用距离代替长度具体做法：首先我们用邻接矩阵来表示这个图，矩阵记录两两点之间的距离，初始化为最大值，自己到自己都是0，再根据输入更新直...

C++ 动态规划图

2021-11-01

2 551

题解 | #数位染色# 来自专栏

题目的主要信息：选出一个最高达18位数的整数nnn十进制中的一些位，这些位数字和等于没选的位的数字和如果可以输出Yes，否则输出No 具体做法：首先使用连除法将nnn的每位数字依次记录在数组中，并在这个过程中求得所有位数之和，那我们要找的就是能否在这个数组中找到诺干个数字加起来等于位数之和...

C++ 动态规划

2021-11-01

4 803

题解 | #红和蓝# 来自专栏

题目的主要信息：一棵无向树，给每个顶点染成红色或蓝色每个红点周围有且仅有一个红点，每个蓝点周围有且仅有一个蓝点无法完成染色输出-1，完成染色输出每个结点的颜色具体做法：首先叶子结点因为只与父亲结点相连，所以叶子结点与父亲结点同色，因此我们可以利用dfs从根节点开始递归遍历树，从叶子结点...

C++ 动态规划 dfs

2021-11-01

1 797

题解 | #旅游# 来自专栏

题目的主要信息：地图上有 n 个城市，它们之间通过 n-1 条道路联通，即一棵无向树第一天会在 s 市住宿，并游览与它距离不超过 1 的所有城市，之后的每天会选择一个城市住宿，然后游览与它距离不超过 1 的所有城市不能住在一个已经浏览过的城市，最多要游览多少天因为每个会去到与这个城市相连...

C++ 动态规划 dfs

2021-11-01

7 576

题解 | #走方格的方案数# 来自专栏

题目的主要信息：一个n∗mn*mn∗m的表格，从左上角走到右下角的方法种数每次只能走下或者右不能回头方法一：递归具体做法：容易想到的是，在第一步时可以选择向右或者向下，只需要当前的路径选择上加上(n,m−1)(n,m-1)(n,m−1)和(n−1,m)(n-1,m)(n−1,m)的矩...

C++ 递归动态规划数学

2021-11-01

87 2472