2020.07.25 2020牛客暑期多校训练营（第七场）

2020.07.27 2020牛客暑期多校训练营（第八场）

2020牛客暑期多校训练营（第七场）

2020牛客暑期多校训练营（第八场）CJY A XX H ZRX C

2019台大选拔赛 CJY D XX F/H

Codeforces

整理了点分治、倍增优化DP、状压DP相关题目，稍后上传到csdn上

2020.08.05 Codeforces div3

2020牛客多校训练营（第八场）H

2019台大选拔赛 F/H

题意

思路：

评论：

贪心、进制拆分

题意：搬运n个砝码，有m个容器。任何两个砝码都有一个特征，他们的中总有一个的重量是另外一个的整数倍，当然他们也可能相等。($1 \le n, m \le 100000$) 。$w_{i}$，表示每个容器能够装的最大质量。($1 \le w_{i} \le 1000000000 $)。 $m_{j}$，表示每个砝码的质量。($1 \le m_{j} \le 1000000000$)。求最多可以带走多少个砝码。

思路：

注意条件：任意两个砝码中总有一个的重量是另外一个的整数倍。设最小的为x,则次小的可以写成xy，第三小的可以写成xyz,……以此类推。因此最多有$log_{2} max_{1 \le i \le n} m_{i}$个本质不同的砝码。

思考贪心策略

小的砝码必然要优先满足。如果一个容器能装下一个重量为kx的砝码，那么优先满足x的砝码，然后再满足kx的砝码。

进制拆分，按照砝码重量将容器的容积进行拆分。

例如：砝码 2 4 12， 容器18 = 12 * 1 + 4 * 1 + 2 * 1，13 = 12 * 1 + 剩下的不要了。

拆分以后，统计所有容器拆出来每一位的数量。从小到大枚举砝码，如果这一位有，那么这一位的数量-1， 否则向高位借。

P.S.少见的贪心题目，进制拆分的思想很巧妙。