题目链接 小红的有序数组 题目描述 小红有一个长度为  的排列，她每次可以选择两个数  和 ，要求  和  的奇偶性相同，然后交换这两个数。问最少需要多少次操作才能使得数组变成有序的，如果不能变的有序，输出 -1。 输入:  第一行输入一个整数 ，表示数组的长度 第二行输入  个整数 ，表示数组的元素  输出:  如果能变成有序的，输出最少需要的操作次数，否则输出 -1  解题思路 这是一个贪心问题，可以通过以下步骤解决：   关键发现：  只能交换相同奇偶性的数字 这意味着奇数和偶数的相对位置不能改变 最终数组要升序排列    解题策略：  分别记录奇数和偶数的位置 检查奇数和偶数的相对位置...

题目链接 小苯的比赛上分 题目描述 有一款著名的大型多人电子竞技游戏网站"喜爱福"，网站通常会举办一些比赛。通常一名参赛选手只有一个账号，但不难猜到，总会有人"开小号"上分。 小苯就是一位该游戏的忠实玩家，他总共有  个账号，每个账号的分数分别为 。他深谙游戏中一位著名玩家 st****lk 的一句名言："只要你永远打分更低的号，那么你的最高分就是单调不降"。 现在我们记录了小苯  次的比赛记录，已知小苯每次都会谨记 st****lk 的名言，从而使用分数最低的账号参赛。现在我们想知道小苯每次参赛后，他的最高分是多少。 输入:  第一...

题目链接 小红的校招笔试 题目描述 小红正在参加校招笔试，现在给出了小红的分数、总人数以及其他人的分数，已知校招的过线率是50%（向下取整），小红想知道她最终是否能过线？ 注：如果有多个人和恰好过线的分数相同，那么这些人会同时过线。 输入:  第一行输入一个正整数 ，表示总人数 第二行输入  个整数，用空格隔开，第一个数是小红的分数，其他是其他人的分数  输出:  如果小红过线了，输出"Yes"，否则输出"No"  解题思路 这是一个排序问题，可以通过以下步骤解决：   关键发现：  过线人数是总人数的一半（向下取整） 过线分数是排序后第 n/2 个位置...

题目链接 小红的多彩糖葫芦 题目描述 小红喜欢吃多彩糖葫芦，多彩糖葫芦上的每一个糖葫芦都有一种颜色。但小红有非常严重的强迫症，她绝对不会连续吃两个相同颜色的糖葫芦。一串糖葫芦只能从上往下吃，一旦小红发现下一颗糖葫芦和她刚吃过的糖葫芦颜色相同时，小红就会把整串多彩糖葫芦丢掉。小红想知道她吃一串多彩糖葫芦时可以吃到几颗糖葫芦。 输入:  一个字符串，表示多彩糖葫芦串上从上到下每一颗糖葫芦的颜色  输出:  一个整数，表示小红最多能吃到的糖葫芦数量  解题思路 这是一个模拟问题，可以通过以下步骤解决：   关键发现：  小红只能从上往下吃 遇到相同颜色就会停止 需要记录上一个吃的糖葫芦的颜色    ...

题目链接 分组 题目描述 现在有  个同学，老师要把他们分成若干组去做游戏，每个组的同学必须要不少于  个人，请问这  个同学最多可以分成多少组。 输入:  一个正整数 ，表示同学的数量  输出:  一个整数，代表最多可以分成的组数  解题思路 这是一个数学问题，可以通过以下步骤解决：   关键发现：  要使组数最多，应该尽可能让每组人数最少 每组至少要有3人 所有人必须被分配到某个组中    数学推导：  设最多可以分成 x 组 每组至少3人，所以总人数至少需要 3x 人 因此必须满足：3x ≤ n 解得：x ≤ n/3 所以答案就是 ⌊n/3⌋    具体步骤：  直接计算 n/3 的整数...

题目链接 小红的好数组 题目描述 小红定义一个数组为好数组当且仅当这个数组至少存在一个长度为3的非降序子数组。小红可以进行多次操作，每次操作可以修改数组中的一个元素。小红想知道至少需要操作几次才可以把这个数组变成不是好数组。 输入:  第一行输入一个整数 ，表示数组的长度 第二行输入  个整数 ，表示数组的初始值  输出:  一个整数，表示最少需要的操作次数  解题思路 这是一个贪心问题，可以通过以下步骤解决：   关键发现：  要使数组不是好数组，就要破坏所有长度为3的非降序子数组 对于连续的三个数 a[i-1], a[i], a[i+1]：  如果 a[i] >= a[i-1] 且 ...

题目链接 小苯的区间删除 题目描述 小苯有一个长度为  的数组 ，他想要使得数组有序（单调不降）。为此，他必须选择一段区间 ，将数组的这一段删除，其他的部分（如果存在的话）就按顺序拼在一起。 现在他想知道有多少种不同的选择区间的方案。注：小苯认为，空数组也满足有序，即你可以选择  这个区间。 输入:  第一行一个正整数 ，表示数组的长度 第二行  个正整数 ，表示数组   输出:  一个正整数表示答案  解题思路 这是一个区间问题，可以通过以下步骤优化解决：   关键发现：  对于每个位置 i，我们可以预处理：  p[i] 表示从位置 i 向左最多有多少个连续递增的数 s[i] 表示从位置 i...

题目链接 小红的蛋糕切割 题目描述 小红拿到了一个矩形的蛋糕，共分成了  行  列，共  个区域，每个区域是一个小正方形，已知蛋糕每个区域都有一个美味度。 小红希望切割出一个正方形的小蛋糕（正方形边长必须平行于矩阵的边长，且必须都是完整的区域），自己吃掉正方形的部分，把剩下的部分给小紫吃。 小红希望两人吃的部分的美味度之和尽可能接近，小红吃的蛋糕美味度之和为 ，小紫吃的蛋糕美味度之和为 ，请你输出  的最小值。 输入:  第一行输入两个正整数  和 ，代表蛋糕区域的行数和列数 接下来  行，每行输入  个正整数，表示每个区域的美味度  输出:  一个整数，代表  的最小值  解题思路 这是一个...

题目链接 Y型树 题目描述 给出  个顶点，你可以将这些顶点构成一棵树。若这棵树恰好只有三个分叉（即存在一个点，从这个点出发恰好有三条不同的路径到叶子节点），那么我们称这种树为Y型树。 现在给出  个顶点，请你求出可以由这些顶点构建的Y型树有多少种？ 输入:  一个整数 ，表示顶点的个数  输出:  一个整数，表示可以构建的Y型树的数量（对  取模）  解题思路 这是一个数学问题，可以通过以下步骤解决：   数学推导：  设 n-1 个点分成三组，每组至少一个点 每组点数的和为 n-1（除去分叉点） 最大组的点数不能超过 (n-1)/3    计算策略：  使用等差数列求和公式计算部分结果 通...

题目链接 小红的魔法药剂 题目描述 小红需要  个不同的魔法药剂。对于第  种药剂：  可以从商店以  的价格购买红色版本 也可以用两种其他的红色版本药剂配置成蓝色版本  小红想知道，她最少需要花多少钱才能得到 1 到  个不同的魔法药剂（蓝色或红色都可以）。 输入:  第一行输入一个整数 ，表示魔法药剂数量 第二行输入  个整数 ，表示第  种红色版本魔法药剂的价格 接下来  行，每行两个整数  和 ，表示用第  种和第  种红色版本魔法药剂配置第  种蓝色版本魔法药剂  输出:  一个整数，表示最少需要的花费  解题思路 这是一个贪心问题，可以通过以下步骤解决：   关键发现：  对于每种...

多边形 问题描述 多边形处理平面上由多条线段围成的封闭图形，包括面积计算、点位置判断等。常用于区域判断和几何构造问题。 基本操作 算法思想  使用点序列表示多边形 基于向量和叉积计算 适用于面积和位置判断 时间复杂度   代码实现   c++   java   python   class Polygon { public: vector<Point> points; // 按顺时针或逆时针顺序存储顶点 Polygon(vector<Point> p = {}) : points(p) {} // 计算多边形面积 double area() const { double...

圆圆关系 问题描述 圆圆关系处理平面上两个圆之间的基本关系，包括相交判断、交点计算等。常用于碰撞检测和几何构造问题。 基本操作 算法思想  使用圆心距离判断 基于半径关系判断 适用于相交和包含判断 时间复杂度   代码实现   c++   java   python   class Solution { public: // 判断两圆位置关系 // 返回值: -2内含 -1内切 0相交 1外切 2相离 int circlePosition(const Circle& c1, const Circle& c2) { double d = c1.center.distance(c2...

数位 DP 问题描述 数位动态规划是指统计满足某些条件的数字个数的问题。 常见的有统计区间内数字出现次数、数字计数等。 通常需要按位考虑，从高位到低位进行状态转移。 数字计数 算法思想  定义dp[pos][sum][limit]表示当前第pos位，已有和为sum，是否有限制的方案数 对于每一位，枚举可以填的数字 状态转移时需要考虑是否受到上限的限制 最终将所有合法方案数相加  代码实现   c++   java   python   class Solution { vector<int> digits; vector<vector<vector<int>...

树形 DP 问题描述 树形动态规划是指在树结构上进行状态转移的问题。 常见的有树的最大独立集、树的直径等。 通常需要定义状态表示树上某个节点的最优解。 树的最大独立集 算法思想  定义dp[i][0/1]表示以i为根的子树中，不选/选择i节点的最大独立集大小 如果选择当前节点，则子节点不能选 状态转移方程：  dp[i][0] = sum(max(dp[j][0], dp[j][1])) 其中j是i的子节点 dp[i][1] = 1 + sum(dp[j][0]) 其中j是i的子节点   最终答案为max(dp[root][0], dp[root][1])  代码实现   c++   java...