题目链接 灵异背包？ 题目描述 给定  个正整数 ，你可以任选其中若干个数放入一个“灵异背包”。要求背包内所有数之和为偶数，并且在这个前提下，和要尽可能大。 如果一个数也不选，则背包和为0。请输出可以获得的最大偶数和。 解题思路 这是一个基于奇偶性的贪心问题。我们的目标是获得最大的偶数和。 1. 从最大和出发 要使和尽可能大，我们最理想的情况是把所有的数都选上。设所有数的总和为 total_sum。现在我们基于这个最大可能的和进行分类讨论。 2. 分类讨论   情况一：total_sum 本身是偶数 如果所有数的总和本来就是偶数，那么这已经是我们能得到的最大和了，并且它满足条件。因此，直接选择...

题目链接 小红的字符串 题目描述 小红有一个长度为  的小写字母字符串 。她可以对字符串进行任意次操作：选择一个下标 ，将字符  循环右移到字母表中的下一个字母（例如 'a' 变成 'b'，'z' 变成 'a'）。 请计算，使字符串  变为回文串所需的最少操作次数。 解题思路 本题的目标是，用最少的操作次数将一个字符串变为回文串。操作的本质是改变字符。 1. 回文串的性质 一个字符串是回文串，意味着对于所有 ，第  个字符都必须和倒数第  个字符（即下标为  的字符）相同。因此，我们的任务就是让每一对对称位置的字符  变得相同。 2. 计算单对字符的最小操作数 总的最少操作次数，等于所有对称字...

题目链接 清楚姐姐买竹鼠 题目描述 清楚姐姐需要购买至少  只竹鼠。商店提供两种购买方式：  花费  元购买1只竹鼠。 花费  元购买3只竹鼠。  求买到至少  只竹鼠所需的最小花费。 解题思路 这是一个典型的优化问题，我们需要在不同的购买组合中找到总价最低的方案。问题的核心在于比较两种购买方式的“单价”。 1. 比较单位成本 我们可以比较买3只竹鼠的两种方式的成本：  方式一：买3次单只的，成本为 。 方式二：买1次3只装的，成本为 。  这将我们的决策分为两种主要情况： 情况一：  在这种情况下，单独购买3只竹鼠比打包购买更便宜或价格相等。这意味着打包购买没有任何优势。 因此，最优策略是全...

题目链接 讨厌鬼进货 题目描述 讨厌鬼需要采购  种货物，每种货物都至少要购买一件。对于第  种货物，她有两种独立的购买方式：  从供应商A处以  元的价格购买。 从供应商B处以  元的价格购买。  此外，还有第三种打包购买方式： 3. 在网购平台一次性购买全部  种货物，总花费为  元。 可以自由组合以上方式，求满足每种货物都至少有一件的最小总花费。 解题思路 这是一个典型的决策问题，我们需要在两种主要的采购策略中选择花费更小的一种。 策略一：完全不使用网购平台 在这种策略下，我们完全放弃网购平台的打包优惠。对于需要的每一种货物 （从1到），我们都必须独立购买。为了使花费最小，我们应该为每种...

题目链接 小红的优惠券 题目描述 小红的购物车结算金额为  元，她手中有  张优惠券。第  张优惠券的规则为“满  元立减  元”。这意味着，只有当  时，这张优惠券才能使用，使用后可以减免  元。 小红最多只能使用一张优惠券。请问，她最少需要支付多少元？ 解题思路 这是一个简单的决策问题。小红的目标是最大化优惠金额，从而最小化支付金额。 决策过程如下：  初始状态：如果不使用任何优惠券，小红需要支付  元。我们可以将这个金额作为初始的“最小支付金额”。 遍历所有选项：小红需要检查她手中的每一张优惠券，看看哪一张能给她带来最大的优惠。 筛选可用优惠券：对于第  张优惠券（满  减 ），首先要判...

题目链接 最大 FST 距离 题目描述 给定  个元素，第  个元素具有特征值 。定义两个元素  和  之间的 FST 距离为：  请计算所有元素对中的最大 FST 距离。 解题思路 这是一个求解最大距离的问题。如果采用暴力法，遍历所有可能的元素对  来计算距离，时间复杂度将是 ，对于  较大的情况会超时。因此，我们需要对公式进行分析和优化。 1. 公式分析与几何解释 FST 距离的公式  实际上是二维平面上两点之间的曼哈顿距离。 我们可以将每个元素  看作是平面上的一个点 ，其坐标为 。这样，FST 距离  就是点  和  之间的曼哈顿距离。问题就转化为了：在由  个点组成的点集中，找出曼哈...

题目链接 谐距下标对 题目描述 给定一个长度为  的整数数组 。若下标对  满足  且 ，则称  为一对谐距下标对。请计算数组中的谐距下标对数量。 解题思路 这是一个计数问题，直接使用暴力法（双重循环）检查所有下标对  的时间复杂度为 ，在  较大时会超时。我们需要寻找一种更高效的解法。 核心思想：公式变形 题目的核心条件是 。我们可以对这个等式进行移项变形：  这个变形是解题的关键。它告诉我们，如果一对下标  是谐距下标对，那么它们对应的 “值-下标” 这个差是相等的。 问题转化 令 ，那么原问题就等价于：统计有多少对下标  满足  且 。 这个问题就转化成了一个经典的频次统计问题。我们可以...

题目链接 小红背单词 题目描述 小红按顺序背  个单词。她记住一个新单词的规则如下：如果她已经记住了  个单词，那么她需要背一个没有记住的新单词  次，才能记住这个新单词。 请根据小红背单词的顺序，计算她最终记住了多少个单词。 解题思路 这是一个模拟题，我们需要精确地追踪小红的记忆状态。具体来说，需要记录两类信息：  已经记住的单词集合：哪些单词已经被小红完全掌握。 正在背的单词的次数：对于那些尚未记住的单词，它们各自被背了多少次。  算法步骤如下：  初始化数据结构：  使用一个哈希集合（set）来存储已经记住的单词，我们称之为 known_words。这可以让我们快速判断一个单词是否已被记...

题目链接 小红书推荐系统 题目描述 根据小红的搜索记录（一个由空格分隔的单词组成的字符串），找出所有的“关键词”。一个单词被称为“关键词”，当且仅当它在搜索记录中出现的次数不少于3次。 请输出所有关键词，并遵循以下排序规则：  按出现频次从高到低排序。 如果频次相同，则按字典序升序排序。  解题思路 这是一个典型的词频统计和自定义排序问题。我们可以分步解决： 1. 词频统计 首先，我们需要知道每个单词在输入字符串中出现了多少次。最适合这个任务的数据结构是哈希表（在C++中是 map，Java中是 HashMap，Python中是 dict）。  我们先将输入的整行字符串按空格分割成一个个独立的...

题目链接 小红的矩阵染色 题目描述 小红有一个  的矩阵，其中一些格子是黑色的 ('*')，另一些是白色的 ('o')。她最多可以把  个白色格子染成红色。 计分规则是：如果一个红色格子下方相邻的格子也是红色，那么这个红色的格子可以获得1分。请问小红最多可以得到多少分？ 解题思路 这是一个典型的贪心策略问题。我们的目标是用有限的资源（最多染  个格子）来获得最大的收益（分数）。 1. 分析得分方式与成本  得分方式：分数只能由垂直相邻的一对红色格子产生。具体来说，一对上下的红色格子可以为上面的那个格子贡献1分。 成本分析：为了获得分数，我们必须至少染两个垂直相邻的白色格子。  染一对垂直相邻的...

题目链接 BGN23 支付宝消费打折 题目描述 小苯在超市购买  种物品，每种物品只能购买一个。他的支付宝余额为  元。 部分物品支持“九五折”优惠。给定每种物品的价格以及是否支持优惠，请问他仅用支付宝支付，最多能买几件物品？ 输入描述 第一行两个正整数 。 第二行包含  个正整数 ，表示第  个物品的价格。 第三行一个长度为  的字符串，由 '0' 和 '1' 组成。如果第  个字符是 '1'，代表第  个物品支持优惠，否则不支持。 输出描述 输出一行一个整数，表示最多能购买的物品数量。 样例 输入 5 9 3 4 2 3 1 11101  输出 4  解题思路 本题的目标是在有限的预算内，...

题目链接 BGN22 小苯送礼物 题目描述 小苯是“小红书app”的一名博主，他有  名粉丝，编号从 1 到 。他想选择其中对他支持力度最大的前  名粉丝送礼物。 支持力度计算：  每点一次赞，增加 1 点支持力度。 每收藏一篇文章，增加 2 点支持力度。  筛选规则（按优先级）：  总支持力度：越高越好。 收藏数：如果支持力度相同，收藏数越多越好。 粉丝编号：如果前两者都相同，编号越小越好。  请你帮小苯找出他应该送礼物的  名粉丝的编号。 输入描述 第一行两个正整数 。 接下来  行，每行两个整数 ，分别表示第  位粉丝的点赞数和收藏数。 输出描述 输出一行  个正整数，表示小苯选择的粉丝...

题目链接 BGN21 分数线划定 题目描述 某市为世博会选拔志愿者，先进行笔试，再按笔试成绩划定面试分数线。规则如下：  计划最终录取  名志愿者。 面试名额定为 ，向下取整，记为 。 将所有报名号及笔试成绩按 成绩从高到低、成绩相同则报名号从小到大 的规则排序。 第  名选手的成绩即为面试分数线。 所有笔试成绩不低于该分数线的选手均进入面试。  请输出面试分数线及所有进入面试选手的信息（按排序后的顺序）。 输入描述 第一行输入两个整数 ，分别表示报名人数与计划录取人数。 接下来  行，每行输入两个整数 ，分别为报名号与笔试成绩。报名号保证唯一。 输出描述 第一行输出两个整数：面试分数线和进入...

题目链接 BGN20 【模板】排序 题目描述 给定一个长度为  的整数数组 （允许元素重复），请将其按非递减顺序排序并输出。 输入描述 第一行输入整数 ，表示数组长度。 第二行输入  个整数 。 输出描述 在一行上输出排序后的数组，各元素以空格分隔。 样例 输入 5 5 4 3 2 1  输出 1 2 3 4 5  解题思路 本题是排序算法的模板题，要求对一个整数数组进行非递减排序。 最直接、高效且在竞赛中常用的方法是利用各编程语言标准库中内置的排序函数。这些函数通常经过了高度优化（例如，C++的 std::sort 通常是内省排序，Java的 Arrays.sort 对基本类型是双轴快排，P...