NOIP 2025 游记

Day 1 (11.29)

A 秒了。

阅读 B 题题面（包含样例解释）。

思考过程

认为需要分析在何种定价方案下，贪心策略是最优的，何种情况下不是。[^1]

考虑如何解决固定定价方案时，求最大原价的选择方案的问题，相当于两种 \(w\) 各自排序后每次决策从哪堆中买。

当 \(w_i = 2\) 的第一个待选物品的性价比大于等于 \(w_i = 1\) 的第一个待选物品的性价比时，选 \(w_i = 2\) 的物品一定是不劣的，即贪心策略在此时是正确的。

所以贪心策略出的错误只能是“在应当买 \(w_i = 2\) 的物品时被第一个 \(w_i = 1\) 的物品的高性价比诱骗了，被迫一起买下低性价比的第二个 \(w_i = 1\) 的物品，或发现后面没有第二个 \(w_i = 1\) 的物品但自己还有一块钱没花出去。”

贪心策略在这里显然会被骗至多一次，因为后面的 \(w_i = 1\) 的物品的性价比会比第二个更低，此时没有高性价比的诱饵了。

接下来思考枚举几个关键位置后组合计数。考虑了几个位置，并思考如何确保“贪心策略一定会选成这样”，然后一直无法保证贪心策略会选最后一个 \(w_i = 2\) 的而不是去选下一个 \(w_i = 1\) 的。

9:10，感觉组合计数没有前途，去想怎么做 DP 了。

定下策略“9:30 没进展就打暴力跑路。”在 9:30 左右看了 C、D 题后感觉非常困难回来继续思考 B 题，将时限延至 10:00。

约 9:40，回看组合计数思路。

思考过程

发现“贪心策略选择钦定的最后一个 \(w_i = 2\) 的物品”是必然成立的。于是在此基础上继续考虑。

想到了可以枚举第一个未选的 \(w_i = 2\) 的物品，记为 \(x\)，和倒数第二个选择的 \(w_i = 1\) 的物品，记为 \(y\)。将最后一个选择的 \(w_i = 1\) 的物品记为 \(z\)，则需要满足的条件如下。

• \(a_y + a_z < a_x\)
• \(2a_y > a_x\)

考虑其他物品会不会被购买。分段考虑，\(i< x\) 的 \(i\) 无论其 \(w\) 如何一定会被购买；\(x < i < y\) 的 \(i\) 仅当 \(w_i = 1\) 时会被购买；\(y < i < z\) 的 \(i\) 必须满足 \(w_i = 2\)（否则 \(i\) 会被购买，不满足“\(y\) 是倒数第二个被选择的 \(w_i = 1\) 的物品”的要求），且一定不会没购买；\(z < i\) 的 \(i\) 一定不会被购买。

那么总共花费为 \(2 + \sum_{i=1}^{x-1}1 + [w_i = 2] + \sum_{i=x+1}^{y-1}[w_i = 1]\)，即要求 \(\sum_{i=1}^{x-1}[w_i = 2] + \sum_{i=x+1}^{y-1}[w_i = 1] = m - x - 1\)。

这个东西是简单的，相当于 \(x - 1\) 和 \(y - x - 1\) 中共选 \(m - x - 1\) 个翻转，方案数为 \({ {y - 2}\choose{m - x - 1} }\cdot 2^{n - z}\)。

对于确定的 \(x, y\)，满足条件的 \(z\) 是一个后缀，\(\sum 2^{n-z}\) 可以 \(O(1)\) 计算。

再算一下将所有 \(w_i = 1\) 的物品选完后还剩一块钱花不出去的情况，做完了。

写错了两个东西，一直调到 10:40。

看 C 题，有一种和一个月前的 D 题一样的感觉——编不出半个复杂度优于指数的做法。

看 D 题，这个 ABCDE 性质一看就能拼很多分，开拼。

最后拼了 C 的前两个点，D 的前三个点和 AB 性质。

估分 \(100+100+8+40=248\)。