2020-2021:teams:mian:weekly_report:2020_summer_week_1_report
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:mian:weekly_report:2020_summer_week_1_report [2020/07/17 22:56] grapelemonade [比赛] |
2020-2021:teams:mian:weekly_report:2020_summer_week_1_report [2020/07/17 23:05] (当前版本) withinlover |
||
|---|---|---|---|
| 行 84: | 行 84: | ||
| [[https://atcoder.jp/contests/agc002/tasks/agc002_d|AGC002 D]] | [[https://atcoder.jp/contests/agc002/tasks/agc002_d|AGC002 D]] | ||
| + | |||
| + | * 分类：Kruskal重构树，整体二分 | ||
| + | * 题意：给定一个无向图，n个点m条边，每次询问一对（x，y，z），求从x，y开始，走过z个点所经过的边的编号最大值的最小值 | ||
| + | * 解法：按编号枚举，可以二分答案然后在Kruskal重构树上倍增。正解是整体二分复杂度少个$\log$（反正我大暴力写过了） | ||
| + | * 评论：当初觉得这种建树思路挺好的，查了题解发现是自己Naive了 | ||
| + | |||
| ===== Gary ===== | ===== Gary ===== | ||
| 行 91: | 行 97: | ||
| * 分类：凸包 | * 分类：凸包 | ||
| * 题意：n个人比赛，游泳和赛跑，游泳距离S，赛跑R。每个人对应两个速度（陆地和水上的），如果存在S，R，使得第i个人胜利，则输出i | * 题意：n个人比赛，游泳和赛跑，游泳距离S，赛跑R。每个人对应两个速度（陆地和水上的），如果存在S，R，使得第i个人胜利，则输出i | ||
| - | * 解法：花费时间可以看做 | + | * 解法：花费时间可以看做$\frac{S}{v_s}+\frac{R}{v_R}$，也就是（S，R）和（$\frac{1}{v_s}+\frac{1}{v_R}$）的点积，简单画图推理可以发现只有凸包上的点可以满足，因而直接维护凸包即可 |
| - | * 评论： | + | * 评论：转到平面上做日常想不到 |
2020-2021/teams/mian/weekly_report/2020_summer_week_1_report.1594997807.txt.gz · 最后更改: 2020/07/17 22:56 由 grapelemonade
