找出出现至少三次的最长特殊子字符串 II

题目

输入长度为 \(n\) 的由小写字母组成的字符串 \(s\)。如果一个字符串仅由单一字符组成，则它被称为特殊字符串。输出在 \(s\) 中出现至少三次的最长特殊非空子字符串的长度，如果不存在则输出 \(-1\)。

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

思路

可以直接想到二分答案，时间复杂度为 \(O(n\log{n})\)。不过该题有 \(O(n)\) 的做法，其实就是分类讨论。首先遍历一边数组，将数组按照字母分段，把对应的长度存到桶中。假设字符串 \(s\) 的最长特殊子字符串的长度为 \(m\)，则答案必定在 \([m-2,m]\) 范围内，枚举答案然后判断是否满足条件即可。当然还可以像灵神一样讨论得更细，但是不好理解。

回文串重新排列查询

题目

输入长度为偶数 \(n\) 的字符串 \(s\)，以及长度为 \(m\) 的二维数组 \(q\)，其中 \(q_{i}=[a_{i},b_{i},c_{i},d_{i}]\)。对于每个查询 \(i\)，可以将区间 \([a_{i},b_{i}]\) 和 \([c_{i},d_{i}]\) 中的字符重新排列，输出是否能让字符串 \(s\) 变为回文串。每个查询是独立的。

数据范围：\(2\leq n\leq 10^{5}\)，\(1\leq m\leq 10^{5}\)，\(0\leq a_{i}\leq b_{i}<\frac{n}{2}\)，\(\frac{n}{2}\leq c_{i}\leq d_{i}<n\)。

思路

比赛时基本的思路是有的，就是没有实现出来。首先可以将后半段字符串反转，将原串当成两个字符串，这就将问题转化为判断操作之后两个字符串能否相等，从而简化实现。然后就是预处理前缀的字符计数（类似前缀和），最后对每个查询分类讨论，两个区间是相离、相交还是包含关系。个人觉得稍微复杂点的就是相交关系该如何判断，具体可以看题解区。

移除栅栏得到的正方形田地的最大面积

题目

输入整数 \(m\) 和 \(n\)，表示宽为 \(m\) 长为 \(n\) 的矩形，左上角为 \((1,1)\)，右下角为 \((m,n)\)。输入长度分别为 \(p\) 和 \(q\) 的数组 \(a\) 和 \(b\)，数组 \(a\) 中的数对矩形水平分割，数组 \(b\) 中的数对矩形垂直分割。输出从数组 \(a\) 和 \(b\) 中移除任意个数，所能够形成的最大正方形面积，结果对 \(10^{9}+7\) 取余。

数据范围：\(3\leq m,n\leq 10^{9}\)，\(1\leq p,q\leq 600\)，\(1<a_{i}<m\)，\(1<b_{i}<n\)。

思路

首先考虑对于宽来说，能够表示的长度是多少。显然，可以通过二重循环枚举出所有可能的长度。将宽能够表示的长度放入哈希表，然后同样使用二重循环枚举长能够表示的长度（假设当前枚举到长度 \(x\)），如果该长度在哈希表中，则说明可以形成长度为 \(x\) 的正方形。最后输出最大值即可。

转换字符串的最小成本 II

题目

输入长度为 \(n\) 的字符串 \(source\) 和 \(target\)，以及长度为 \(m\) 的字符串数组 \(original\)、\(changed\) 和 \(cost\)。其中 \(cost[i]\) 表示将字符串 \(original[i]\) 替换为 \(changed[i]\) 的成本。输出将 \(source\) 转换为 \(target\) 所需的最小成本，如果无法转换则输出 \(-1\)。任意两个替换操作所替换的区间要么相同，要么不相交。

数据范围：\(1\leq n\leq 1000\)，\(1\leq m\leq 100\)，\(1\leq \operatorname{len}(original[i])=\operatorname{len}(changed[i])\leq n\)。

思路

首先使用哈希表将 \(original\) 和 \(changed\) 数组中的字符串映射为数字，每个数字都作为图中的一个顶点。对于每个下标 \(i\)，建立一条从顶点 \(original[i]\) 到顶点 \(changed[i]\) 的边，然后使用 Floyd 算法求出多源最短路径。最后使用动态规划，定义 \(dp[i+1]\) 为对 \(source\) 的前缀 \([0,i]\) 做替换使其和 \(target\) 的前缀 \([0,i]\) 相等，所需的最小代价。注意，外层循环枚举前缀的右端点 \(i\)，内层循环枚举 \(original\) 数组，总时间复杂度为 \(O(m^{3}+n^{2}m)\)。使用字典树会更快，参考灵神题解。

统计移除递增子数组的数目 II

题目

输入长度为 \(n\) 的数组 \(a\)，输出子数组的数目，使得移除该子数组之后剩余的数是严格递增的，空数组也被认为是递增的。

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

思路

首先找到第一个满足 \(a_{i}>=a_{i+1}\) 的下标 \(i\)。如果 \(i=n-1\)，则表示可以移除任意子数组，直接返回 \(\frac{n(n-1)}{2}\)。否则，我们需要移除一个子数组使得剩余前缀和后缀分别递增，并且前缀的右端点小于后缀的左端点。可以使用双指针，一个指针枚举后缀的左端点 \(j\)，另一个指针从 \(i\) 开始左移，寻找满足条件的前缀的右端点 \(i\)，然后将 \(i+2\) 添加到答案中，重复此过程直到 \(a_{j}>=a_{j+1}\)。