项目组建问题 [题目链接](https://www.nowcoder.com/practice/e363e99bc8144436b4e0f0b8f1ed481d) 思路 给定项目所需的开发角色编号数组 reqSkills，以及每位工程师能承担的角色数组 peoSkills，要求选出人数最少的工程师组合，使其技能并集覆盖所有所需角色。若存在多种最少人数方案，输出编号字典序最小的。 状压 DP 所需角色数量有限（最多 20 左右），可以用位掩码表示角色覆盖状态。  角色编号映射：将 reqSkills 中每个角色映射到一个比特位 。目标状态为 （全部覆盖）。   工程师技能掩码：将每位工程师的技能...

礼品派发 [题目链接](https://www.nowcoder.com/practice/f19531dcc5e243b98a9826ee8849cfd2) 思路 本题是经典的 K 等和子集划分 问题：给定一组礼品价格和粉丝人数 ，判断能否将所有礼品分成  组，使每组价格之和相等。 回溯 + 剪枝  基本判断：若总价格不能被  整除，直接返回 false。每组的目标价格为 。   降序排序：将价格从大到小排序，这样能更早触发剪枝（大的放不下就提前回退）。   回溯搜索：维护  个桶，依次尝试将每个礼品放入某个桶，若桶内累加值不超过  就递归下一个礼品。   关键剪枝：   - 如果当前桶的值...

给3个组员分配任务 [题目链接](https://www.nowcoder.com/practice/dbf078efb7b64f80806fbf33b9b19cf5) 思路 将  个任务分配给三位员工，每人分别不超过 、、 个，求方案数。 直接枚举：设员工小v分到  个任务，员工小i分到  个任务，则员工小o分到  个任务。只需满足：     且   枚举  和 ，检查  是否合法即可。由于 ，双重循环最多  次，完全没有性能问题。 代码    C++   Java   class Solution { public: int assignJobs(int n, int x, int y, ...

员工分组 [题目链接](https://www.nowcoder.com/practice/bbfaec07fc7c4763bed03fc9c0e23283) 思路 本题要求将新老员工分成最少的组，需要遵守三条规则：  每组最多 3 人； 每组最多 1 个老员工； 如果组里有老员工，则该组最多 2 人。  贪心策略 统计老员工数量  和新员工数量 。 老员工必须独占一组（因为每组最多 1 个老员工），但每个老员工的组里还能带 1 个新员工（组上限为 2 人）。因此优先把新员工塞进老员工的组里，能消耗掉  个新员工。 剩余的新员工每 3 人一组，即需要  组。 最终答案为： $$ 样例验证  [...

小苯的最小好数 [题目链接](https://www.nowcoder.com/practice/9ae46830704e4d2399f025074ffcb949) 思路 给定正整数 ，求不小于  的最小"好数"，即所有数位互不相同的数。 回溯（DFS）逐位试填 从最高位到最低位，依次尝试填入数字。核心思想类似数位 DP 中的"贴上界"：  贴上界阶段：如果前面所有位都和原数一样（还没有变大），当前位只能从  对应位的数字开始往上尝试，不能更小。 松弛阶段：一旦某一位填了比原数更大的数字，后续所有位可以从  开始自由选取（只要没被用过）。 去重约束：用一...

小苯的格子移动 [题目链接](https://www.nowcoder.com/practice/d1c43a534cb943398e6fafcc5e27aefb) 思路 数轴上有  个格子，第  个格子的解锁时间为 （保证 ）。从第 1 个格子出发，每秒可以移动到下一个格子（前提是已解锁）或原地等待。求到达第  个格子的最少时间。 贪心模拟 用  记录当前时间，初始为 0（在第 1 格）。依次考虑移动到第  格：  移动需要 1 秒，所以最早到达时间为 ； 同时第  格需要在  时刻后才能到达。  因此到达第  格的最早时间为： $$ 这是最优策略：能走就走，不能走就等。不存在"提...

小红的可爱括号串 [题目链接](https://www.nowcoder.com/practice/ec6b4a16994b4c6cb5c156f5cb40e5ca) 思路 题目定义"可爱括号串"为前半全是左括号、后半全是右括号的偶数长度括号串，即形如  的串。我们需要统计原串中有多少个子序列构成可爱括号串。 拆解问题 一个可爱子序列由  个 ( 紧跟  个 ) 组成，且在原串中所有被选中的 ( 都出现在所有被选中的 ) 之前。那么，我们能否找到一个"分界点"来把选取的左右括号分开呢？ 枚举第一个右括号 关键思路是：枚举可爱子序列中最左边的那个 )。假设...

字符串奇偶性问题 [题目链接](https://www.nowcoder.com/practice/49b1dfff37014c17bd726796ee5ef388) 题意 对于长度为  的字符串 ，定义  为：   的全部奇数位字符（位置 1, 3, 5, ...），按字典序从小到大排序； 拼接上  的全部偶数位字符（位置 2, 4, 6, ...），按字典序从大到小排序。  给定长度为  的字符串 ，取出其所有长度为  的子串，分别构造  值，统计有多少个不同的  值。 字典序按 ASCII 码，大写字母 (A=65) 小于小写字母 (a=97)。 思路 关键观察  的值仅取决于子串中奇数...

小红的字符串匹配 思路 这道题乍一看需要对每个查询字符串  判断很多前缀和后缀，好像很复杂。我们来一步步拆解。 问题本质是什么？ 对于字符串 ，我们要检查两件事：   的某个长度  的前缀是  的子串  的某个长度  的后缀是  的子串  只要任意一个成立就输出 YES。 前缀的关键观察 如果我们从左到右逐字符把  喂进  的后缀自动机（SAM），只要走到第  步还没有失配，就说明 （长度为  的前缀）是  的子串，可以直接返回 YES。如果在某一步失配了，那更长的前缀也不可能是  的子串（因为前缀有包含关系），可以直接返回 NO。 后缀怎么处理？ 后缀的判断可以巧妙转化： 的后缀是  的子串...

小红的异或之和 思路分析 拿到这道题，我们首先要搞清楚：矩阵  的所有子矩阵之和到底怎么算？ 暴力枚举所有子矩阵肯定不行。那我们换个角度想：每个元素  会被多少个子矩阵包含？ 一个子矩阵由左上角  和右下角  确定。如果  被包含，需要  且 。 用 1-indexed 来算：   有  种选法（ 到 ）， 有  种选法（ 到 ）  有  种选法， 有  种选法  所以  的贡献次数为 。 接下来，注意到贡献次数可以行列分离：定义行权重 ，列权重 ，那么： $$ 由于 ，异或结果只有两种情况：  ：，对应  的列 ：，对应  的列  因此我们预处理出  和 ，然后对每一行 ：  若 ，贡献为 ...

模串 思路分析 这道题其实就是一道纯模拟题，但我们需要仔细读清楚题意。 题目说的是什么呢？小歪有一个数字 ，初始为零。他依次读入  个字符串，对于第  个字符串，执行以下操作：  如果第  个字符串的长度  满足 ，则  加一； 否则， 减一。  最终要求整个过程中  能达到的最大值。 那思路就很直接了：逐个读入字符串，每读一个就判断长度模  是否等于下标模 ，然后更新 ，同时维护一个最大值即可。 我们来手动模拟一下示例 1：，字符串分别为 "d", "dd", "ddd", "ddddd", "d&qu...

小苯的美丽区间 [牛客链接](https://www.nowcoder.com/practice/b80c412275d44f2c8312cfedaa630faa) 题意 一个正整数  是「美丽数」当且仅当它是  的幂次。美丽值定义为 （即不断除以  的次数），非美丽数的美丽值为 。 给定长度为  的正整数数组 ，求所有连续子数组之和的美丽值之和。 思路 枚举  的幂次 + 前缀和哈希 暴力枚举所有子数组是 ，但注意到一个子数组和  只有在  时才有贡献 ，而  的取值只有  种（ 为数组总和），这就为我们打开了突破口。 核心思路：把"枚举子数组"转化为"枚举目标...

小红的纸牌游戏 [题目链接](https://www.nowcoder.com/practice/a454e716209c467c924577295f6e0d8d) 思路 本题是一个博弈 + 贪心问题。 张纸牌排成一行，每张上面写着  或 。小红和小紫轮流取走一张牌（小红先手），直到剩下  张牌，剩余牌按原始顺序拼成一个二进制数。小红想让这个数尽可能大，小紫想让它尽可能小。 贪心策略 二进制数的高位比低位重要得多，因此双方都应该优先影响高位。对于每一方：  小红（最大化）：希望高位是 ，因此她应该移除最左边的 。去掉一个靠前的 ，相当于让后面的  顶上更高位。如果没有  可移除（全是 ），那移...

小红的相等数组 [题目链接](https://www.nowcoder.com/practice/d45de1dae26a49bca9d8832b9551737f) 思路 构造长度为  的数组，每个元素在 ，要求所有元素的异或和  不超过与和 。统计方案数，对  取模。 逐位分析 异或和与按位与都是逐位运算。对于第  位，设  为  个元素中该位为 1 的个数，则：  AND 第  位  当且仅当  XOR 第  位  当且仅当  为奇数  要满足 ，从最高位到最低位扫描，第一个  和  不同的位必须是 （即  在该位赢了）。 每一位有三种状态：    状态 条件 含义     相等 (E) ...