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]\) 求和得到答案。单调栈这个规律有点难想，具体看视频吧。

使数组成为等数数组的最小代价

题目

输入长度为 \(n\) 的整数数组 \(a\)，输出执行任意次操作后使得数组中的数全部相等并且是回文数的最小代价（要求该回文数小于 \(10^{9}\)）。每次操作可以将数组中的某个数（假设为 \(a_{i}\)）修改为任意正整数（假设为 \(x\)），对应的代价为 \(|a_{i}-x|\)。

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

思路

如果没有限制是回文数，那么将数组排序之后按如下方式修改，代价是最小的（假设有序数组中的元素为 \(a_{0},a_{1},\dots,a_{n-1}\)）：

• 当 \(n\) 为奇数时，将所有数修改为中位数 \(a_{\lfloor\frac{n}{2}\rfloor}\)。
• 当 \(n\) 为偶数时，将所有数修改为区间 \([a_{\lfloor\frac{n-1}{2}\rfloor},a_{\lfloor\frac{n}{2}\rfloor}]\) 内的某个数。

首先使用反证法证明，最小代价可以通过将所有数修改为数组中的某个数取到。

• 假设将所有数修改为 \(x\)，\(x\) 在区间 \((a_{i},a_{i+1})\) 范围内，其中 \(a_{i}\) 和 \(a_{i+1}\) 表示数组中相邻的两个数。此时 \(x\) 左边有 \(i+1\) 个元素，右边有 \(n-i\) 个元素。将 \(x\) 修改为 \(a_{i+1}\) 会使代价增加 \((i+1)\times (a_{i+1}-x)\)，并且使代价减少 \((n-i)\times(a_{i+1}-x)\)。将 \(x\) 修改为 \(a_{i}\) 会使代价减少 \((i+1)\times (x-a_{i})\)，并且使代价增加 \((n-i)\times(x-a_{i})\)。
• 当 \(i+1<n-i\) 时，将 \(x\) 修改为 \(a_{i+1}\) 会使代价减少；当 \(i+1>n-i\) 时，将 \(x\) 修改为 \(a_{i}\) 会使代价减少；当 \(i+1=n-i\) 时，将 \(x\) 修改为 \(a_{i}\) 或者 \(a_{i+1}\) 代价不变。
• 特别的，\(x\) 在区间 \([1,a_{0})\) 或者 \((a_{n-1},+\infty]\) 范围内时，同理。

然后再使用反证法证明上述结论：

• 假设将数组中的数都修改为 \(a_{i}\) 时，代价最小，\(a_{i}\) 不满足上述条件。
• 当 \(n\) 为奇数时，由于 \(a_{i}\) 不是中位数：
  • 当 \(i<\lfloor\frac{n}{2}\rfloor\) 时，有 \(i+1<n-1-i\)，此时 \(i\) 每向中位数移动一位，代价都会减少 \((n-1-i)-(i+1)>0\)。
  • 反之亦然。
• 当 \(n\) 为偶数时，同理。

综上，得出按照上述方式修改代价最少，即 \(x\) 越靠近中位数代价越小。所以，如果需要将所有数修改为某个回文数，那么该回文数一定是最靠近中位数的回文数。PS：还是灵神的证明更简单。

该题有两种方法可以找到距离 \(x\) 的最近回文数：

• 方法一：将 \(x\) 的前半部分作为回文根，对称之后得到回文数 \(y\)。如果 \(y<x\)，则将回文根加一再做对称得到回文数 \(z\)，然后取 \(y\) 和 \(z\) 中距离最近者；如果 \(y>x\)，则将回文根减一再做对称得到回文数 \(z\)，然后取 \(y\) 和 \(z\) 中距离最近者；否则，\(x\) 本身就是回文数。注意，排除大于等于 \(10^{9}\) 的回文数，以及做加减法时可能会遇到回文根为 \(100\dots0\) 或 \(99\dots9\) 的特殊情况，此时做对称会得到错误答案，我们应该直接根据长度构造回文数。（这个代码还挺好看，把所有情况都直接循环枚举，就可以不用写那么多判断语句）
• 方法二：枚举出 \([1,10^{9}]\) 范围内的所有回文数，然后二分找到距离 \(x\) 最近的回文数。

执行操作使频率分数最大

题目

输入长度为 \(n\) 的整数数组 \(a\) 和一个整数 \(k\)，输出经过至多 \(k\) 次操作之后，数组中众数的最大频率。每次操作可以选择数组中的某个数 \(a_{i}\)，将其增加或者减少 \(1\)。

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

思路

排序 + 前缀和 + 滑动窗口。要使众数尽可能多，可以首先对数组排序，假设最终众数有 \(x\) 个，那么这 \(x\) 个数一定是在某个子数组中。使用滑动窗口，将尽可能多的数包含在窗口内，同时满足操作次数小于等于 \(k\)，如果大于 \(k\) 则将左端点右移。类似上一题，将窗口内的所有数都修改为窗口的中位数，所需的操作次数最少。窗口的操作次数可以使用前缀和 \(O(1)\) 的计算出来，假设窗口的左右端点的下标分别为 \(i\) 和 \(j\)，中位数的下标为 \(k\)，则窗口的操作次数为：\((a_{k}\times (k-i)-(s[k]-s[i]))+((s[j+1]-s[k+1])-a_{k}\times (j-k))\)。