小O的整数操作 [题目链接](https://www.nowcoder.com/practice/52e3cbb106d54366a3f5fefac03d169f) 题目理解 给定整数 、目标值  和除数 ，每次可以执行以下操作之一：   （仅当  时）  求将  变为  的最少操作次数。 思路：贪心 关键观察：每次除以  能将  快速缩小，而减 1 每次只减少 1。因此，只要除以  不会让  低于目标值 ，就应该尽量利用除法。 贪心策略：从  出发，每一步：  若 ，无法通过除法缩小 ，只能减法：答案 ，结束。 若  能被  整除，且 ：执行一次除法（操作数 ，）。 若 （除法会越过目标）：...

小O的子序列最值 [题目链接](https://www.nowcoder.com/practice/c7e5b649799845dca44b2f9ba0f02177) 题意 给定两个长度为  的数组  和 ，从  和  中各选一个非空子序列，要求  所选子序列的最大值不大于  所选子序列的最小值。求两个子序列长度之和的最大值。若无法找到满足条件的选法，输出 。 思路 枚举阈值 设"阈值"为 ，表示第一个子序列的最大值（即 ，同时 ）。 对于给定阈值 ：  第一个子序列中可以选  中所有  的元素，全选最优，数量为 。 第二个子序列中可以选  中所有  的元素，全选最优，数量...

小O的子序列最值(二) [题目链接](https://www.nowcoder.com/practice/ccde5aaa096f418b81ee6ed9dc253504) 题意 给定两个长度为  的数组  和 ，从  和  中各选一个非空子序列，要求  所选子序列的最大值不大于  所选子序列的最小值。求满足条件的选法总数，答案对  取模。 思路 枚举最大值分组 将两个数组分别排序。 对于从  中选取的子序列，其最大值是确定的。我们可以枚举  中每个不同的值  作为所选子序列的最大值，然后对每个 ：  统计从  中选出最大值恰好为  的非空子序列数。 统计从  中选出最小值  的非空子序列数。...

小O的叶子 [题目链接](https://www.nowcoder.com/practice/e0b315f386354e0fbcfd4f69ece56a3a) 思路 给定一棵  个节点的树，枚举删除每个节点后，统计剩余森林中叶子节点（度恰好为 1 的节点）的数量，取最大值。 关键观察 暴力枚举每个节点并重新统计叶子数是  的。注意到树的边数为 ，度数之和为 ，可以用差量法将整体复杂度压到 。 设原树中叶子节点数为 （度为 1 的节点数），现在枚举删除节点 ：   自身的影响：若 ，则  本身是叶子，删除后少一个叶子，。    的邻居的影响：删除  后， 的每个邻居  的度减少 1，即 ：  ...

小O的字符串重排 [题目链接](https://www.nowcoder.com/practice/729b24646e17478db41e4ad2675e9d7e) 思路 给定字符串 （全小写），以及两个模式串 （首字母大写，其余小写）。可以任意重排  并改变大小写，求新串中最多能包含多少个不重叠的  或  子串。 关键观察 由于可以任意重排和任意改变大小写，我们可以自由地把字符放到任何位置并赋予任何大小写。因此问题本质上和位置、大小写无关，只和字母频次有关。 将所有字符统一为小写来计数：  统计  中各字母出现次数 ； 统计  中各字母出现次数 （忽略大小写）； 统计  中各字母出现次数 ...

诗 [题目链接](https://www.nowcoder.com/practice/7eef94e6f96f401b9078213cbc6c7eaf) 思路 模拟题。按照规则将字符串分行：第 1 行取 1 个字符，第 2 行取 2 个字符，第 3 行取 3 个字符……每行的首字母位置依次是 ，即第  行（从 1 开始）的首字母下标为 。 只需用一个指针 pos 从 0 开始，每次取 s[pos] 加入答案，然后 pos += k（k 从 1 递增），直到 pos 超出字符串长度。 时间复杂度 （行数约为 ），空间复杂度 。 代码    C++   Java   #include <io...

游游的数组染色 [题目链接](https://www.nowcoder.com/practice/d0733785b73f4430aa735d15452b72ab) 思路 给定数组，选择若干元素涂黑，得分为 黑色数字的最小值 + 黑色数字的个数，求最大得分。 关键观察 假设我们选了  个数，为了让最小值尽可能大，一定选最大的  个数。将数组降序排序后，选前  个，最小值就是 ，得分为 。 算法  将数组降序排序。 枚举 ，计算 ，取最大值即可。  时间复杂度 ，瓶颈在排序。 代码 C++ #include <bits/stdc++.h> using namespace std; i...

移山 [题目链接](https://www.nowcoder.com/practice/d917144251c6433ca633112d83c4422a) 思路 给定  个山头的初始高度和  次施法操作，每次操作将区间  内的所有山头高度减少 。问最早在第几次操作后，存在某个山头高度 。 关键观察：答案具有单调性 如果前  次操作后已经有山头 ，那么前  次操作后也一定有（因为只减不加）。因此可以二分答案。 二分 + 差分数组 对于二分的 ，我们需要快速判断：执行前  次操作后，是否存在某个山头高度 。 每次操作是区间减法，可以用差分数组在  时间内记录每次操作，最后做一次前缀和即可得到每个位...

偏爱的字符 [题目链接](https://www.nowcoder.com/practice/294da7ea5f184655a31bf659035fc874) 思路 对于每个非偏爱字符，需要找到距离它最近的偏爱字符来替换。如果距离相同则选左边的。 暴力做法是对每个位置扫描整个字符串找最近偏爱字符，时间复杂度 。可以用两遍扫描优化到 ：  从左到右扫描：记录每个位置左边（含自身）最近的偏爱字符位置 left[i]。 从右到左扫描：记录每个位置右边（含自身）最近的偏爱字符位置 right[i]。  对于每个非偏爱字符位置 ：  左侧距离 （若左边无偏爱字符则为 ） 右侧距离 （若右边无偏爱字符则...

排队选人 [题目链接](https://www.nowcoder.com/practice/8f526def031f43b49d54e71117f6d990) 思路 从  个同学中选出连续  个，要求每个人的能力值 、合作值 ，求方案数。 标记与连续计数 先对每个同学判断是否"合格"（能力值  且合作值 ）。问题转化为：在一个  序列中，有多少个长度为  的子段全为 。 只需维护一个计数器 ，记录当前位置为止连续合格同学的个数：  若第  个同学合格，； 否则 。  每当 ，就找到了一个合法方案（以第  个同学为结尾的连续  人）。 样例验证 能力值 [2,2,9,1,8,...

神奇苹果桶 [题目链接](https://www.nowcoder.com/practice/dec56cf338154d30bd0f56b30ee8769a) 思路 本题是一道简单的模拟题。维护一个变量 apples 表示当前苹果数量（初始为 0），依次处理  次操作：  操作 1（增加）：apples += x 操作 2（取走）：若 apples >= x，则 apples -= x，否则不操作 操作 3（按比例取走）：取走  个苹果，即 apples -= ceil(apples / x)  对于向上取整，可以利用整数运算公式  来避免浮点数精度问题。 注意苹果数量可能较大，需要使...

拉票 [题目链接](https://www.nowcoder.com/practice/f1a2cd7a704443d08221d896d6d7a7c0) 思路 贪心。小明的基础票数是自己阵营  中的人数。他可以额外游说一个阵营，为了票数最大化，显然应该选人数最多的非  阵营。 做法：统计每个阵营的人数，答案 = 阵营  的人数 + 其余阵营中人数最多的那个。若所有人都属于阵营 ，则不需要游说，答案就是 。 时间复杂度 ，空间复杂度 。 代码    C++   Java   #include <bits/stdc++.h> using namespace std; int main...

字符消除 [题目链接](https://www.nowcoder.com/practice/c2d5576d39bf41e99bbe2f5ac9270889) 思路 本题要求将一个偶数长度的字符串通过反复删除相邻字符对完全消除，使得总花费最大化。每次删除相邻的字符  和  花费 ，删除后左右两部分拼接。 区间 DP 这是一个经典的区间 DP 问题。定义  为将子串  完全消除所能获得的最大花费（ 必须为偶数才可能消除干净）。 转移思路：考虑  最终和谁配对消除。 必须和某个  配对，其中  与  的距离为奇数（即 ），这样  和  之间的子串长度为偶数，可以先被完全消除，使得  和  变为相邻...

对比之美 [题目链接](https://www.nowcoder.com/practice/0fcbb83370124426bfee75aca43b7ee7) 思路 给定  个格子和  个收藏品，要求将收藏品放入格子中（每个格子放  个），使美观度  最大。 分类讨论 ：没有相邻对，美观度为 。 ：将所有  个收藏品放在一个格子，另一个放 ，美观度为 。 ：将所有  个收藏品放在某个中间位置（非端点），例如 ，该位置与左右邻居各产生  的差值，美观度为 。 为什么  是上界？注意每个收藏品对美观度的贡献最多为 （它所在格子最多参与两个相邻对的差值），所以总美观度 。当  时，把所有物品放在一个...