摸鱼学大师

题解

未归档(8)

/ 注册

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

题解 | #剪绳子（进阶版）# 来自专栏

题目的主要信息：把一根长度为nnn的绳子分成mmm段，每段长度都是整数求每段长度乘积的最大值由于答案过大，请对 998244353 取模进阶要求：空间复杂度：O(1)O(1)O(1)，时间复杂度：O(log2n)O(log_2n)O(log2n) 数学推算根据均值不等式，有：n1+...

C++ 快速幂快速乘法数学

2021-12-04

15 983

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

题目的主要信息：一个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

题解 | #将真分数分解为埃及分数# 来自专栏

题目的主要信息：分子为1的分数称为埃及分数输入一个分子比分母小的分数，请分解为分母不同的埃及分数分子和分母有可能gcd不为1 如有多个解，输出一个即可方法一：迭代具体做法：如下图公式推算，我们可以贪心地用这种除法取余地方式更新分子分母，不断获取分子为1的分数。因为分子分母gcd可...

C++ 数学

2021-10-31

21 1587

题解 | #蛇形矩阵# 来自专栏

题目的主要信息：蛇形矩阵是由1开始的自然数依次排列成的一个矩阵上三角形形如： 1 3 6 10 15 2 5 9 14 4 8 13 7 12 11 方法一：顺序填表具体做法：我们...

C++ 数组数学

2021-10-20

42 1105

题解 | #整数中1出现的次数（从1到n整数中1出现的次数）# 来自专栏

题目的主要信息：输入一个整数 n ，求1～n这n个整数的十进制表示中1出现的次数方法一：暴力统计法具体做法：我们可以尝试遍历1到n的每个数字，然后对每个数字单独遍历它的每一位，检查是否是1，如果是1则计数。 class Solution { public: int NumberO...

C++ 数学

2021-10-02

2 868

题解 | #跳台阶# 来自专栏

题目的主要信息：一只青蛙一次可以跳上1级台阶，也可以跳上2级，先后次序算不同的方案求该青蛙跳上一个n级的台阶总共有多少种跳法要求：时间复杂度O(n)O(n)O(n)，空间复杂度O(1)O(1)O(1) 方法一：动态规划具体做法：我们用可以考虑第n级台阶，它可以由第n-1级台阶跳1级而来...

C++ 动态规划矩阵快速幂数学

2021-09-30

7 526

题解 | #找出重复的数# 来自专栏

题目的主要信息：数组中n+1个元素，包括1到n的所有整数找到重复的那个数字额外要求：时间复杂度O(n)O(n)O(n)，空间复杂度O(1)O(1)O(1) 方法一：排序法（能通过，时间不符合要求）具体做法：利用sort函数对数组排序，遍历数组，相邻两个数相同则找到所求。 class S...

数学异或运算排序哈希表双指针

2021-09-14

6 642

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

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

数学整除分块

2021-09-03

0 0

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

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

树贪心数学

2021-08-31

0 559

题解 | #牛牛排队# 来自专栏

思路：题目的主要信息：数组a表示n个人，记忆的他们原来的位置左边人数减去右边人数的绝对值求原来有多少种排法我们可以发现一个人的时候，，两个人的时候，，三个人的时候，，四个人的时候，或者其打乱了顺序，我们可以根据数学归纳法判断，若是为奇数，则数组a排序后应为，若是为偶数，则数组a排序后应为...

数组数学快速幂排序

2021-08-25

0 531