统计移除递增子数组的数目 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\) 依次选择数组中的下标，该游戏方式是最优的。

Swap and Delete

题目

输入长度为 \(n\) 的二进制字符串，输出执行操作需要的最小成本，使得对于操作之后得到的字符串 \(t\) 的每个字符 \(t_{i}\)，都有 \(t_{i}\neq s_{i}\)，其中 \(1\leq i\leq |t|\)。有两种操作：

• 从字符串 \(s\) 中删除一个字符，操作的成本为 \(1\)。
• 交换字符串 \(s\) 中的两个字符，操作的成本为 \(0\)。

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

思路

由于只有删除操作会导致成本增加，所以我们只需要让字符串 \(t\) 尽可能长就好。首先对字符串 \(s\) 中的 \(0\) 和 \(1\) 计数，然后贪心的构造字符串 \(t\)，如果 \(s_{i}=0\)，则 \(t_{i}=1\)，反之亦然，直到不能增加长度为止。最后最小成本就是 \(n-|t|\)。

Game with Multiset

题目

输入一个整数 \(m\) 表示查询的次数，以及 \(m\) 行查询，每行包含两个整数 \(t_{i}\) 和 \(v_{i}\)。初始时你有一个空的多重集合（multiset）：

• 如果 \(t_{i}=1\)，将元素 \(2^{v}\) 加入集合。（\(0\leq v_{i}\leq 29\)）
• 如果 \(t_{i}=2\)，询问 \(v_{i}\) 是否可以表示为当前集合的某个子集之和，并输出 YES 或 NO。（\(0\leq v_{i}\leq 10^{9}\)）

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

思路

• 方法一：使用数组对 \(t_{i}=1\) 的 \(v_{i}\) 计数，对于每个询问，从低到高遍历 \(v_{i}\) 的二进制 \(1\)。假设当前遍历到 \(2^{k}\)，如果集合中存在 \(2^{k}\) 则当前位可以被表示（假设集合中有 \(c_{k}\) 个 \(2^{k}\)），并且集合中剩余的 \(2^{k}\) 可以合并为 \(\frac{c_{k}-1}{2}\) 个 \(2^{k+1}\)，然后遍历下一位，这样最终可以判断 \(v_{i}\) 是否能被集合表示。
• 方法二：使用数组对 \(t_{i}=1\) 的 \(v_{i}\) 计数，对于每个询问，从高到低遍历 \(v_{i}\) 的二进制 \(1\)。假设当前遍历到 \(2^{k}\)，则执行 \(v_{i}=v_{i}-(\min{(v_{i}>>k,c_{k})}<<k)\) 操作（假设集合中有 \(c_{k}\) 个 \(2^{k}\)），表示将集合中的元素尽可能填补到 \(v_{i}\) 中，最终 \(v_{i}\) 还需要多少值，如果最终 \(v_{i}=0\) 则它可以被集合表示。

Array Collapse

题目

输入长度为 \(n\) 的数组 \(p\)，其中的元素互不相同。输出执行任意次操作能够得到的不同数组个数，结果对 \(998244353\) 取余。每次操作可以选择 \(p\) 的一个子数组（假设为 \([i,j]\)），将子数组中除最小值之外的所有数删除。

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

思路

• 方法一：使用分治 + 线段树的时间复杂度为 \(O(n\log{n})\) 的思路，比赛时大概就是这个思路，不过想岔了一点。对于区间 \([i,j]\)，使用线段树找到区间最小值的下标，然后左右分治求不同数组的个数，最后将两者相乘。这个方法还有一些特殊情况需要维护，具体看代码。
• 方法二：参考灵神视频单调栈优化 DP，将 \(f[i]\) 定义为以 \(p[i]\) 结尾的子序列个数，然后利用动态规划转移，最后将所有 \(f[i]\) 求和得到答案。单调栈这个规律有点难想，具体看视频吧。