RC-04 / InfOJ R1 题解

feecle6418 · 2020-12-12 22:18:20 · 个人记录

A

直接输出 90-x 即可，注意整形溢出，要开 long long。

B

答案为 (1+p^{a_1})(1+p^{a_2})(1+p^{a_3})\dots(1+p^{a_n})。

理解方式：

• 加入一个重量为 k 的物品后，可以不放入背包（价值和不变），可以放入背包（价值和乘上 p^k），所以应该乘上 (1+p^k)。
• 在生成函数角度下看，式子是显然的（

C

正难则反，记录积小于等于 m 的方案数。

可以背包，设 f_{i,j} 为前 i 个物品积为 j 的方案数，复杂度 O(\sum \dfrac{m}{a_i})。

把相同的 a_i 一块用组合数转移就能严格 O(n\log n)。常数很小。

D

直接 dfs，随便乱写就有 75。

考虑精细实现，每个位置保证只试探一次，就能 AC，可以证明操作次数不超过 2n^2。

E

一个有趣的 trick（我自己想出来的）