第 119 场力扣夜喵双周赛

消除相邻近似相等字符

题目

输入长度为 \(n\) 的字符串 \(s\)，输出所需的最少操作次数，使得字符串 \(s\) 中的相邻字符在字母表中的距离大于 \(1\)。每次操作可以将字符串 \(s\) 中的某个字符修改为任意字符。

数据范围：\(1\leq n\leq 100\)。

思路

思路一：距离大于 \(1\) 的相邻字符可以将字符串 \(s\) 分割为若干子串，每个子串所需的最少操作次数为 \(\lfloor\frac{l}{2}\rfloor\)，其中 \(l\) 表示子串的长度。

思路二：如果相邻字符距离小于等于 \(1\)，那么贪心的修改右边的字符即可。

两种思路原理是一样的，只是实现时略有不同。

关闭分部的可行集合数目

题目

输入整数 \(n\) 表示有 \(n\) 个节点，长度为 \(m\) 表示无向边的数组 \(e\)（包含重边），以及整数 \(d\)。输出删除节点的方案数，使得剩余节点两两之间的最短路不超过 \(d\)。

数据范围：\(1\leq n\leq 10\)，\(0\leq m\leq 1000\)。其他数据不会影响时间复杂度，所以不列出。

思路

题目要求满足条件的方案数，首先想到枚举所有方案，总共有 \(2^{n}\) 个方案，然后对每个方案求删除节点后的多源最短路（Floyd 算法），如果剩余节点两两之间的最短路都不超过 \(d\)，那么答案就加一，总时间复杂度为 \(O(m+2^{n}n^{3})\)。因为是求最短路，所以重边可以只保留最小的那条边。