第 375 场力扣周赛

统计最大元素出现至少 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:① 可以边计数边做乘法,不使用快速幂;② 可以只统计最大下标,然后遍历数组时维护最大下标的最大值,如果当前下标等于该值,那么就可以做一次分割。(代码

第 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})\)。因为是求最短路,所以重边可以只保留最小的那条边。

第 374 场力扣周赛

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

题目

输入长度为 \(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}!}}\) 种放置方案。将两者相乘即可得到答案,计算过程需要使用逆元和快速幂。