2020-2021:teams:acm_life_from_zero:8.1-8.7
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 | |||
|
2020-2021:teams:acm_life_from_zero:8.1-8.7 [2020/08/07 15:43] holmium [姜维翰] |
2020-2021:teams:acm_life_from_zero:8.1-8.7 [2020/08/07 17:00] (当前版本) kipple |
||
|---|---|---|---|
| 行 14: | 行 14: | ||
| ====== 袁熙 ====== | ====== 袁熙 ====== | ||
| - | ===== 专题 ===== | ||
| - | 没有专题 | ||
| ===== 比赛 ===== | ===== 比赛 ===== | ||
| - | 没有比赛 | + | cf round 661 |
| - | ===== 题目 ===== | + | |
| - | 补题（板子） 牛客第五场B \\ [[https://ac.nowcoder.com/acm/contest/5670|链接]] \\ | + | |
| - | 题意；给边带权的树，可以连边或删边，要求始终连通且形成的环异或和=0，求最后图的最小权值和\\ | + | |
| - | 思路：对原图的树，可以把边权用所连点的权值异或和来表示，转化成异或最小生成树\\ | + | |
| - | 类似的模板题：[[http://codeforces.com/problemset/problem/888/G|链接]] | + | |
| ====== 本周推荐 ====== | ====== 本周推荐 ====== | ||
| ====== 李元恺 ====== | ====== 李元恺 ====== | ||
| 行 39: | 行 34: | ||
| comment:这周做的最有意思的题，推荐给大家 | comment:这周做的最有意思的题，推荐给大家 | ||
| ====== 袁熙 ====== | ====== 袁熙 ====== | ||
| + | cf 1380e Inverse Genealogy | ||
| + | |||
| + | tag：构造 分治 | ||
| + | |||
| + | 题意：对给定的n,k，构造一颗完全二叉树使这棵树的n个节点中，k个点满足其一个儿子所在子树大小是另一个的至少两倍 | ||
| + | |||
| + | 题解： | ||
| + | |||
| + | 观察一下后可以发现符合题意的树的这些性质： | ||
| + | |||
| + | 1.有奇数个点，且k不大于(n-3)/2 | ||
| + | |||
| + | 2.当且仅当2^x=n+1时，可以有k=0 | ||
| + | |||
| + | 3.(n,k)可以向(n-2,k-1)转化 | ||
| + | |||
| + | 又可以发现，k=1时，只要n+1≠2^x,按顺序从根向下在每层放满点就可以满足要求，问题变成怎么放点能使(n-2*k+2,1)转变到(n,k) | ||
| + | |||
| + | 对n-2*k+2≠2^x的情况，我们要在不破坏之前结果的情况下构造。由(n-2*k+2,1)的构造可以知道满足题意的点所在的位置，在维护之前大小关系的情况下放点。 | ||
| + | n-2*k+2=2^x时，不存在(n-2*k+2,1)的构造，可以先提前留下几个点，然后当做上面的情况继续构造，最后将这些点放在不影响结果的位置 | ||
| + | |||
| + | comment：有点麻烦的构造题。。没有看到能比较好的做最后一步转化的方法 | ||
| + | |||
| ====== 姜维翰 ====== | ====== 姜维翰 ====== | ||
2020-2021/teams/acm_life_from_zero/8.1-8.7.1596786191.txt.gz · 最后更改: 2020/08/07 15:43 由 holmium
