======2020/08/08 -- 2020/08/14 周报====== ======团队====== 2020.08.08 [[.nowcodersummer9|2020牛客暑期多校训练营（第九场）]] 2020.08.10 [[.nowcodersummer10|2020牛客暑期多校训练营（第十场）]] 2020.08.12 [[.2015BeiJing|2015ICPC北京赛区]] ======个人====== =====todolist（补题）===== 2020牛客暑期多校训练营（第一场）CJY G XX C 2020牛客暑期多校训练营（第二场）**Finish** 2020牛客暑期多校训练营（第三场）CJY J/K ZRX I 2020牛客暑期多校训练营（第四场）CJY E/J XX G ZRX **I** 2020牛客暑期多校训练营（第五场）CJY G/J ZRX **A**/**H** 2020牛客暑期多校训练营（第六场）CJY F XX I ZRX D 2020牛客暑期多校训练营（第七场）CJY E XX **F** ZRX A/**C** 2020牛客暑期多校训练营（第八场）CJY **D** XX J ZRX B/C 2020牛客暑期多校训练营（第九场）CJY **H** XX **G** ZRX L 2020牛客暑期多校训练营（第十场）CJY G/**H** XX B/**D** ZRX F 2020加赛1 CJY A/E XX B/C ZRX D 2020加赛2 CJY E 2015ICPC北京 CJY **C** XX **D** ZRX E (BFH) =====CJY===== ====专题==== 无 ====比赛==== 2020.08.12 AtCoder Grand Contest 047 2020.08.13 Codeforces Round #664 ====题目==== 2015ICPC Beijing C D 2020牛客多校训练营（第九场）D H =====ZRX===== ====专题==== 从二分图最大匹配到二分图最优匹配 ====比赛==== 2020.08.08 [[.nowcodersummer9|2020牛客暑期多校训练营（第九场）]] 2020.08.10 [[.nowcodersummer10|2020牛客暑期多校训练营（第十场）]] 2020.08.12 [[.2015BeiJing|2015ICPC北京赛区]] atcoder abc 171 atcoder abc 172 ====题目==== 2020牛客暑期多校训练营（第四场）I atcoder abc 171 F atcoder abc 172 E =====XX===== ====专题==== 无 ====比赛==== 2020/08/12 codeforces 664 ====题目==== 2020牛客暑期多校训练营2020（第8场） F/H 2020牛客暑期多校训练营2020第9场 A 2020牛客暑期多校训练营2020第10场 D ======本周推荐====== =====zrx===== **题意** atcoder abc 171 F 长度为n(<=1e6)的只有26个小写字母的串，往进再插入k个(<=1e6)个小写字母，能组成多少种不同的串。 **思路**： 考虑最终的串，先把n个本身的串插进去，然后要求如果有重复的话，要求本身的串插进去的必须是最后一个出现的位置。 所以枚举第一个字符插到i，前面是随便填的，$26^{i-1}$,然后其他n-1个就通过一个组合数知道了方案数，至于剩下的没有被插入的位置，由于我们规定了原字符是出现的最后一个位置，所有它后面到下一个字符出现前只有25种选法，所以再乘上25的剩下位置次方即可。 **评论**： 找到一个好的去重姿势 =====cjy===== 2020牛客多校训练营（第九场）D **题意** 有一棵树，n个点，每一条边只能是编号在$[L_i,R_i]$内的人通过，问每个人在通过不超过$K_i$($K_i\leq1$)条自己不能通过的边所能到达的点的数量。 **思路**： 容易想到用线段树维护加边，这样就转化成在线段树dfs，用可撤销并查集来维护连通块的一个问题。 当然K=0就已经完美解决了，我们发现K=1时要求的是这个连通块往外一步的点的个数，第一反应是去维护这个值，发现做不到，于是我们意识到 要利用树的性质。 考虑每个联通块维护除根节点向上以外的所有不属于这个连通块的一部点的数量，发现这个是可以维护的，只要维护每个连通块的最高节点就好 了。 再利用栈去维护修改操作就可了。 **评论**： 可撤销并查集是一个好东西，就看你会不会用。 =====XX===== ====party==== 来源：CF 906 C 算法：**状压DP** **题意**：n个人，m条信息，每条信息为(x, y)表示x和y认识。每次操作可以选取一个人，让他的所有朋友相互认识。求使得所有人相互认识的最少操作次数以及对应的方案。（n$\leq$22） **思路**： 操作的实际意义是什么？ 将一个的所有朋友合并到同一个集合中，这个集合中的元素相互认识。 操作即是集合合并。 顺序不影响结果！ 对于a, b两次操作，如果先a后b和先b后a的结果是一样的。 所以，动态规划时只需要记录集合中有哪些元素即可。 同时，我们也可以知道同一个元素最多只会被操作一次。 **实现** 预处理每一个点的朋友。 初始，每一个点的朋友集合的操作数为1。 状态S表示现有的集合。 枚举元素i, 操作i，到达新状态S'。 DP的过程中记录方案。 注意特判答案为0的情况 [[http://codeforces.com/problemset/problem/906/C|题目]] [[http://codeforces.com/contest/906/submission/88668069|代码]] **评论**： 状压DP的一种变式。