毛毛虫 [题目链接](https://www.nowcoder.com/practice/02b12ffe5e374b85bfa7e708abfb038a) 思路 在以 1 为根的有根树上，两只毛毛虫分别从节点  和  出发，只能往更深的方向走，走到叶子节点停下。问所有可能到达的  二元组个数。 关键观察 毛毛虫从节点  出发，能到达的叶子节点恰好就是  的子树中所有的叶子。因此每次询问的答案就是： $$ 其中  表示节点  的子树中叶子节点的数量。如果  本身就是叶子（无子节点），则 。 预处理 由于输入已经按编号顺序给出了每个节点的父亲（），且保证 ，所以我们可以直接按编号从大到小累加： ...

回文串 [题目链接](https://www.nowcoder.com/practice/feb7cc6085e0487dab796e00e53ee772) 思路 本题是一道模拟题。按照题意，依次从字符串  的开头取出长度为  的子串，判断其是否为回文串，然后决定拼接到  的前面还是后面。 模拟过程  将字符串  从左到右每  个字符分成一组，共得到  个子串。 对每个子串判断是否为回文串：   - 如果是回文串，将其拼接到  的前面（prepend）。  - 如果不是回文串，将其拼接到  的后面（append）。  输出最终的 。  使用双端队列（deque）可以方便地实现头部和尾部的插入操...

最长合法子串长度 [题目链接](https://www.nowcoder.com/practice/bda1d9a196644a66a233ab91144b41d4) 思路 给定一个 01 字符串，每次操作可以将一个 '1' 变成 '0'，最多执行  次操作。要求最小化操作后最长全 1 子串的长度。 "最小化最大值" 是经典的二分答案模型。 二分答案 二分目标值 ，表示"操作后最长全 1 子串长度不超过 "，然后贪心判断是否可行。 贪心判定 先预处理出所有极长全 1 段的长度。对于一段长度为  的全 1 段，我们要在其中放置若干个 '0'（即执行若干次操...

小红的链表节点染色 [题目链接](https://www.nowcoder.com/practice/43369411700648e8bc78932bcabf04d0) 思路 题目要求：给定一个链表，其中部分节点已被染成红色（'R'），选择一些未染色节点（'W'）染红，使得所有红色节点的权值之和为偶数。求方案数，对  取模。 关键观察：奇偶性分析 一个数的和是否为偶数，只取决于其中奇数的个数的奇偶性。因此只需关注每个节点值的奇偶性。 将未染色节点分为两类：  偶数值节点（共  个）：无论是否染红，都不改变总和的奇偶性，因此可以任意选择。 奇数值节点（共  个）：每选一个奇数，总和的奇偶性翻转一...

小红的二叉树构造 [题目链接](https://www.nowcoder.com/practice/f798461d82c94959a1922efda1dd05eb) 思路 要构造一棵  层的满二叉树，使得每一层的节点权值和都相等。 关键观察：第  层（从  开始计数）有  个节点。设每层权值和为 ，则第  层每个节点的平均权值为 。为了让所有节点权值都是正整数， 必须是  的倍数（因为最后一层有  个节点）。 最简单的构造方案：取 ，则第  层的每个节点权值为 。  第  层（根节点）：权值为  第  层：每个节点权值为  ... 第  层（叶子层）：每个节点权值为   这样每一层的权值和都...

小红的链表扩展 [题目链接](https://www.nowcoder.com/practice/a260b3c244e4429faa0ccbd9028452eb) 思路 给定一个链表，要求在每两个相邻节点之间插入一个值为 0 的新节点。 做法非常直接：从头节点开始遍历链表，对于每个节点 cur（只要 cur.next 存在），创建一个值为 0 的新节点，将其插入 cur 和 cur.next 之间，然后将指针跳到新节点的下一个节点（即原来的 cur.next），继续处理。 样例演示 输入链表 {1,2,3,1}：  cur = 1，在 1 和 2 之间插入 0，链表变为 1 → 0 → 2 ...

小红的二叉树排序 [题目链接](https://www.nowcoder.com/practice/7f6dbe10fbe44d6ea8dd1414ed305620) 思路 题目要求：通过交换任意两个节点的权值，用最少的操作次数使二叉树的先序遍历为升序数组。 关键观察 先序遍历得到一个长度为  的序列 ，将其排序后得到目标序列 。问题等价于：给定排列 ，最少交换多少次使其变为 ？ 这是经典的最少交换次数排序问题。 置换环方法 将  到  的映射看作一个置换（permutation），其中  应该被放到  中对应的位置。这个置换可以分解为若干个不相交的环（cycle）。 对于一个长度为  的环，...

小红的好数 [题目链接](https://www.nowcoder.com/practice/2d051851420c40baa5a3b7cefcaa78d5) 思路 定义"好数"为：数位中奇数个数等于偶数个数的正整数。例如 1124 有两个奇数位（1, 1）和两个偶数位（2, 4），是好数。注意 0 是偶数。 要求统计区间  内好数的个数。由于  可达 ，不可能逐个枚举，需要使用数位 DP。 数位 DP 框架 利用前缀和思想，将问题转化为： $$ 其中  表示  中好数的个数。 对于 ，将  按十进制拆成数位数组，然后从高位到低位递归，维护以下状态：    状态 含义  ...

小红的 red 串 [题目链接](https://www.nowcoder.com/practice/b8e19a2c1d454a8897f2155d74304185) 思路 字符串仅由 'r'、'e'、'd' 三种字符组成，要求同时进行如下替换：  'r' → 'e' 'e' → 'd' 'd' → 'r'  由于变化是同时发生的，不能原地逐个替换后影响后续字符（实际上这里每个字符的替换互不影响，因为每个字符只看自身原始值）。直接遍历字符串，对每个字符按映射关系输出即可。 样例演示 输入 "rredd"：  r → e r → e e → d d → r d → r  输...

小红的数组构造 [题目链接](https://www.nowcoder.com/practice/7a08d1da90ab43daa2e70112781a3bd9) 思路 给定  个数，要求用这些数构造一个长度为  的数组，使得相邻两个数之和都是素数，问有多少种不同的构造方案。 本质上就是对数组求满足条件的全排列计数，同时需要处理重复元素。 算法：回溯 + 剪枝  先将数组排序，这样相同的数会聚在一起，方便跳过重复。 用回溯法逐个位置选数：   - 维护 used 数组标记哪些元素已被使用。  - 每次选择下一个数时，检查它与前一个数之和是否为素数，不满足则剪枝。  - 去重技巧：在同一层递归...

ACM中的AC题 [题目链接](https://www.nowcoder.com/practice/b56db882e9f94aed81b0a9d00da0ebff) 思路 两个玩家从同一起点出发，每步必须同时朝相反方向移动。当某人踩到传送门 @ 后离开，剩下的人可以自由移动。求两人都离开的最少步数。 关键观察：镜像约束压缩状态 如果两人都未离开，玩家 1 走 ，玩家 2 必须走 。设起点为 ，经过若干步后玩家 1 在 ，玩家 2 在 ，则始终满足： $$ 因此只要知道玩家 1 的位置，就能推出玩家 2 的位置。双人阶段的状态空间只有  而非 。 三阶段 BFS 将问题分成三个阶段，用统一的 ...

小欧的美丽矩阵 [题目链接](https://www.nowcoder.com/practice/c78fcff464f34fe5a6d5cfe5c43842d7) 思路 给定一个  的矩阵，判断能否通过若干次顺时针旋转使其变为"美丽矩阵"。 美丽矩阵的条件 矩阵  是美丽的，当且仅当：  每行递增：， 每列递增：，  即左上角最小，右下角最大，且行列均严格递增。 旋转变换 一次顺时针旋转将  变为 。 旋转 4 次回到原矩阵，所以最多只需要检查 4 种状态（旋转 0、1、2、3 次）。 做法 枚举 0~3 次旋转，每次检查当前矩阵是否满足美丽条件。如果任意一次满足则输出 ...

小欧吃苹果 [题目链接](https://www.nowcoder.com/practice/1e681787c63045cdbfc26b9b09002aeb) 思路 一棵  个结点的树，结点  上的人当前有  个苹果，想吃恰好  个。每次操作可以沿一条边传递 1 个苹果，求最小总传递次数。 关键观察：边上的流量 对于树上的任意一条边 ，删掉这条边后树被分成两个连通分量。设其中一个分量的结点集合为 ，则  中所有人的"盈余"之和为： $$ 如果 ，说明  中有多余的苹果需要向外运出；如果 ，说明需要从外面运入。无论哪种情况，经过边  的苹果传递次数恰好是 。 因此，最小总传...

小欧的最短路 [题目链接](https://www.nowcoder.com/practice/dcdac37856144dd58faf7e8c8450c8aa) 思路 小欧站在字符串的开头（位置 0），需要走到字符串的结尾（位置 ）。每一步有两种走法：  相邻移动：从位置  走到位置 ，代价为 （ASCII 码值之差的绝对值）。 同字母跳跃：从位置  跳到下一个与  相同的字母所在的位置 ，代价为 。  求从位置 0 到位置  的最小总代价。 动态规划 定义  为从位置 0 到达位置  的最小代价，初始 ，其余为正无穷。 对于每个位置 ，我们有两种转移：  相邻移动： 同字母跳跃：设  是位...