2020/08/29 – 2020/09/04 周报
团队训练
无
李英龙
专题
无
比赛
题目
无
陈源
专题
无
比赛
无
题目
胡琎
专题
无
比赛
题目
本周推荐
李英龙
对树上问题进行了一些总结：
陈源
CF Round #660E
Tag : Convex Hull Trick
题意：给定n条水平片段，保证互相不重叠，需要选择一个方向，将这些线段投影到x轴上，需要保证这些投影不相交（可以相接触），问这些投影的x轴坐标的最大值和最小值的差最小可以是多少。
题解：发现最优的方向向量，一定会存在两个线段，他们的投影相接触，所以这样我们暴力两两枚举，每一组能找到两个方向向量使其相接触，可以得到$2*n^2$个方向向量，随后我们要去掉其中可能会导致存在重叠投影的方向向量（这一步只需要计算夹角即可），然后在剩下的方向向量中找到最优的那个，经过计算，若方向向量的斜率为$k$，则对于点$(a,b)$，其投影x坐标为$a+bk$，于是我们的答案就是$\max{(a_i - b_i * k)} - \min{(a_i - b_i * k)}$，我们将其看成有多条直线$y = a_i + b_i * x$，对这些直线取同一个x值求最值，用Convex Hull Trick，按照斜率排序以及二分查找，可以在$logn$的时间里完成。
胡琎
Codeforces Round #657 (Div. 2) E. Inverse Genealogy
题意：如果一个节点的左右子树节点数相差一倍或以上，则称这个节点是不平衡的。给定n, k,尝试构造包含n个节点、k个不平衡节点的二叉树。
可以发现n个节点最多包含（n-3）/2个不平衡节点，且n一定是奇数。如果所有节点都是平衡的，那么这颗树一定是满二叉树，即n+1为2的幂。反过来，如果n+1是2的幂那么一定无法构造出1个不平衡节点的二叉树。
另外，也存在一些特殊的情况如n=9,k=2无法构造。
如果采用递归向下构造，将k分割到两个子树中，很容易出现构造失败的情况，难以确定k合适的值。对于k=1的情况可以比较容易的构造出解或判定无解，只有左子树=右子树节点数*2或左子树k=0，右子树k=1两种情况。比较难想到的是可以从根部向上构造，这样可以确保新加入的根节点是不平衡的，即增加2n个节点，n个不平衡节点。
结合后两种方法，再在无解的时候（即无法构造k=1的子树）尝试做一些调整，避开2的幂就可以过了。n<13的情况下可以直接递归向下构造子树，在k=1、k=2的情况下特判。
Comment：这道题赛前没有人通过，做的过程中也遇到了不少坑。实际上可以打表验算一下/使用暴力方法对拍验证思路。
Tag：二叉树、构造
