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

题目

输入整数 \(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}\)。

Three Activities

题目

输入长度为 \(n\) 的数组 \(a,b,c\)，输出 \(a_{i}+b_{j}+c_{k}\) 的最大值，要求 \(i,j,k\) 互不相同。

数据范围：\(3\leq n\leq 10^{5}\)，\(1\leq a_{i},b_{i},c_{i}\leq 10^{8}\)。

思路

• 方法一：可以发现答案只和数组 \(a,b,c\) 中最大的三个元素有关，首先建立三个数组对应的下标数组，对其降序排序。然后使用三重循环暴力枚举前三个元素的组合，要求 \(i,j,k\) 互不相同，最后取组合的最大值作为答案。
• 方法二：状压 DP，定义 \(dp[i][j]\) 表示 \([0,i]\) 范围内从 \(j\)（\(0\leq j\leq 7\)）所对应数组中各取一个元素，能够得到的元素和的最大值。例如，当 \(j=3\) 时，表示从 \(a\) 和 \(b\) 中取元素。可以使用倒序枚举的方式优化空间。

Game with Marbles (Hard Version)

题目

输入长度为 \(n\) 的数组 \(a,b\)，输出游戏结束时的得分 \(s\)。游戏内容为：玩家 \(A,B\) 每次可以选一个下标 \(i\)，如果当前轮到玩家 \(A\)，则进行 \(s=s+(a_{i}-1)\) 操作，否则进行 \(s=s-(b_{i}-1)\) 操作，不能重复选择同一个下标。游戏从玩家 \(A\) 开始，并且假设 \(A,B\) 双方都以最优的方式进行游戏。

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

思路

假设当前轮到玩家 \(A\)，选择下标 \(i\)，则答案会增加 \(a_{i}-1\)，并且 \(b_{i}\) 将会无效化。相当于每次选择对答案的贡献为 \(a_{i}+b_{i}\)，建立一个下标数组，按照该方式对数组降序排序。然后让玩家 \(A,B\) 依次选择数组中的下标，该游戏方式是最优的。