CF1992场题解

Only Pluses

算法：数学。

题意简述：有三个数，每次选择一个数 \(x\)，使得 \(x\) 增加一，至多操作 \(5\) 次，最后求出这三个数的乘积最大值。

简单题，一眼秒了。考虑把这 \(3\) 个数从小到大排序，显然加最小的数比加其他的数更优。

简单证一下：设排序后的三个数为 \(a,b,c\)，有 \(b\times c\ge a\times b\) 且 \(b\times c\ge a\times c\)，而 \(b\times c\) 就是把最小数 \(a\) 加一增加的贡献，故改变最小数一定更优。

Angry Monk

算法：数学。

题意简述：有两种操作，把一个大于 \(1\) 的数 \(x\) 拆成 \(x-1\) 和 \(1\)；或者把 \(1\) 和另一个数 \(x\) 合并成 \(x+1\)，问把原序列合成一个数最少需要几次操作。

简单题，同样一眼秒了。考虑最大的数不要拆，把剩下的数都拆成 \(a_i\) 个 \(1\)，最后把每个 \(1\) 和最大数 \(a_1\) 合并。

这里把一个数 \(x\) 拆开需要 \(x-1\) 次操作，合并需要 \(x\) 次操作，总共需要 \(x\times 2-1\) 次操作，所以我们应该按这个数排序，最大操作次数的不动。事实上，就是最大数不动。

Gorilla and Permutation

算法：贪心，构造。

题意简述：定义两个数组 \(f_i\) 和 \(g_i\)，构造出的数组为 \(a_i\)，给定 \(m,k\)。\(f_i\) 的转移：\(f_i=f_{i-1}+(a_i \ge k?a_i:0)\)；\(g_i\) 的转移：\(g_i=g_{i-1}+(a_i \le m?a_i:0)\)，最后求序列 \(a\) 使得 \(\displaystyle \sum_{i=1}^{n}(f_i-g_i)\) 取到最大值。