思路： 题目的主要信息：  给定n，求，输出答案对998244353取模后的值 运算表示向下取整  方法一：暴力法（超时）具体做法：遍历1到n，暴力累加答案并取模 class Solution { public: int work(long long n) { long long res = 0; int mod = 998244353; for(long long i = 1; i <= n; i++){ //注意n为long long res = (res + n / i) % mod; //按照公式累加 } return (int)res; } };复杂度分析：  时间复杂度：，一...

思路： 题目的主要信息：  一个有向无环图，路径是单向从小序号到大序号，每个节点有权值 求图中一条权值和最大的路径，并以字符串输出这条路径  方法一：动态规划具体做法：我们可以用动态规划的方式来解决。首先利用给出的路径数组构建一个邻接矩阵，我们以weigh数组表示从每个节点开始的最长路径的长度，path表示这条路径的字符串组成，初始时都只有自己。因为是从每个节点开始的最长路径的长度，为了方便“-”的连接，我们逆序查找。每到一个节点，我们遍历其所有直接相连的后续节点，找到最长的路径，将其放入上述两个数组。但是因为这种连接会断，因此第一个并非一定是最大，因此我们还需要遍历weigh数组找到最大值及...

思路： 题目的主要信息：  一个长度为n的字符串，用数字表示牌的点数，字母'C''D''H''S'表示花色，同一牌这两部分相连，即长度为n的字符串有张牌 如果还剩下素数张牌，则扔掉牌顶，如果还剩下非素数张牌则将牌底扔掉 求扔掉全部牌的顺序，输出字符串  方法一：暴力判断素数+字符串截取具体做法：对于每次剩下的牌数，我们可以暴力判断其是否是素数。我们用两个指针left和right指向牌顶和牌底的下标，每次剩下的n为素数我们就截取牌顶指针后两位字符，n为非素数我们就截取牌底指针后两位字符，直到n为0.  class Solution { public: bool isPrime(int a){ i...

思路： 题目的主要信息：  对于一个数组，如果呈现先递增后递减的趋势，则称之为金字塔数组 求连续数组num中的最长金字塔子数组长度，不存在输出0  方法一：动态规划具体做法：我们可以使用最长递增子序列的动态规划法来做这道题。准备两个数组，increase[i]表示到i为止的最长递增子序列长度，decrease[i]表示从i开始的最长递减子序列长度，我们遍历数组中每个元素，一旦对于某个元素以其为结尾的递增子序列长度和以其开始的递减子序列长度都大于1（因为只有自己时为1），我们认为这是一个金字塔数组，两边长度相加减1即是这个金字塔数组的长度（因为这个元素本身重复计算）。遍历数组，维护最大值即可得到...

思路： 题目的主要信息：  一棵树编号1到n，其中1为根，树的每条边有权值 ，其中为x节点到y节点经过的边的权值 构造一个排列p，使得最大，且输出这个最大值  树的边集不会直接给出，但会给出随机种子和构造方式，输入数据包含题干中的n和三个随机种子seed1，seed2，seed3. 构造方式如下 //////////////////////////// 定义数组u[],v[],w[] //u[i],v[i]分别表示第i条边的两个端点，w[i]表示第i条边的边权。 定义变量seed4. 定义循环变量 i 从1到n-1 循环体开始 seed4=((seed1+seed2)%998244353)*s...

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

题目的主要信息：  n个节点，m条边，数组edge记录的是有边的两个节点 判断这个图是否有从1号节点开始的回路  方法一：dfs 具体做法： 首先我们构建图。然后从节点1开始进行深度优先搜索，遍历与其相连的每一个节点，每到一个节点不能遍历前序节点或者已经访问过的，然后每次需要判断是否回到了节点1，如果没有则继续深度优先搜索往下走，如果最后也没有回到节点1，返回false。 class Solution { public: bool dfs(int cur, int pre, vector<vector<int>>& G, vector<int>&am...

思路： 题目的主要信息：  一共k个码头，每个码头每天可卸货一吨，完成一艘船的任务后才能开始下一艘船 一共n艘货船，到达码头的时间记录在数组a(每艘船到达时间不一样），货物吨数记录在数组b（本题中可直接认为是卸货天数） 先抵达先卸货，问最少多少天卸完  方法一：小顶堆+排序具体做法：因为是先到先卸货，且没有卸完这艘船不能开启下一艘船，因此我们可以对船按照到达时间进行排序，然后分配给k个码头。分配的时候我们使用小顶堆，若是船到达的时候还有空码头，可以直接分配，入堆即可，若是船到达的时候没有空码头了，我们可以将其需要时间接到堆顶（即最小的一个），这样耗时可以最短。每艘船到达的时候需要检查是否有完成...

思路： 题目的主要信息：  n棵苹果树上的果实存在数组a中 m天，每天要从每棵树上摘得苹果数存在数组b 对于某一天，对于每一棵树，若是苹果树上存留得苹果数大于等于，则摘取个，否则摘取剩余得全部 求每天各可以摘取共多少苹果  方法一：暴力法（超时）具体做法：我们可以遍历每一天，每天遍历数组a检查苹果树现有的苹果树，然后根据与b[i]的比较，摘取苹果并更新数组a。 class Solution { public: vector<long> solve(vector<int>& a, vector<int>& b) { int n = a.size...

思路： 题目的主要信息：  数组a表示n个人，记忆的他们原来的位置左边人数减去右边人数的绝对值 求原来有多少种排法  我们可以发现一个人的时候，，两个人的时候，，三个人的时候，，四个人的时候，或者其打乱了顺序，我们可以根据数学归纳法判断，若是为奇数，则数组a排序后应为，若是为偶数，则数组a排序后应为，其中数字0一定在中央，其他数字可以分别对换一次位置，因此总方案数为 方法一：排序+快速幂具体做法：首先对数组进行排序，然后根据奇偶人数检查数组是否是上述的形式，如若不是则无法构成正确的队列，如果是则根据公式，利用快速幂算出答案。快速幂的解析如下：如果我们要计算，常规的算法是，然后再，如此往下，一共...

思路： 题目的主要信息：  n个人的身高用数组a表示 每个人往前面开枪，会打到他前面比他高的第一个人，同时荒唐度增加被打到这个人的次序号（下标+1） 求最后总的荒唐度 方法一：暴力解法* 具体做法：*遍历数组每个人，然后每次往这个前面找到第一个大于它的元素，返回值增加下标加1.class Solution { public: long long solve(int n, vector<int>& a) { long long res = 0; for(int i = 1; i < n; i++){ int j = i - 1; //往前 while(j >= 0...

思路： 题目的主要信息：  定义函数 已知与，求  方法一：暴力解法（超时）具体做法：写一个循环算幂的函数，然后遍历到，将计算的幂结果按照公式相乘再相加并取模。因为，超出了long long的表示范围，因此该方法就算不超时也会有部分过大的案例无法通过。 class Solution { public: long long cal(int x, int y){ //计算x的y次幂 long long res = 1; for(int i = 0; i < y; i++) res *= x; return res; } long long solve(string sa, string sb...

##思路： 题目的主要信息：  定义函数f(x)=xa+xa+1+...+xb−1+xbf(x) = x^a + x^{a+1} +...+ x^{b-1} + x^bf(x)=xa+xa+1+...+xb−1+xb 已知nnn、aaa、bbb，求f(n)%10000000033f(n)\%10000000033f(n)%10000000033  方法一：暴力解法（超时） 具体做法： 写一个循环算幂的函数，然后遍历aaa到bbb，将计算的幂结果相加并取模。 class Solution { public: long long cal(int x, int i){ //计算x的i次幂 long ...

思路： 题目的主要信息：  有n种不同面值的货币，面值大小和数量记录在数组a中 问将x元换成若干零钱的种类有多少，x可以不为货币面值  方法一：动态规划具体做法：使用动态规划，设表示用前种货币凑出金额为的方案数量，初始时，因为每种面值的货币的数量有限，我们要枚举每一个出现的可能数量。则用前种货币凑出金额为的方案数等于前种面值的货币凑出金额不加入个第种货币的方案数的累加和：，其中. class Solution { public: int solve(int n, int x, vector<vector<int> >& a) { vector<vector...