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
Codeforces 1153F
- 分类：动态规划、概率
- 题意：在一条长度为$l$的线段上随机出现$n$条线段，求被$k$条线段覆盖的长度之和
- 题解：$dp[i][j]$用来表示前$i$个端点里有$j$个起点没有被匹配的方案数，然后转移的时候就有两种情况，要么是起点，要么是终点
- comment：学弟出的题真的🐂啊，，，
JJLeo
题目名称
- 分类：
- 题意：
- 题解：
- comment：
个人训练
2sozx
比赛
题目
Bazoka13
比赛
题目
JJLeo
比赛
题目
2020-2021/teams/farmer_john/week_16.1597998863.txt.gz · 最后更改: 2020/08/21 16:34 由 bazoka13
