AtCoder Regular Contest 104 题解

A - Plus Minus

题面

直接输出 \(\frac{x+y}{2}\) 和 \(\frac{x-y}{2}\)。

B - DNA Sequence

题面

前缀和后暴力枚举区间。

C - Fair Elevator

题面

首先你要读懂题

设 \(dp_i\) 表示前 \(i\) 层楼是否满足条件。

考虑转移：枚举上一个区间包含的人数 \(k\)，如果 \(i-2k+1\sim i\) 可以满足题目中给的条件，那么 dp[i] |= dp[i - 2 * k]。

如何判断满足条件？枚举楼层后分类讨论一下即可。

注意无解的判断。

代码

D - Multiset Mean

题面

一道神题。

首先，暴力 DP 是 \(\mathcal O(n^4k^2)\) 的，显然过不去。

考虑转化题目条件，一个集合 \(S\) 中所有数平均数为 \(x\)， 即 \(\frac{\sum a_i}{|S|}=x\)，等价于 \(\sum (a_i-x) = 0\)。

那么题目就转化为：\(1\sim n\) 中每个数有 \(k\) 个，从中选出若干个数使得 \(\sum (a_i-x) = 0\)。

然后发现每个数可以变成 \(-(x-1),-(x-2),\dots,-2,-1,0,1,2,\dots,n-x\)。

先不考虑 \(0\) 的存在，原问题即为从这些数中选出若干个，使得正数之和 \(=\) 负数之和。

考虑 DP，设 \(dp_{i,j}\) 表示仅考虑 \(1\sim i\) 中的数，每个数有 \(k\) 个，选出若干个数和为 \(j\) 的方案数。

显然有 \(dp_{i,j} = \sum\limits_{l=0}^k dp_{i-1,j-l\times i}\)。

这样做依然会 TLE，考虑进一步优化。

首先不考虑限制，我们让 \(dp_{i,j} = dp_{i-1,j} + dp_{i-1,j-i}\)。

这样做时，如果 \(j < (k+1)\times i\)，\(dp_{i,j}\) 的值不会出错；但当 \(j\ge (k+1)\times i\) 时，我们求出的 DP 值会偏大，它多加了 \(\sum\limits_{l=k+1} dp_{i-1,j-l\times i}\)。

发现后面那一坨式子就是 \(dp_{i-1,j-(k+1)\times i}\)，直接倒序循环减去即可。

最后答案还要 \(\times k\)，因为 \(x\) 选或不选都不会对答案有影响；还要记得 \(-1\)，因为我们统计了集合为空集的情况。

代码