2020-2021:teams:farmer_john:week_16
这是本文档旧的修订版！
团队训练
| 比赛时间 | 比赛名称 | 当场过题数 | 至今过题数 | 总题数 | 排名 |
|---|---|---|---|---|---|
| 2020-08-20 | HDU 2020 Multi-University Training Contest 7 | 4 | 5 | 11 | 28/757 |
本周推荐
2sozx
WC2013 平面图
- 分类：平面图对偶图，点定位，扫描线，最小生成树，倍增
- 题意：给定一个平面图 $n\le10^5$，每条边有权值，$q$ 次询问，每次给出平面上两个点，问所有不通过无穷大平面的曲线链接这两个点所经过的边的最小值是多少。$q\le10^5$，平面图的点为整点，询问的点坐标为 $0.5$ 的奇数倍且不在边上。
- 题解：先用最左转线将平面图进行划分，转成对偶图，并且连边，求出对偶图的最小生成树。对于每个点我们要定位在属于对偶图的哪个点，因此将线段进行排序，用扫描线从左向右扫描，将扫到的线段插入 $treap$ 中，如果遇到了询问的点则在 $treap$ 中找到比这个点高的最低的线段，则这个点则属于这条线段下方的区域内，对于每个询问可以通过在最小生成树上倍增求解即可。
- comment：知识点巨多，虽然还没通过hack数据，但是感觉还是一道好题。
Bazoka13
题目名称
- 分类：
- 题意：
- 题解：
- comment：
JJLeo
题目名称
- 分类：
- 题意：
- 题解：
- comment：
个人训练
2sozx
比赛
题目
Bazoka13
比赛
题目
JJLeo
比赛
题目
2020-2021/teams/farmer_john/week_16.1597983672.txt.gz · 最后更改: 2020/08/21 12:21 由 2sozx
