2020-2021:teams:intrepidsword:2020-hdu-multi-3

差别

这里会显示出您选择的修订版和当前版本之间的差别。

到此差别页面的链接

--- 2020-2021:teams:intrepidsword:2020-hdu-multi-3 [2021/04/09 15:29]
toxel 创建
+++ 2020-2021:teams:intrepidsword:2020-hdu-multi-3 [2021/08/27 17:46] (当前版本)
toxel
@@ 行 1: / 行 1: @@
+====== Contest Info ======
+date: 2021.01.23 ??:??-??:??
+[[https://vjudge.net/contest/419242|practice link]]
+====== Solutions ======
+===== B. Lady Layton and Stone Game =====
+**题目大意**：有若干堆石子，每次可以取若干堆合并在一起，代价为合并后堆的大小。但是，堆数必须在 $L$ 和 $R$ 之间。求最小代价。
+**题解**：显然每次合并时都会取最小的那几堆。假设两次相邻的合并分别取了 $x$ 堆和 $y$ 堆，若 $x>y$ 或 $x\le y$ 但是 $x-1$ 和 $y+1$ 合法，那么可以证明交换 $x,y$ 或者 $x-1,y+1$ 这样合并一定更优：
+  * 若 $\sum_{i=1}^{x}a_{i}\le a_{x+y}$，那么前者代价为 $\sum_{i=1}^{x}a_{i}+\sum_{i=1}^{x+y-1}a_{i}$，后者代价为 $\sum_{i=1}^{x-1}a_{i}+\sum_{i=1}^{x+y-1}a_{i}$。此后两个序列变得相同。因此 $x-1,y+1$ 更优。
+  * 否则，若 $\sum_{i=1}^{x-1}a_{i}\le a_{x+y}$，那么前者合并再次的代价为 $\sum_{i=1}^{x}a_{i}+\sum_{i=x+1}^{x+y}a_{i}$，后者合并两次代价为 $\sum_{i=1}^{x-1}a_{i}+\sum_{i=1}^{x+y-1}a_{i}$。后者代价更小。而合并完成之后，前者得到了 $\sum_{i=1}^{x}a_{i}$ 与 $\sum_{i=x+1}^{x+y}a_{i}$，后者得到了 $\sum_{i=1}^{x+y-1}a_{i}$ 与 $a_{x+y}$。由于 $a_{x+y}<\sum_{i=1}^{x}a_{i}$，且 $a_{x+y}\le\sum_{i=x+1}^{x+y}a_{i}$，因此后者的序列前缀和总是小于前者。可以证明在这一前提下，在任意的合并树下，后者的代价总比前者要优。因此 $x-1,y+1$ 更优。
+  * 否则，即 $\sum_{i=1}^{x-1}a_{i}>a_{x+y}$，那么前者合并再次的代价为 $\sum_{i=1}^{x}a_{i}+\sum_{i=x+1}^{x+y}a_{i}$，后者合并两次代价为 $\sum_{i=1}^{x-1}a_{i}+\sum_{i=x}^{x+y}a_{i}$。两者相同。而合并完成之后，前者得到了 $\sum_{i=1}^{x}a_{i}$ 与 $\sum_{i=x+1}^{x+y}a_{i}$，后者得到了 $\sum_{i=1}^{x-1}a_{i}$ 与 $\sum_{i=x}^{x+y}a_{i}$。若 $x\le y$，显然 $\sum_{i=1}^{x-1}a_{i}\le\sum_{i=1}^{x}a_{i}$ 且 $\sum_{i=1}^{x-1}a_{i}\le\sum_{i=x+1}^{x+y}a_{i}$，与上一种情况相同。而若 $x>y$，考虑交换 $x,y$，并且不妨钦定第二种情况先合并成 $\sum_{i=1}^{y}a_{i}$ 与 $\sum_{i=y+1}^{x+y}a_{i}$，容易证明这样还是更优。
+因此合并的过程一定可以表示成 $L,L,L,\ldots,L,t,R,R,R,\ldots,R$。考虑两个序列 $A$ 和 $B$，其中 $B$ 的 $R$ 更多/$L$ 更少。显然可以从 $A$ 通过一些 $-1/+1$ 操作得到 $B$，$B$ 更优。
+确定序列后，可以用一个队列直接暴力模拟，老题了。
 ===== K. Game on a Circle =====

2020-2021/teams/intrepidsword/2020-hdu-multi-3.1617953343.txt.gz · 最后更改: 2021/04/09 15:29 由 toxel