统计最大元素出现至少 K 次的子数组

题目

输入长度为 \(n\) 的数组 \(a\) 和整数 \(k\)，输出满足 \(\max(a)\) 至少出现 \(k\) 次的子数组的数目。

数据范围：\(1\leq n\leq 10^{5}\)，\(1\leq k\leq 10^{5}\)。

思路

首先计算出最大值，然后将所有最大值的下标放入列表 \(l\) 中，最后枚举右端点即可。假设列表的长度为 \(m\)，当前枚举到 \(i\)，当 \(i<m-1\) 时，区间 \([l[i],l[i+1]-1]\) 范围内的右端点都对应 \(l[i-k+1]+1\) 数量的左端点，将它们相乘加入答案。特别的，当 \(i=m-1\) 时，取区间 \([l[i],n-1]\)。PS：也可以滑动窗口，使窗口内只包含 \(k-1\) 个最大值，这样计算答案的空间复杂度为 \(O(1)\)。

统计好分割方案的数目

题目

输入长度为 \(n\) 的数组 \(a\)，输出将数组分割为若干不相交子数组的方案数。不相交表示子数组之间没有相同的元素，答案对 \(10^{9}+7\) 取余。

数据范围：\(1\leq n\leq 10^{5}\)。

思路

因为要求子数组之间没有相同元素，那么相同元素必定只会出现在一个子数组中，首先统计每个元素的最小和最大下标，这两个下标构成的区间是不可分割的。然后将所有不可分割的区间进行合并，最后剩余的区间数假设为 \(m\)，那么就会有 \(2^{m-1}\) 种分割方案（因为 \(m\) 个区间有 \(m-1\) 个分割位置，每个分割位置有分割或者不分割两种状态）。PS：① 可以边计数边做乘法，不使用快速幂；② 可以只统计最大下标，然后遍历数组时维护最大下标的最大值，如果当前下标等于该值，那么就可以做一次分割。（代码）

消除相邻近似相等字符

题目

输入长度为 \(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})\)。因为是求最短路，所以重边可以只保留最小的那条边。

需要添加的硬币的最小数量

题目

输入长度为 \(n\) 的数组 \(a\) 和整数 \(k\)，输出需要向数组插入多少个数，使得数组的子序列能够表示 \([1,k]\) 范围内的所有整数。

数据范围：\(1\leq n\leq 10^{5}\)，\(1\leq a_{i}\leq k\leq 10^{5}\)。

思路

从小到大遍历数组，假设当前能够表示的区间为 \([0,s]\)，此时遍历到数组中的数 \(a_{i}\)，我们可以表示区间 \([a_{i},s+a_{i}]\)。

• 如果 \(a_{i}\leq s+1\)，那么就可以合并两个区间，得到 \([0,s+a_{i}]\)，然后继续遍历 \(a_{i+1}\)。
• 否则，需要向数组插入数 \(s+1\) 来保证区间连续，得到 \([0,2s+1]\)，然后再次遍历 \(a_{i}\)。
• 不断重复上述过程直到能够表示区间 \([1,k]\)。

排序数组的时间复杂度为 \(O(n\log{n})\)，插入操作最多执行 \(O(\log{k})\) 次。

统计完全子字符串

题目

输入长度为 \(n\) 的由小写英文字母组成的字符串 \(s\) 和整数 \(k\)，输出满足以下两个条件的子字符串的个数。

• 每个字符恰好出现 \(k\) 次。
• 相邻字符在字母表中的距离小于等于 \(2\)。

数据范围：\(1\leq k\leq n\leq 10^{5}\)。

思路

距离大于 \(2\) 的相邻字符可以将字符串分割成若干子串，对于每个子串 \(t\) 考虑满足条件一的子串 \(t_{i}\) 个数即可。我们可以枚举 \(t_{i}\) 包含多少个不同的字符（设为 \(x\)），对于每个 \(x\) 使用滑动窗口可以得到 \(t\) 中满足条件一的长度为 \(kx\) 的子串个数。时间复杂度为 \(O(|\Sigma| n)\)，外层循环执行 \(O(|\Sigma|)\) 次，内层循环滑窗执行 \(O(n)\) 次，滑窗的同时使用计数数组统计有多少个字符恰好出现 \(k\) 次，判断的时间复杂度为 \(O(1)\)。

统计感冒序列的数目

题目

输入整数 \(n\) 和长度为 \(m\) 的按照升序排列的数组 \(a\)，数组 \(a\) 存储下标 \([0,n-1]\) 的子序列，输出所有不在数组 \(a\) 中的下标被选择的方案数，答案对 \(10^{9}+7\) 取余。下标 \(i\) 可以被选择，当且仅当下标 \(i-1\) 或者 \(i+1\) 被选择，数组 \(a\) 中的下标可以看作是被选择的。

数据范围：\(2\leq n\leq 10^{5}\)，\(1\leq m\leq n-1\)，\(0\leq a_{i}\leq n-1\)。

思路

数组 \(a\) 中的下标将 \([0,n-1]\) 划分为多个子数组，首先考虑每个子数组内部的方案数：最左和最右的子数组只存在一种选择方案，其他子数组存在 \(2^{x_{i}-1}\) 种选择方案，\(x_{i}\) 为该子数组的长度。然后考虑子数组之间的方案数，最初我们有 \(n-m\) 个位置可以放置下标，假设各个子数组的长度分别为 \(x_{0},x_{1},\dots,x_{k}\)，那么总共有 \(\prod_{i=0}^{k}{C(n-m-\sum_{j=0}^{i-1}{x_{j}},x_{i})}=\frac{(n-m)!}{\prod_{i=0}^{k}{x_{i}!}}\) 种放置方案。将两者相乘即可得到答案，计算过程需要使用逆元和快速幂。