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

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

2020牛客暑期多校训练营（第七场）CJY E XX F ZRX A/C

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

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

2020.08.07 Codeforces Round #622 XX E

可撤销并查集

2020.8.5 Codeforces Round #660

2020牛客多校训练营（第七场）I/J

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

2019台大选拔赛 B/C

本周暂无

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

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

2019台大选拔赛

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

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

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

2020.08.05 Codeforces div3

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

2019台大选拔赛 F/H

题意

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

N*M的格子放炸弹，炸弹可以覆盖四联通及自己，问N*M格子最少放多少个可以覆盖完整个格子。

思路：

M⇐15,也显然要三进制表示，但是状态众多怎么办？

有太多无用的状态了！

肯定不可能连放炸弹，或者连续两个都没被覆盖。

压缩一下状态数只有几千。

DP。

评论：

状态压缩要压缩状态。

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

题意

有n个粉丝，m个球员，每个球员都有若干粉丝，一个粉丝会看另外一个球员的比赛，要不是他说这个球员的粉丝，要不是它喜欢的球员有粉丝会

看这个球员的比赛，求最少选几个球员就可以使所有人都去看比赛。

思路：

显然这个是和连通块有关的问题，如果有一个粉丝是孤立的连通块，那么答案就是-1，否则答案就是连通块个数减去孤立孤立球员的个数。

维护图联通块的方法，采用LCT，或者离线可撤销并查集。对询问建线段树，把加边删边看成区间加边，然后把边放在线段树上，对这个线段树跑

dfs用可撤销并查集维护连通性。

评论：

做法比较神奇，这个是从对询问操作的考虑入手的。

来源：POI 2007

算法：贪心、进制拆分

题意：搬运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.少见的贪心题目，进制拆分的思想很巧妙。