2020-2021:teams:too_low:0829-0904
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:too_low:0829-0904 [2020/09/04 11:22] jim [胡琎] |
2020-2021:teams:too_low:0829-0904 [2020/09/04 17:53] (当前版本) jim [题目] |
||
|---|---|---|---|
| 行 17: | 行 17: | ||
| ==== 比赛 ==== | ==== 比赛 ==== | ||
| - | 无 | + | [[https://blog.csdn.net/dragonylee/article/details/108343568|CodeForces Round #666 (div. 1)]] |
| + | |||
| + | [[https://blog.csdn.net/dragonylee/article/details/108310926|Educational Codeforces Round 94 (Div. 2)]] | ||
| + | |||
| + | [[https://blog.csdn.net/dragonylee/article/details/108359309|Codeforces Global Round 10 / contest 1392]] | ||
| ==== 题目 ==== | ==== 题目 ==== | ||
| 行 37: | 行 41: | ||
| ==== 题目 ==== | ==== 题目 ==== | ||
| - | 无 | + | [[http://member.bitcron.com/post/ti-jie/cfedu92|Codeforces Educational Round 92 EFG]] |
| <html><br/></html> | <html><br/></html> | ||
| 行 49: | 行 53: | ||
| ==== 比赛 ==== | ==== 比赛 ==== | ||
| - | 无 | + | [[2020-2021:teams:too_low:abc177hj|AtCoder Beginner Contest 177]] |
| ==== 题目 ==== | ==== 题目 ==== | ||
| 行 61: | 行 64: | ||
| ==== 李英龙 ==== | ==== 李英龙 ==== | ||
| - | 无 | + | 对树上问题进行了一些总结： |
| + | |||
| + | [[https://blog.csdn.net/dragonylee/article/details/104091056|树上问题]] | ||
| ==== 陈源 ==== | ==== 陈源 ==== | ||
| - | 无 | + | 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$的时间里完成。 | ||
| ==== 胡琎 ==== | ==== 胡琎 ==== | ||
| 行 79: | 行 89: | ||
| 如果采用递归向下构造，将k分割到两个子树中，很容易出现构造失败的情况，难以确定k合适的值。对于k=1的情况可以比较容易的构造出解或判定无解，只有左子树=右子树节点数*2或左子树k=0，右子树k=1两种情况。比较难想到的是可以从根部向上构造，这样可以确保新加入的根节点是不平衡的，即增加2n个节点，n个不平衡节点。 | 如果采用递归向下构造，将k分割到两个子树中，很容易出现构造失败的情况，难以确定k合适的值。对于k=1的情况可以比较容易的构造出解或判定无解，只有左子树=右子树节点数*2或左子树k=0，右子树k=1两种情况。比较难想到的是可以从根部向上构造，这样可以确保新加入的根节点是不平衡的，即增加2n个节点，n个不平衡节点。 | ||
| - | 结合后两种方法，再在无解的时候（即无法构造k=1的子树）和尝试做一些调整，避开2的幂就可以过了。n<13的情况下可以直接递归向下构造子树，在k=1、k=2的情况下特判。 | + | 结合后两种方法，再在无解的时候（即无法构造k=1的子树）尝试做一些调整，避开2的幂就可以过了。n<13的情况下可以直接递归向下构造子树，在k=1、k=2的情况下特判。 |
| Comment：这道题赛前没有人通过，做的过程中也遇到了不少坑。实际上可以打表验算一下/使用暴力方法对拍验证思路。 | Comment：这道题赛前没有人通过，做的过程中也遇到了不少坑。实际上可以打表验算一下/使用暴力方法对拍验证思路。 | ||
2020-2021/teams/too_low/0829-0904.1599189768.txt.gz · 最后更改: 2020/09/04 11:22 由 jim
