CVBB ACM Team

到此差别页面的链接

--- 2020-2021:teams:running_chicken:2020_summer_week5_report [2020/08/14 13:35]
yyxzhj
+++ 2020-2021:teams:running_chicken:2020_summer_week5_report [2020/08/18 17:58] (当前版本)
yyxzhj
@@ 行 21: / 行 21: @@
 牛客暑期多校训练营（第四场）CJY E/J XX G ZRX **I**
-牛客暑期多校训练营（第五场）CJY G/J ZRX A/H
+牛客暑期多校训练营（第五场）CJY G/J ZRX **A**/**H**
-牛客暑期多校训练营（第六场）CJY D XX I ZRX F
+牛客暑期多校训练营（第六场）CJY F XX I ZRX D
-牛客暑期多校训练营（第七场）CJY E XX F ZRX A/C
+牛客暑期多校训练营（第七场）CJY E XX **F** ZRX A/**C**
-牛客暑期多校训练营（第八场）CJY D XX J ZRX B/C
+牛客暑期多校训练营（第八场）CJY **D** XX J ZRX B/C
-牛客暑期多校训练营（第九场）CJY **H** XX G ZRX L
+牛客暑期多校训练营（第九场）CJY **H** XX **G** ZRX L
-牛客暑期多校训练营（第十场）CJY G/H XX B/**D** ZRX F
+牛客暑期多校训练营（第十场）CJY G/**H** XX B/**D** ZRX F
 加赛1 CJY A/E XX B/C ZRX D
@@ 行 37: / 行 37: @@
 加赛2 CJY E
-ICPC北京 CJY **C** XX D ZRX E (BFH)
+ICPC北京 CJY **C** XX **D** ZRX E (BFH)
 =====CJY=====
 ====专题====
-可撤销并查集
+无
 ====比赛====
-.8.5 Codeforces Round #660
+.08.12 AtCoder Grand Contest 047
+.08.13 Codeforces Round #664
 ====题目====
-牛客多校训练营（第七场）I/J
+ICPC Beijing C D
-牛客多校训练营（第八场）A
+牛客多校训练营（第九场）D H
-台大选拔赛 B/C
 =====ZRX=====
@@ 行 121: / 行 122: @@
 =====cjy=====
+牛客多校训练营（第九场）D
-牛客多校训练营（第八场）A
 **题意**
-有n个粉丝，m个球员，每个球员都有若干粉丝，一个粉丝会看另外一个球员的比赛，要不是他说这个球员的粉丝，要不是它喜欢的球员有粉丝会
+有一棵树，n个点，每一条边只能是编号在$[L_i,R_i]$内的人通过，问每个人在通过不超过$K_i$($K_i\leq1$)条自己不能通过的边所能到达的点的数量。
-看这个球员的比赛，求最少选几个球员就可以使所有人都去看比赛。
 **思路**：
-显然这个是和连通块有关的问题，如果有一个粉丝是孤立的连通块，那么答案就是-1，否则答案就是连通块个数减去孤立孤立球员的个数。
+容易想到用线段树维护加边，这样就转化成在线段树dfs，用可撤销并查集来维护连通块的一个问题。
+当然K=0就已经完美解决了，我们发现K=1时要求的是这个连通块往外一步的点的个数，第一反应是去维护这个值，发现做不到，于是我们意识到
+要利用树的性质。
+考虑每个联通块维护除根节点向上以外的所有不属于这个连通块的一部点的数量，发现这个是可以维护的，只要维护每个连通块的最高节点就好
-维护图联通块的方法，采用LCT，或者离线可撤销并查集。对询问建线段树，把加边删边看成区间加边，然后把边放在线段树上，对这个线段树跑
+了。
-dfs用可撤销并查集维护连通性。
+再利用栈去维护修改操作就可了。
 **评论**：
-做法比较神奇，这个是从对询问操作的考虑入手的。
+可撤销并查集是一个好东西，就看你会不会用。
 =====XX=====
-====POI2007 odw_weight 砝码====
+====party====
-来源：POI 2007
+来源：CF 906 C
-算法：**贪心**、**进制拆分**
+算法：**状压DP**
-**题意**：搬运n个砝码，有m个容器。任何两个砝码都有一个特征，他们的中总有一个的重量是另外一个的整数倍，当然他们也可能相等。($1 \le n, m \le 100000$) 。$w_{i}$，表示每个容器能够装的最大质量。($1 \le w_{i} \le 1000000000 $)。 $m_{j}$，表示每个砝码的质量。($1 \le m_{j} \le 1000000000$)。求最多可以带走多少个砝码。
+**题意**：n个人，m条信息，每条信息为(x, y)表示x和y认识。每次操作可以选取一个人，让他的所有朋友相互认识。求使得所有人相互认识的最少操作次数以及对应的方案。（n$\leq$22）
 **思路**：
-注意条件：任意两个砝码中总有一个的重量是另外一个的整数倍。设最小的为x,则次小的可以写成xy，第三小的可以写成xyz,……以此类推。因此最多有$log_{2} max_{1 \le i \le n} m_{i}$个本质不同的砝码。
+操作的实际意义是什么？
-思考贪心策略
+将一个的所有朋友合并到同一个集合中，这个集合中的元素相互认识。
-小的砝码必然要优先满足。如果一个容器能装下一个重量为kx的砝码，那么优先满足x的砝码，然后再满足kx的砝码。
+操作即是集合合并。
+顺序不影响结果！
+对于a, b两次操作，如果先a后b和先b后a的结果是一样的。
+所以，动态规划时只需要记录集合中有哪些元素即可。
+同时，我们也可以知道同一个元素最多只会被操作一次。
-进制拆分，按照砝码重量将容器的容积进行拆分。
-例如：砝码 2 4 12， 容器18 = 12 * 1 + 4 * 1 + 2 * 1，13 = 12 * 1 + 剩下的不要了。
 **实现**
-找出本质不同的砝码，将所有容器的容量按照这些砝码进行拆分。拆分以后，统计所有容器拆出来每一位的数量。从小到大枚举砝码，如果这一位有，那么这一位的数量-1， 否则向高位借。
+预处理每一个点的朋友。
+初始，每一个点的朋友集合的操作数为1。
+状态S表示现有的集合。
+枚举元素i, 操作i，到达新状态S'。
+DP的过程中记录方案。
+注意特判答案为0的情况
+[[http://codeforces.com/problemset/problem/906/C|题目]]
+[[http://codeforces.com/contest/906/submission/88668069|代码]]
+**评论**：
-[[https://www.luogu.com.cn/problem/P3462|题目]]
+状压DP的一种变式。
-代码很简单，就不放代码了
-P.S.少见的贪心题目，进制拆分的思想很巧妙。

CVBB ACM Team

用户工具

站点工具

页面工具