CodeStar2023年春第11周周赛普及进阶组

发布时间 2023-06-13 20:01:36作者: V_Melville

T1:等差数

本题难度中等,公差等于 \(0\) 的等差数只含一种数码,公差不等于 \(0\) 的等差数只有几百个。所以本题的方针是先把公差不等于 \(0\) 的等差数都找出来。在公差等于 \(0\) 和公差不等于 \(0\) 的两类中分别找大于 \(n\) 的最小树,两者较小的就是答案。

T2:炼金工坊补充道具

本题难度较大,以消耗能量为物品大小,造成伤害为物品价值,做多重背包即可。

\(q_i\) 是第 \(i\) 种物品的个数
\(c\) 作为物品大小,\(d\) 作为物品价值

dp[i][j] 表示用前 \(i\) 个总大小恰好等于 \(j\) 的物品能选出的最大总价值

\(j\) 最大可达 \(\max(n) \cdot \max(q) \cdot \max(c) = 10^5\)
\(i\) 最大可达 \(\max(n) \cdot \log_2 \max(q) = 700\)

答案为使得 \(dp[cnt][j] \geqslant H\) 的最小 \(j\)
(\(cnt\) 是拆分后的物品个数)