2020-2021:teams:acm_life_from_zero:8.15-8.22
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:acm_life_from_zero:8.15-8.22 [2020/08/21 14:14] lak [比赛] |
2020-2021:teams:acm_life_from_zero:8.15-8.22 [2020/08/21 17:16] (当前版本) kipple [袁熙] |
||
|---|---|---|---|
| 行 40: | 行 40: | ||
| comment:这周写出来的最难的题 | comment:这周写出来的最难的题 | ||
| ===== 姜维翰 ===== | ===== 姜维翰 ===== | ||
| + | codeforces 1214E | ||
| + | |||
| + | 类型：构造，贪心，图论 | ||
| + | |||
| + | 题意：有2n个点，构造一棵树，满足编号2i和2i-1的点的距离恰好为di，保证1<=di<=n | ||
| + | |||
| + | 题解：首先对所有奇数点按di从大到小，从头到尾连成一条链，记下这条链 | ||
| + | |||
| + | 然后对奇数点从头到尾在链上添加对应的偶数点，如果某个偶数点正好加到链尾，则扩展这条链，这样的构造是一定存在的。 | ||
| + | |||
| + | 评论：奇妙的构造题 | ||
| ===== 袁熙 ===== | ===== 袁熙 ===== | ||
| + | codeforces 1388E\\ | ||
| + | |||
| + | 题意：$n（n\leq2000）$条不相交的线段，将他们按照同一方向投影到x轴上，要求投影不相交，求所有投影间最远两点的距离的最小值\\ | ||
| + | |||
| + | tag：计算几何，扫描线\\ | ||
| + | |||
| + | 题解：对任两条高度不同的线段，存在两个向量可以使他们投影的端点为同一点，最优解一定在所有这样的向量中。对每个向量，各点$(x,y)$投影的位置可以表示为$(x+y*arctan(\theta),0),\theta$代表向量与y轴夹角。这样就可以用凸包的形式$O(n^2log(n^2))$得到答案\\ | ||
| + | comment：这周补的比较有趣的题\\ | ||
2020-2021/teams/acm_life_from_zero/8.15-8.22.1597990492.txt.gz · 最后更改: 2020/08/21 14:14 由 lak
