D5题解

题解 爆零

届不到的数

神奇的集合有$2^n$个集合

30

暴搜

60

老师也不知道怎么做

100

直观想法先排个序，先考虑小的数字
考虑前缀集合与下一个元素的关系
下一个就是当前能找到的最小数字，如果下一个数永远大于能拼出来的数，那么一定不能拼出来。
因此排序之，如果前缀和+1比下一个元素大就符合条件。

整除

30

枚举一下

60

O$\sqrt n$，每次找一个不同的答案

for(int i=1;i<=n;++i){
    int a=n/i;
    int b=n/a;//最大的能够得到该值的东西
    i=b;//跳过重复
}

100

先打一个表，观察一下
10 5 3 2 1
分两段，找出分界点。
$\dfrac{n}{i}-\dfrac{n}{i+1}<=1$就会跳过去，因此把这个解出来可以得到一个O(1)的算法。

也可以二分，不过很多坑，并不是完全单调的。也可以按上面那个式子二分，通个分乱搞。

T3

100 输出样例

这个评测机不错，我喜欢.jpg

30 60

暴搜

100

Meet in the Middle思想
问题可以根据左边的信息搞出来右边的信息，将一一对应的搜索变成一块一块的
搜索时为Q<钻石,钱,概率>
分成两堆。先暴搜第一堆，然后按钻石数量分块。
于是第一堆结果为$<a,b,c>$的话，由于钻石数必须严格为k，那么我们要的第二堆就是$<k-a,r,q>$，其中r>=m。如果按m排个序，从大到小找符合的结果，最后的q就是将这些对应的c全部加起来。这里用一个前缀和预处理。
也就是说，我们这种方式，可以将求第二堆的结果的复杂度大量缩减。
代码是啥意思...懵逼状