[数据结构与算法]2021-08-09

1.倒酒：一道裸的拓欧，复习一下板子

2.Golden Feather：打表找规律，（题意是找一颗最小生成树，不是最短路），所以对于第n个点，若存在前面n-1个点中的一个与第n个点的gcd=1，则ans=n-1。因此，问题变为哪些数不符合该条件。而后就是数学证明，fn与fn-1,fn-2,...比较，筛出不符合条件的数

3.硬币购物：其实这道题挺巧妙的，这个数据就一直给我们提示，不可能多重背包暴力做，T飞了。所以一定是预处理好完全背包，再考虑怎么得到答案。然而我太蒻了想不出来，看完题解似乎看懂了，但是要自己推一边发现题解没有把思考步骤写下来。

①dp[i],因为需要预处理，所以表示选择前四个物品的完全背包，而又怎么与多重背包关联起来呢？我们发现每个物品i最多只能选di个，意味着第i个物品占(di+1)*ci个体积及以上是不可能的，而这个方案数就是dp[v-(di+1)*ci]，把这个减掉就行了。

②但是这是否做了对集合枚举的不重不漏呢?答案是否定的，在保证第1件物品多用了的同时，无法保证其他物品没有多用，所以dp[v-(d1+1)*c1]实际上把第2件物品多用，第3件物品多用......包含进去了，用二进制来说就是1000，1001,1010,1011,1100,1101,1110,1111这几种状态

代码不难，思路确实有点新颖