Codeforces Round 916 (Div. 3)

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\) 依次选择数组中的下标，该游戏方式是最优的。