讨厌鬼购物 [题目链接](https://www.nowcoder.com/practice/61d88882485e4a49bfc26c517ca169bd) 思路 有两家店  和 ，出售相同的  类商品。第  类商品在  店售价  元、评分  分，在  店售价  元、评分  分。 如果某类商品在其中一家店的价格严格更低且评分严格更高，讨厌鬼就一定会买。问一共有多少类商品一定会被购买。 判定条件 对第  类商品，满足以下任一条件即可：   且 （在  店买更划算）  且 （在  店买更划算）  直接遍历所有商品，逐个判断即可。 复杂度  时间复杂度： 空间复杂度：  代码 [sol-C++]...

讨厌鬼进货 [题目链接](https://www.nowcoder.com/practice/be73fed67d1b4bceab9e05959d295e49) 思路 讨厌鬼需要购买  种货物，有三种渠道：供货商 A、供货商 B 和网购。网购是一次性买齐所有  种货物，总价为 。而从 A、B 处购买可以逐件选择，因此对每件货物取 A、B 中的较低价即可。 贪心策略 对于从供货商购买的方案，每种货物独立选择，取  再求和，得到线下最优总价 。 最终答案就是线下最优总价和网购总价的较小值：。 样例演示 5 种货物，网购总价 。    货物 A 价格 B 价格 取最小     1 2 1 1   2...

小红的小红树 [题目链接](https://www.nowcoder.com/practice/e0c409d06d0e4fef94e93f34215a0df4) 思路 乍一看这道题，很多同学会以为是"树上最大匹配"，但仔细读题会发现关键区别：操作只是把一对白色结点中的一个染红，另一个保持白色，可以反复参与后续操作。 朴素想法的陷阱 最容易犯的错误是认为"每个红色结点必须有一个永远保持白色的邻居"。但实际上，操作是有时序的：先把 A 染红（此时 B 是白色的帮手），之后再把 B 也染红（用 B 的另一个白色邻居 C 当帮手）。A 虽然失去了白色帮手 B，...

小红删数字 [题目链接](https://www.nowcoder.com/practice/1287555d90d34de3be4ae338b18c1fbd) 思路 每次操作取数组最后两个数  和 ，删除后将  或  放回末尾。操作  次后只剩一个数。问最终结果为  的方案数各是多少。 关键观察 由于每次操作的结果都取个位数，后续运算也只关心个位数，因此整个过程只和每个数的个位有关。 操作顺序是固定的：每次取最后两个元素，所以第一次操作一定是合并  和 ，第二次是合并结果与 ，以此类推。合并的顺序从右往左是确定的，每步只有加法或乘法两种选择。 DP 定义 设  表示当前从右侧已处理的元素合并...

小红的棋盘 [题目链接](https://www.nowcoder.com/practice/b4613aeaf115436394d87cf9db1098ca) 思路 给定一个  的棋盘，需要找出所有由 X 构成的正方形的方案数。注意正方形不限于轴对齐，可以是任意旋转角度的正方形。 核心思想：枚举边 + 旋转验证 一个正方形由四个顶点确定。如果我们枚举所有可能的四元组，复杂度为 （ 为棋子数），太高了。 更好的做法是枚举正方形的一条边。对于正方形的任意一条边 ，另外两个顶点的位置是唯一确定的——只需将向量  旋转  即可得到。 具体地，设两个棋子坐标为  和 ，令 ，，则：  方向一（顺时针旋...

小红的矩阵染色 [题目链接](https://www.nowcoder.com/practice/f8b771318bb04490b7389cc35e148166) 思路 问题分析 给定一个  的矩阵，其中 * 是黑色格子，o 是白色格子。我们最多可以将  个白色格子染成红色。计分规则：如果一个红色格子的正下方也是红色格子，则该红色格子得 1 分。求最大得分。 关键观察：按列分析 得分只与同一列中上下相邻的红色格子有关，不同列之间互不影响。因此可以独立地看每一列。 在某一列中，黑色格子将白色格子分割成若干连续白色段。例如列 o o * o o o 包含两段，长度分别为 2 和 3。 段内染色的...

小红的回文串 [题目链接](https://www.nowcoder.com/practice/f63e9827b5e349179becdce3bd3be8ca) 思路 本题有两种操作：把首字符移到末尾（旋转）和将任意字符改为任意字母。目标是用最少的总操作次数把字符串变成回文串。 枚举旋转次数 操作一本质上是对字符串做左旋转。旋转  次后，原串  变为 。 对于旋转后的字符串，要将其变成回文串，只需数有多少对位置  上的字符不同，每对不同只需一次操作二即可修复。 因此，枚举旋转次数 （从  到 ），总操作次数为： $$ 答案即为 。 样例演示 对 ：  ：串为 aacde，不匹配对 ，cost...

小红的蛋糕切割 [题目链接](https://www.nowcoder.com/practice/ea72b571afdb499fa344e56f06b5c71c) 思路 给定  的矩阵，需要从中切出一个正方形子矩阵，使得切出部分的美味度之和  与剩余部分的美味度之和  的差的绝对值  最小。 转化问题 设矩阵所有元素之和为 ，则： $$ 因此问题转化为：枚举所有可能的正方形子矩阵，找到子矩阵和  使得  最小。 二维前缀和 用二维前缀和数组  表示矩阵左上角  到  的元素之和。建立前缀和后，任意以  为左上角、 为右下角的子矩阵之和可以  计算： $$ 枚举所有正方形 枚举正方形的边长 （...

小红的皇后 [题目链接](https://www.nowcoder.com/practice/32b1af25432c4774b353c9d628dd9efb) 思路 棋盘上有一个皇后，从左上角  出发，每一步可以沿着右、下、右下对角线三个方向移动任意多格（中途不能越过障碍物），问到达右下角  的最少步数。 这和普通 BFS 有什么区别？ 普通网格 BFS 每次只走一格，而这里一步可以"滑行"整条直线。如果暴力地把每个可达格子都当作一条边来建图，边数可达 ，会超时。 关键优化：沿射线扩展时的剪枝 用标准 BFS 逐层搜索，每次取出一个格子 ，设其距离为 ，然后沿三个方向一格...

小红吃药 [题目链接](https://www.nowcoder.com/practice/ea822e4a974e4ab0bc72c203adce7d44) 思路 本题是一道位运算模拟题。 问题分析 小红有  种症状，用一个 01 串表示当前的症状状态。每副药有两个属性：  治疗掩码：能治好哪些症状（对应位清零） 副作用掩码：会新增哪些症状（对应位置一）  题目保证同一副药的治疗掩码和副作用掩码不会在同一位上都为 1。 位运算建模 将症状状态和每副药的治疗/副作用都用二进制整数表示。设当前症状状态为 ，服用第  副药时： $$  ：把能治好的症状位清零 ：把副作用对应的症状位置一  每次操作...

小红的兽 [题目链接](https://www.nowcoder.com/practice/c0503d04a0324dac8bd85507773d8a80) 思路 本题是一道模拟题，按照题意逐轮处理遭遇事件即可。 战斗触发条件 两个单位  和  遭遇时， 表示  是否向  公布身份， 表示  是否向  公布身份。战斗是否发生取决于以下规则：  兽发现对方是人：如果  是兽，且  公布了身份（），且  是人，则兽主动攻击，战斗发生。反之亦然。 人发现对方是兽：如果  是人，且  公布了身份（），且  是兽，则人只在自己战斗力严格大于对方时才发起攻击。反之亦然。 同阵营：无论是否公布身份，都不会...

小红笔试 [题目链接](https://www.nowcoder.com/practice/a165da3628d6438495da2f789fb3d3c0) 思路 本题是一个经典的分组背包问题。每道题有三种选择：写正解（A）、写暴力（B）、放弃（F），需要在总时间  内最大化总得分，并输出具体方案。 建模 将总时间视为背包容量，每道题视为一组物品：  A：耗时 ，得分  B：耗时 ，得分  F：耗时 ，得分   每组恰好选一个，这就是标准的分组背包。 DP 定义与转移 定义  为前  道题、耗时恰好为  时的最大得分。转移方程： $$ 方案回溯 在 DP 过程中，记录每个状态  的最优选择（...

小红的夹吃棋 [题目链接](https://www.nowcoder.com/practice/364c9d2c2af247ddb7df8f71f5f7ca5e) 思路 纯模拟题。在  的棋盘上，判断黑棋和白棋是否被"夹吃"。 夹吃判定 对于棋盘上的每个棋子，检查它是否被对方颜色的棋子夹住：  横向夹吃：当前棋子位于某行的中间位置（列号为 1），且左右两侧都是对方棋子。 纵向夹吃：当前棋子位于某列的中间位置（行号为 1），且上下两侧都是对方棋子。  只要存在任意一个黑棋被白棋夹住，就认为"黑棋被夹吃"；白棋同理。 胜负判定 用两个布尔变量分别记录黑棋是否...

小红购物 [题目链接](https://www.nowcoder.com/practice/d4e0c4c4e5154787b7ddc9141d64deda) 思路 本题的核心是：对每件商品，在所有适用的优惠券中选一张折扣最大的使用。 优惠券  对价格为  的商品适用，当且仅当 ，此时可以减去 。每件商品最多用一张券，每种券不限次数。 贪心 + 排序 + 二分 关键观察：对于价格为  的商品，所有满足  的优惠券都可以使用，我们只需要找到其中  最大的那张即可。 做法：  将优惠券按门槛  从小到大排序。 构造一个前缀最大折扣数组 ：表示前  张优惠券中折扣的最大值。即 。 对于每件价格为  ...