2020-2021:teams:running_chicken:2020_summer_week4_report

差别

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

到此差别页面的链接

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

2020-2021/teams/running_chicken/2020_summer_week4_report.1596770979.txt.gz · 最后更改: 2020/08/07 11:29 由 selia