CVBB ACM Team

用户工具

站点工具

您在这里: front_page » 2020-2021 » teams » running_chicken » 2020_summer_week4_report
2020-2021:teams:running_chicken:2020_summer_week4_report

差别

这里会显示出您选择的修订版和当前版本之间的差别。

到此差别页面的链接

两侧同时换到之前的修订记录 前一修订版
后一修订版 		前一修订版
2020-2021:teams:running_chicken:2020_summer_week4_report [2020/08/07 11:15]
selia [题目] 		2020-2021:teams:running_chicken:2020_summer_week4_report [2020/08/16 14:50] (当前版本)
selia [todolist（补题）]
行 1: 行 1:
-======2020/07/25 -- 2020/07/31 周报======+======2020/08/01 -- 2020/08/07 周报======
  
 ======团队====== ======团队======
行 11: 行 11:
 =====todolist（补题）===== =====todolist（补题）=====
  
-2020牛客暑期多校训练营（第七场）+2020牛客暑期多校训练营（第七场）CJY E XX F ZRX A/C
  
-2020牛客暑期多校训练营（第八场）CJY A XX **H** ZRX C+2020牛客暑期多校训练营（第八场）CJY ​**A**/D XX **H**/J ZRX B/C
  
 2019台大选拔赛 CJY **D** XX **F**/**H** 2019台大选拔赛 CJY **D** XX **F**/**H**
  
-Codeforces ​+2020.08.07 ​Codeforces ​Round #622 XX **E**
 =====CJY===== =====CJY=====
  
 ====专题==== ====专题====
 +可撤销并查集
 ====比赛==== ====比赛====
 +2020.8.5 Codeforces Round #660
 ====题目==== ====题目====
 +
 +2020牛客多校训练营（第七场）I/​J
 +
 +2020牛客多校训练营（第八场）A
 +
 +2019台大选拔赛 B/C
  
 =====ZRX===== =====ZRX=====
  
 ====专题==== ====专题====
 +
 +本周暂无
  
 ====比赛==== ====比赛====
 +
 +2020牛客暑期多校训练营（第七场）
 +
 +2020牛客暑期多校训练营（第八场）
 +
 +2019台大选拔赛 ​
  
 ====题目==== ====题目====
 +
 +2020牛客暑期多校训练营（第七场）C
 +
 +2020牛客暑期多校训练营（第八场）C
  
 =====XX===== =====XX=====
行 55: 行 73:
 =====zrx===== =====zrx=====
  
 +**题意**
 +
 +2020牛客暑期多校训练营（第八场）C
 +
 +N*M的格子放炸弹，炸弹可以覆盖四联通及自己，问N*M格子最少放多少个可以覆盖完整个格子。
 +
 +**思路**：
 +
 +M<​=15,​也显然要三进制表示，但是状态众多怎么办？
 +
 +有太多无用的状态了！
 +
 +肯定不可能连放炸弹，或者连续两个都没被覆盖。
 +
 +压缩一下状态数只有几千。
 +
 +DP。
 +
 +**评论**：
 +
 +状态压缩要压缩状态。
  
 =====cjy===== =====cjy=====
 +
 +
 +2020牛客多校训练营（第八场）A
  
 **题意** **题意**
 +
 +有n个粉丝，m个球员，每个球员都有若干粉丝，一个粉丝会看另外一个球员的比赛，要不是他说这个球员的粉丝，要不是它喜欢的球员有粉丝会
 +
 +看这个球员的比赛，求最少选几个球员就可以使所有人都去看比赛。
  
 **思路**： **思路**：
 +
 +显然这个是和连通块有关的问题，如果有一个粉丝是孤立的连通块，那么答案就是-1，否则答案就是连通块个数减去孤立孤立球员的个数。
 +
 +维护图联通块的方法，采用LCT，或者离线可撤销并查集。对询问建线段树，把加边删边看成区间加边，然后把边放在线段树上，对这个线段树跑
 +
 +dfs用可撤销并查集维护连通性。
  
 **评论**： **评论**：
 +
 +做法比较神奇，这个是从对询问操作的考虑入手的。
  
 =====XX===== =====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.少见的贪心题目，进制拆分的思想很巧妙。
  
  
2020-2021/teams/running_chicken/2020_summer_week4_report.1596770135.txt.gz · 最后更改: 2020/08/07 11:15 由 selia

页面工具

除额外注明的地方外，本维基上的内容按下列许可协议发布： CC Attribution-Share Alike 4.0 International
CC Attribution-Share Alike 4.0 International Donate Powered by PHP Valid HTML5 Valid CSS Driven by DokuWiki
京ICP备20018844号-3