2020 年百度之星·程序设计大赛 - 复赛 rk:69 pros:3/6

Codeforces Round #664 (Div. 1) rk:131 pros:2/5

atcoder abc 174

cf round 661

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：有点麻烦的构造题。。没有看到能比较好的做最后一步转化的方法

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：很妙的题，尤其是对于无解的判断