题意： 给你一棵个节点的有根树，根节点为1，每个节点的权值为0或者1，问有多少条从根节点到叶子节点的路径，使得所经过的节点权值和不超过2 ？ 解法一（深度优先搜索） 从根节点对整棵树进行dfs，然后计算答案 具体的：     我们定义递归函数表示当前是以点为根节点的子树，并且点的父亲节点为，当前经过的节点权值和为，节点权值数组为     1. 将当前的变量加上对应节点的权值，即     2. 若大于2，则往下走到叶子结点一定不合法，故直接返回     3. 枚举当前节...

题意： 给你一棵个节点的有根树，给你个操作，每次你需要将以为根节点的子树所有节点的权值加上 最后返回所有节点的权值 解法一（暴力算法，不可AC） 首先对整棵树进行一次dfs，预处理出每个节点的父节点 然后对于第个操作，我们直接一遍dfs将对应子树节点的权值加上对应的值 最后返回答案数组即可 代码： /**  * struct Point {  * int x;  * int y;  * Point(int xx, int yy)...

题意： 给你一个的整数集合，再给你个限制条件，条件的形式如下：     第个条件给你两个数，表示和不能在同一个集合中 现在问你总共有多少种选法，使得所选集合满足条件？ 解法一（暴力枚举） 发现本题中数据范围，于是我们可以直接枚举每一个数字选或者不选两种情况，最后枚举完所有情况后再判断是否满足条件即可 具体的：     我们定义递归函数表示当前考虑到第个数字，然后枚举两种情况继续递归即可，到递归边界再进行判断是否满足条件     递归树如下图： 代码： /** &nbsp...

题意： 给定一棵节点数为的二叉树的前序遍历和后序遍历的序列，求出该二叉树中序遍历的序列 解法一（递归求解） 我们考虑表示求解前序遍历的序列为，后序遍历的序列为的一棵子二叉树的答案     1. 根据前序遍历的性质，我们知道当前子树的根节点为     2. 根据前序遍历（根、左、右）的顺序，我们知道当前节点的左子树的根节点为     3. 接下来我们考虑求解当前左子树的节点个数         （1）我们知道对于后序遍历来说，根节点是...

题意： 给你一个长度为的01数组，你可以将其中个数字0变成数字1，问变化后数组中最长连续的一段1长度是多少？ 解法一（暴力求解，不可AC） 首先我们可以枚举数组中每一个数，当枚举到第个数时，我们可以暴力求出以第个数为结尾，最长的连续一段1长度的值，我们记其为第个数对答案的贡献 最终答案即为所有贡献的最大值 具体的：     对于第个数字，我们可以暴力往前循环，若遇到0，则将减一；若遇到1，则继续向前，直到无法向前或者为0则结束循环     最后对于第个数字的贡献即为遇到数字的总个数   &nbs...

题意简述： 给你一个大小的网格迷宫，迷宫的每个格子分为四种类型：空地、障碍物、唯一固定传送门、可放置传送门位置 游戏刚开始时，你可以选择一个『可放置传送门位置』放置一个传送门，这个传送门可以和『唯一固定传送门』互通 刚开始玩家处于迷宫第行第列，玩家每次可以走上、下、左、右四个方向，且不能走到障碍物，不能超界，遇到传送门可以选择传送也可以选择不传送 问玩家最少花多少步可以到达迷宫第行第列？ 解法一（枚举放传送门位置，多次BFS，不可AC） 我们可以枚举所有『可放置传送门位置』放置传送门，并且在当前条件下利用BFS求出起点到终点的最少步数。 代码： c...

题意： 给你个数，请求出这个数有多少个连续的区间，使得每个区间都满足： 区间内数字的最大值大于等于区间内数字的最小值的两倍 解法一（暴力求解，不可AC） 直接枚举所有区间，并判断是否满足条件 具体的：     第一层循环枚举左端点，并且在第一层循环内维护最大值和最小值     第二层循环枚举右端点，从左到右枚举的过程中顺便维护和 代码： class Solution { public:     long long ...

题意： 在所有不同的组合数中，求出第小的组合数。 解法一（暴力枚举，set判重，不可AC） 我们首先观察杨辉三角的一部分 我们可以直接枚举出杨辉三角中行中的所有数字，然后利用set数据结构来进行判重，最后返回set中第个数字即可。 具体的：     我们已知，故对于第行，我们只需要枚举第个数字即可 代码： class Solution { public:     unordered_map<int,int> fac;//记忆化搜索，存储n!...

题意： 给定一棵完全二叉树按照层次遍历的访问序列，对于这棵树的每条边，所表示的价值为这条边两点序号的异或值，求出整棵树所有边的价值和。 解法一（记录父节点） 我们用一个变量表示当前枚举到的节点下标（从左到右枚举），从开始枚举 用一个变量表示当前下标为所代表的节点的父亲节点的下标，显然刚开始为 如下图： 我们的变量是从左到右枚举的，变量显然也是从左到右枚举 我们发现，变量每枚举了两个节点，变量刚好枚举了一个节点 于是我们可以记录下当前已经访问了多少个节点，每访问两个节点后让变量加上 于是我们就做完了 代码： class...

题意： 将一根长度为 切割为每段至少长度为5的若干段，求总的切割方案数？（5+6和6+5算两种不同的方案） 解法一（暴力枚举，不可AC）： 我们可以定义递归函数 表示当前绳子长度为 ，进行递归地切割，最后 时统计答案。 代码： class Solution { public: const int mod=998244353; int ans; void dfs(int i){ if(i<0)return;//长度不能为负数 if(i==0){//刚好切割完 ans=(ans...

题意： 有数码 各无限个，消耗一个数码 需要的代价为 ，现有大小为 的可消耗代价，问可以凑成的最大数字为多少？ 解法一（完全背包）： 注意到每个数码可以用一次和多次，使用数码需要消耗一定的代价，这显然是一个变形的完全背包问题。 现在需要解决的是，有一个数字字符串 ，要将数码 插入到数字字符串 中，怎样可以让结果最大？ 我们记使得结果最大的数字字符串为 。 我们知道，在长度相同的情况下，高位的数码越大可以使得整个数字字符串越大，那么我们容易设计出如下算法： 从高位到低位遍历数字字符串 ，若数码 大于等于当前遍历到的数码，则将数码 插入到当前位置。 例如，原本的数字...

题意： 有两种蛋糕，第一种蛋糕有 个，第二种蛋糕有 个，要求将这些蛋糕分到 个盘子里，分法必须满足下列要求： 1. 每个盘子里只能放一种蛋糕 2. 盘子不能为空 现在让你求出满足上述要求的前提下，装有最少蛋糕数量的盘子中装的蛋糕数量最多是多少？ 解法一（暴力枚举答案） 有一个显然的结论，要让能够装的盘子越多，盘子中的蛋糕数量就必须要越少。 那么，我们已经枚举了盘子中蛋糕数量的最小值了，那么显然我们让每个盘子的蛋糕数量都为这个最小值，那么可装的盘子数量一定是最多的，即 均分 蛋糕一定是最优的。 具体的，我们从大到小枚举这个最小值 ，然后我们不妨先 均分 第一种蛋糕，再 均分 第...

题意： 给你一个数字 ，求 。 解法一（暴力求解，不可AC）： 直接循环 按题意计算过去即可。代码： class Solution { public: const int mod=998244353; int work(long long n) { int ans=0; for(long long i=1;i<=n;i++){//注意开 long long ans=(ans+n/i)%mod; } return ans; } };时间复杂度： ，程序中有一个 的循环，故时间...

题意： 给你一张有向无环图，图中每个点都有一个权值，找出一条路径使得路径经过的点权值和最大，输出这条路径。 解法一（记忆化搜索）： 我们记 表示以点 为起点能够获得的最大权值和， 表示以点 为起点能够获得最大权值和的前提下下一个点的编号。 对于 ，显然有 对于 ，显然就是使得 最大的那个 例如本题样例（为了简化，我们图中只表示了f[i][0]）： 具体的，我们可以开一个标记数组 记录某个节点是否计算过，然后再枚举每个节点为起点进行递归求解。 代码： class Solution { public: /*以下是动...