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:15]
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:这周做的最有意思的题，推荐给大家
 ====== 袁熙 ======
+cf 1380e Inverse Genealogy
+tag：构造 分治
+题意：对给定的n,k，构造一颗完全二叉树使这棵树的n个节点中，k个点满足其一个儿子所在子树大小是另一个的至少两倍
+题解：
+观察一下后可以发现符合题意的树的这些性质：
+.有奇数个点，且k不大于(n-3)/2
+.当且仅当2^x=n+1时，可以有k=0
+.(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：有点麻烦的构造题。。没有看到能比较好的做最后一步转化的方法
 ====== 姜维翰 ======
+cf 1382e mastermind
+tag：贪心
+题意：给n,x,y和一个长n的数组，数组元素的大小为1到n+1间的整数，求另一个数组，元素大小同样在1到n+1，两个数组元素相同的位置有x个，重新排列后两个数组最多有y个相同位置的元素相同
+题解：首先对出现的元素进行计数，显然要把x的指标优先给数量多的元素
+这样还剩下n-x个元素，对于这n-x个元素，两个数组在不重新排列前不能有匹配，对于一某种元素c，假设它有k个，如果2*k>n-x，那么必然有一部分元素要变成其它的元素，n个位置有n+1种元素，所以这个用来替换的元素是一定存在的，而如果出现这样的情况，n-x这一部分在重排之后至多能匹配2*(n-x-k)个，也就是要2*(n-x-k)>=y-x，化简得2*n-x-y>=2*k，不满足则无解
+对于有解的情况就比较简单了，对n-x这部分的元素排序，然后旋转(n-x)/2之后放进去，再把n-y个位置的元素换成不存在过的元素就可以了
+comment：很妙的题，尤其是对于无解的判断

2020-2021/teams/acm_life_from_zero/8.1-8.7.1596784511.txt.gz · 最后更改: 2020/08/07 15:15 由 holmium