diverta 2019 Programming Contest 2 题解
AB 就不写了。
C - Successive Subtraction
题意
有 \(N\) 个数，执行 \(N-1\) 次操作，每次选择两个数 \(x,y\)，删去这两个数，替换成 \(x-y\)。求最后结果的最大值并构造方案。
\(N\le 10^5\)
题解
最后一定是给每个数一个正负号后加起来的结果。
显然，全部填正号或全部填负号一定不可行。而同时有正负时，记其中一个填正号的数是 \(a\)，填负号的数是 \(b\)，那么我们可以用 \(b\) 减去其他填正号的数，再用 \(a\) 减去该数，最后再减去其他填负号的数。
所以我们只要将所有正数填上正号，所有负数填上负号即可，需要注意全正和全负的情况。
D - Squirrel Merchant
题意
一开始有 \(N\) 个球，有两个商店 A、B。在商店 \(X\) 交易时，可以按任意顺序执行任意次以下交换（交换是双向的）：
- 交换 \(g_X\) 个球与 \(1\) 单位的金。
- 交换 \(s_X\) 个球与 \(1\) 单位的银。
- 交换 \(b_X\) 个球与 \(1\) 单位的铜。
你可以按顺序在商店 A，商店 B，商店 A 进行交易。
求最后最多有多少球。
\(N,g_A,s_A,b_A,g_B,s_B,b_B\le 5000\)
题解
我们可以把问题看成先用 \(N\) 个球依次在 A 和 B 交易，全部换成球，得到 \(M\) 个球，然后再用这 \(M\) 个球依次在 B 和 A 交易，再全部换成球，就是答案。
这两步的问题是一样且独立的，而每一步的问题相当于一个完全背包问题。直接 DP 即可。
时间复杂度 \(O(N^2)\)。
E - Balanced Piles
题意
有 \(N\) 个初始为 \(0\) 的整数，每次可以执行以下操作：
- 记 \(N\) 个数中的最小值为 \(m\)，最大值为 \(M\)。选择任意一个等于 \(m\) 的数，加上一个正整数，使得该数在 \([M,M+D]\) 中。
你的目标是使所有数都变成 \(H\)。求操作方案数，对 \(10^9+7\) 取模。
\(N,D,H\le 10^6\)
题解
令 \(f_{i,j}\) 表示当前最大值为 \(i\)，有 \(j\) 个时的操作方案数。
注意到此时转移与最小值有关，貌似并不能转移。
但是考虑到这 \(j\) 个最大值在接下来的某段操作中会变成最小值，而在这一段操作中，因为我们确定了每一次操作后的最大值，所以这 \(j\) 个最大值的贡献是 \(j!\)。
于是我们有 \[ f_{i,j}= \begin{cases} \sum\limits_{k=1}^d\sum\limits_{l=1}^{n} f_{i-k,l} & \text{ if }j=1\\ f_{i,j-1}\cdot j & \text{ if }j>1 \end{cases} \]
也就是说我们有 \(f_{i,j}=f_{i,1}\cdot j!,f_{i,1}=\sum\limits_{k=1}^{d}f_{i-k,1}\sum\limits_{l=1}^{n}l!\)。
所以只记录 \(f_{i,1}\)，用前缀和优化转移即可。
注意 \(i=0\) 时，只有 \(f_{i,n}=n!\)，其他位置都是 \(0\)，所以最后答案需要乘上 \(\frac{n!}{\sum\limits_{i=1}^{n}i!}\) 去掉其他位置的贡献。
F - Diverta City
题意
给一个 \(n\) 个点的无向完全图的每条边确定一个权值，使得所有 \(\frac{n!}{2}\) 条本质不同的哈密顿路权值不同。
\(n\le 10\)
题解
构造一个序列 \(f=\{1, 2, 4, 7, 12, 20, 29, 38, 52\}\)，这个序列满足所有元素以及所有元素两两的和都互不相等。
考虑每次加入一个点 \(i\)，对于所有 \(j < i\)，将 \((i,j)\) 这条边的边权置为 \((M+1)f_j\)，其中 \(M\) 表示前 \(i-1\) 个点的所有哈密顿路权值的最大值。
这样构造显然是正确的。证明可以考虑在任意两条哈密顿路中的任意位置插入 \(i\)，因为乘了 \((M+1)\)，原来哈密顿路的权值以及减去的边的权值都不需要考虑，而只需要考虑加入的两条边。因为乘了 \(f_i\)，这些边具有了 \(f\) 的性质，即所有元素以及所有元素两两的和都互不相等，所以这些新的哈密顿路权值一定都互不相等。
