题意： 给你一个长度为n的数组 ，让你找到数组中最长的一个连续子段 ，使得这个子段之间存在一个 ，使得 且 严格递增 且 严格递减，求出这个子段的长度即可。 解法一（枚举点k，暴力统计答案，不可AC） 我们可以从左到右依次枚举这个点 ，然后尝试以 为最高点依次向左右两边扩展，最后统计答案取最大值即可。 代码： class Solution { public: int getMaxLength(int n, vector<int>& num) { int ans=0;//最终答案 for(int k=0;k&l...

题意： 有若干个物品，每个物品有两种费用 和一个价值 , 现在给你两个数字 和 ，每种物品可以选也可以不选，让你找到一种组合物品的方案，使得 并且 且 最小。 方法一（暴力DFS，不可AC） 依次递归地考虑每个物品 选/不选，最后统计符合要求的答案求最小值即可。 具体的，我们设递归函数 表示当前考虑到第 个物品，当前的 总和为 ，当前的 总和为 ，当前的 总和为 ，最后统计即可。 代码： class Solution { public: int n;//物品总数 int x,y; int ans;//答案 vec...

题意： 给你一个只包含小写字母的字符串，现在要将字符串中的字符 全部移动到字符串末尾，其他字符保持原来的相对顺序不变，求变化后的字符串。 解法1（按照题意模拟，不可AC）： 前置知识：STL之string的使用 按照题意模拟：从左到右扫描过去，遇到字符 就将其 从当前位置 删除并且追加到字符串末尾。 例如： 遇到字符时 将其删除并且移动到最末尾，指针向前移动 代码： class Solution { public: string change(string s) { int idx=0; ...

题意： 有一个 大小的棋盘，你需要在棋盘上面放 个点，问使得第一行，第一列，最后一行，最后一列都有点的方案数，答案对 取模。 解法一（暴力搜索，不可AC）： 直接枚举矩阵每个点是否放点，然后判断是否符合要求再统计答案。 具体的，我们递归地用 表示当前考虑第 个点，当前已经放了 个点，依次统计答案。 代码： class Solution { public: const int mod=1e9+7; int n,m,k; int ans; int vis[4];//vis[0]表示第一行点的数量，vis[1]表示第一列点的数量,vis[2]表示最...

题意： 给你一个数列 ，其中 ， ， 求 的值。 解法一（暴力递推，不可AC）： 根据 可得出 ，因此我们直接循环递推过去即可。 这边我们采用滚动数组的形式，由于每一个只依赖连续的两个值求解，故我们开一个长度为的数组，接下来我们来模拟『填写』值的过程 为了方便，我们将映射到，如表示原来的，表示原来的 ： ： ： ： 代码： class Solution { public: const int mod=1e9+7; int f[2];//采用滚动数组 int solve(int a, in...

题意： 给你两个字符串 和 ，字符串由小写字母组成，长度都为4，现在给你一种操作方法，每次操作你可以选择3个位置将其分别 "加上" 2,3,5，即 ，现在问你 最少操作 几次可以将 变成 ？ 解法1：广度优先搜索 我们以每个长度为4的字符串作为点，每个字符串与其经过一次操作后变换成的字符串所代表的点连边，边权为1，用此方法构造隐式图，最后答案为起点 到终点 的最短路径。 由于图中每条边权都为1，故直接跑广度优先搜索即可求出答案。 代码： class Solution { public: int solve(string s1, stri...

题意： 给你一个数字 ，你可以将当前数字 +1，将当前数字 -1，将当前数字 平方。 问最少操作多少次可以将数字 变换为数字 ？ 方法1（记忆化搜索） 我们设 表示将数字 变换为数字 的最少步数。 接下来我们分情况讨论。 n>=m时，如下图所示 显然有 ，因为数字 想要变小只能每次减1 。 n<m时 第一种决策：将数字 加1， 即 第二种决策：当 时，将数字 平方， 即 接下来我们考虑，能否考虑 这个决策呢？ 显然是不可以的，我们直接考虑一个简单的情况， 依赖 ，而 又依赖 ，这样就形...

题意 有5个盘子，每个盘子有有限个或者无限个体积为 的面包，你有一个体积为 的背包，问刚好装满背包的方案数（两个方案不同当且仅当从某一个盘子中拿出的面包体积不同）。 方法一（暴力解法，不可AC）：分组背包 显然这是一个分组背包问题，其中第1个盘子对应着物体体积为1的完全背包问题，第2个盘子对应着物体体积为1的01背包问题,第3个盘子对应着最多只能拿4个，每个物体体积为1的多重背包问题，第4个盘子对应着物体体积为2的完全背包问题，第5个盘子对应着物体体积为5的完全背包问题。代码： class Solution { public: long long f[1000000001]; ...

题意： 给你一棵 个节点的无根树，每个节点有一个权值，给你 次询问，每次询问你需要求出点 到点 之间的简单路径所经过的点的权值积，答案对 取模。 方法一（暴力求解） 对于每次询问，我们可以把点 和点 都跳到它们的最近公共祖先上，然后把经过的点的权值作为贡献乘到答案里。接下来是如何跳到最近公共祖先上？我们可以首先预处理出每个点的深度，每个点的父亲节点，显然只需要一次DFS即可。然后我们可以把点 和点 暴力往上跳，直到跳到它们的最近公共祖先上。具体的：每次选择深度较大的一个点往上跳，直到跳到跟另外一个点深度相同。接着两个点同时向上跳，直到两个点相遇，即找到最近公共祖先。把跳的过程中遇到的点的权值乘...

题意 给你一个 的矩形范围，你可以用一个宽度最多为 ，高度为 的十字架覆盖矩形范围之内的点，求最多可以覆盖多少个点？（不同点的坐标可能重合，十字架中心点可以随意移动） 方法一（暴力求解） 枚举矩形范围内的所有点，作为十字架的中心点，然后依照题意统计当前点作为十字架的中心点后能够覆盖多少个点，最后答案取最大值即可。 class Solution { public: int cnt[200005]; int g[200005][200005]; int BoomKill(int n, int m, vector<Point>& Player) { ...