P14636 功亏一篑

· · 题解

虽然我们的 NOIP 题目很难，有 NOI 难度。但是我们比 NOI 少半个小时还多一道签到题，还没有 selfeval 要自己写对拍呢！

建议评蓝，虽然场上被创飞了，但是被创飞的部分只有黄难度。

首先将 a 从大到小排序。

发现直接计算十分困难，于是正难则反，考虑什么时候无法取到总价值最大值。

设我们已经确定每颗糖果的价格 w_i，考虑如何取到总价值最大值。我们将 w_i=1 和 w_i=2 分离出来，一块钱的糖原价格为 x_j，两块钱的糖原价格为 y_j，显然我们会取两个序列的前缀。

设一块钱的糖取了 A 颗，两块钱的糖取了 B 颗。那么根据性价比贪心取不到最大值当且仅当 x_{A+1}> \frac{y_B}{2} 且 x_{A+1}+x_{A+2}<y_B。

::::info[为什么？] 这部分的实际意义就是，在只剩最后两块钱的时候，由于 x_{A+1} 的性价比比 y_B 高，因此先花一块钱购买 x_{A+1} 导致无法购买 y_B，只能购买 x_{A+1}，又因为 x_{A+1}+x_{A+2}<y_B 所以没能取到总价值最大值。 ::::

于是直接枚举 y_B 和 x_{A+1} 在原序列中的位置 i 和 j，发现这两个位置确定后 x_{A+2} 可能的位置 k 是一段后缀 k\sim n。

此时我们发现 a_1\sim a_i 在正解中都会被取到，a_{i+1}\sim a_{j-1} 中定价为 1 的糖在正解中也都会被取到（从分离后取前缀就可以看出），这样的取法构成了正解。

而我们的目标是在 a_1\sim a_{j-1} 按如上方法取的时候，将 m 块钱都花完，这就是一个组合数问题，此时我们已经有了 O(n^3) 解法，拼上后面所有 a 全相等和 \frac{a_1}{2}>a_n 的部分就有了 64 分。

::::info[fun fact] 笔者只花了 10min 就想到了这一步。 ::::

接下来我们发现，对于 1\le k<i，w_k=1 有 1 的贡献，w_k=2 有 2 的贡献。对于 i<k<j，w_k=1 有 1 的贡献，w_k=2 有 0 的贡献。w_i=2 固定有 2 的贡献。我们将 1\le k<i 中每个元素固定的 1 贡献提取出来，就变成了：

然后这就是一个组合数问题（对的就是在这里被创飞的）后面 x_{A+2} 所处的后缀可以任取，全定价 2 也是合法的（这样最后一块钱就花不掉了）对于 j+1 到 k-1 这一段必须全定价 2，否则最后一块钱会提前花掉。

因此对于一对满足 a_j<a_i<2a_j 的 i,j，其对答案的贡献是 C_{j-1}^{m-i-1}\times 2^{n-k+1}，其中 k 是最小的正整数满足 a_j+a_k<a_i 且 a_k<a_j，枚举 i,j 直接计算总和即可。