2020-2021:teams:wangzai_milk:weekly15
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:wangzai_milk:weekly15 [2020/08/14 16:37] wzx27 |
2020-2021:teams:wangzai_milk:weekly15 [2020/08/14 18:25] (当前版本) zars19 [比赛] |
||
|---|---|---|---|
| 行 3: | 行 3: | ||
| ===== 团队训练 ===== | ===== 团队训练 ===== | ||
| + | 无。 | ||
| ===== _wzx27 ===== | ===== _wzx27 ===== | ||
| 行 35: | 行 36: | ||
| ==== 专题 ==== | ==== 专题 ==== | ||
| + | 无。 | ||
| ==== 题目 ==== | ==== 题目 ==== | ||
| + | 无。 | ||
| ==== 比赛 ==== | ==== 比赛 ==== | ||
| + | ◉ Codeforces Round 662 (Div. 2) | ||
| + | |||
| + | ◉ [[Codeforces Round 663 (Div. 2)]] **DONE** | ||
| + | |||
| + | ◉ Codeforces Round 664 (Div. 1) | ||
| + | |||
| + | ◉ AtCoder Grand Contest 047 | ||
| ===== 本周推荐 ===== | ===== 本周推荐 ===== | ||
| ==== Infinity37 ==== | ==== Infinity37 ==== | ||
| 行 72: | 行 82: | ||
| 如果从类似生成函数的角度入手，把贡献累计在 $x^i$ 的指数 $i$ 上就可以用 $\text{FFT}$ 求出贡献。但注意到只把指数作为模 $P$ 的值会有问题，由于 $x^i \cdot x^j = x^{i+j}$，但我们实际想要的是 $i*j$ 的答案。于是考虑原根的对数来表示就可以转化成乘法了。 | 如果从类似生成函数的角度入手，把贡献累计在 $x^i$ 的指数 $i$ 上就可以用 $\text{FFT}$ 求出贡献。但注意到只把指数作为模 $P$ 的值会有问题，由于 $x^i \cdot x^j = x^{i+j}$，但我们实际想要的是 $i*j$ 的答案。于是考虑原根的对数来表示就可以转化成乘法了。 | ||
| - | 先预处理出每个原根的幂次 $g^i \% P$ 的值和 $x = g^i \% p$ 的对应幂次 $i$,最后做一次 $\text{FFT}$ 即可，但注意要减去同一个数乘了自己的贡献。 | + | 先预处理出每个原根的幂次 $g^i \% P$ 的值和 $x = g^i \% p$ 的对应幂次 $i$,然后做一次 $\text{FFT}$ 即可，但注意要减去同一个数乘了自己的贡献。 |
| **comments**：一个原根的经典用法，需要掌握。 | **comments**：一个原根的经典用法，需要掌握。 | ||
| + | |||
| + | ==== Zars19 ==== | ||
| + | |||
| + | **来源**：CF1388E - Uncle Bogdan and Projections | ||
| + | |||
| + | **tag**：计算几何，Convex Hull Trick | ||
| + | |||
| + | **概述**： | ||
| + | |||
| + | 给 $x$ 轴以上的若干水平线段。现可以指定一个向量让所有线段沿该方向投影到 $x$ 轴上，投影不可以重叠，宽度定义为投影最右端横坐标减去最左端横坐标，问可能的最小宽度。 | ||
| + | |||
| + | **答案**： | ||
| + | |||
| + | 如果纵坐标全部相同，直接垂直投影即可。否则我们可以在使得某个投影与投影相切的时候取到最小宽度。对任意两个纵坐标不同的线段，我们可以算出两个投影相切的角度，从而得到一段不可行的区间。扫描线得出全局的可行投影角度区间。 | ||
| + | |||
| + | 而要在合理时间内得到取若干角度时投影的最大最小横坐标，可以用一个叫Convex Hull Trick的做法。设 $\theta$ 为投影线与 $x$ 轴正方向的夹角， $(x,y)$ 投影在横坐标 $x-\frac y{tan(\theta)}$ 的位置。以 $-\frac 1{tan(\theta)}$ 为自变量，则 $y_i$ 为斜率， $x_i$ 为截距。若干直线只会在一个凸包上取得最大值，我们先求出这个凸包，之后对于每个 $-\frac 1{tan(\theta_i)}$ 可以二分。最小值同理。 | ||
| + | |||
| + | **comments**：Convex Hull Trick可以适用在很多题上>< | ||
2020-2021/teams/wangzai_milk/weekly15.1597394267.txt.gz · 最后更改: 2020/08/14 16:37 由 wzx27
