======2020/08/01 -- 2020/08/07 周报====== ======团队====== 2020.07.25 [[.nowcodersummer3|2020牛客暑期多校训练营（第七场）]] 2020.07.27 [[.nowcodersummer4|2020牛客暑期多校训练营（第八场）]] ======个人====== =====todolist（补题）===== 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** =====CJY===== ====专题==== 可撤销并查集 ====比赛==== 2020.8.5 Codeforces Round #660 ====题目==== 2020牛客多校训练营（第七场）I/J 2020牛客多校训练营（第八场）A 2019台大选拔赛 B/C =====ZRX===== ====专题==== 本周暂无 ====比赛==== 2020牛客暑期多校训练营（第七场） 2020牛客暑期多校训练营（第八场） 2019台大选拔赛 ====题目==== 2020牛客暑期多校训练营（第七场）C 2020牛客暑期多校训练营（第八场）C =====XX===== ====专题==== 整理了点分治、倍增优化DP、状压DP相关题目，稍后上传到csdn上 ====比赛==== 2020.08.05 Codeforces div3 ====题目==== 2020牛客多校训练营（第八场）H 2019台大选拔赛 F/H ======本周推荐====== =====zrx===== **题意** 2020牛客暑期多校训练营（第八场）C N*M的格子放炸弹，炸弹可以覆盖四联通及自己，问N*M格子最少放多少个可以覆盖完整个格子。 **思路**： M<=15,也显然要三进制表示，但是状态众多怎么办？ 有太多无用的状态了！ 肯定不可能连放炸弹，或者连续两个都没被覆盖。 压缩一下状态数只有几千。 DP。 **评论**： 状态压缩要压缩状态。 =====cjy===== 2020牛客多校训练营（第八场）A **题意** 有n个粉丝，m个球员，每个球员都有若干粉丝，一个粉丝会看另外一个球员的比赛，要不是他说这个球员的粉丝，要不是它喜欢的球员有粉丝会 看这个球员的比赛，求最少选几个球员就可以使所有人都去看比赛。 **思路**： 显然这个是和连通块有关的问题，如果有一个粉丝是孤立的连通块，那么答案就是-1，否则答案就是连通块个数减去孤立孤立球员的个数。 维护图联通块的方法，采用LCT，或者离线可撤销并查集。对询问建线段树，把加边删边看成区间加边，然后把边放在线段树上，对这个线段树跑 dfs用可撤销并查集维护连通性。 **评论**： 做法比较神奇，这个是从对询问操作的考虑入手的。 =====XX===== ====POI2007 odw_weight 砝码==== 来源：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， 否则向高位借。 [[https://www.luogu.com.cn/problem/P3462|题目]] 代码很简单，就不放代码了 P.S.少见的贪心题目，进制拆分的思想很巧妙。