日记

神秘搜索综合训练。

Grid of Letters# Link to

记忆化搜索板子题

Item Crafting# Link to

观察到 $n \le 15$，考虑 $2^n$ 枚举每种集合。先记搜出每个传奇对于每种原材料都需要多少个，然后直接枚举每种集合，看看哪种最多就好。

但是出题人不是人，还会爆 long long，甚至 __int128。

Chevonne’s Necklace# Link to

最终的答案就是以 $n$ 为容量，$c_i$ 为质量的 01 背包方案数。

让我们来证明一下：设选中的珍珠下标为 $p_1,p_2,p_3,\dots,p_k$。显然有 $\sum\limits_{i = 1}^{k}c_{p_i} \le n$。设 $d_{p_i}$ 表示 $p_i$ 之后选的那个与当前的距离，显然有 $c_{p_i} \le d_{p_i}$。根据鸽巢原理，显然每次都会有一个合法的备选。而题目里的方案又说的是：不同的集合视为不同的方案。那么就更不关顺序的事了。

剩下的等明天再写吧。

后日谈 # Link to 后日谈

今天是 3 月的最后一天。马上就到半期了，希望我能趁早把得分率提到 $\ge 30 \%$。

我会成为新的王 # Link to 我会成为新的王