2020-2021:teams:i_dont_know_png:neerc2015
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 | |||
|
2020-2021:teams:i_dont_know_png:neerc2015 [2020/05/17 12:14] potassium [题目描述] |
2020-2021:teams:i_dont_know_png:neerc2015 [2020/05/22 20:12] (当前版本) potassium fix typos |
||
|---|---|---|---|
| 行 33: | 行 33: | ||
| $$p\times 10=(p<<3)+(p<<1)$$ | $$p\times 10=(p<<3)+(p<<1)$$ | ||
| - | 数归， $(10^k)_2$ 后 $k$ 位都为 $0$ 。按位从低到高枚举填 $0$ 或者 $1$ ，填数不影响前 $k-1$ 个位置的二进制表示，仅需要判断填数后第 $k$ 位的十进制和二进制相等与否即可。需要用大数，复杂度$\mathcal{O}(nl)$。 | + | 数归， $(10^k)_2$ 后 $k$ 位都为 $0$ 。按位从低到高枚举填 $0$ 或者 $1$ ，填数不影响前 $k-1$ 个位置的二进制表示，仅需要判断填数后第 $k$ 位的十进制和二进制相等与否即可。需要用大数，复杂度$O(nl)$。 |
| 行 76: | 行 76: | ||
| 分治，每次将多边形尽可能均匀地分成 $A,B$ 两部分，询问中两点分别在两边的直接 $BFS$ 处理出距离，在同一边的递归处理。 | 分治，每次将多边形尽可能均匀地分成 $A,B$ 两部分，询问中两点分别在两边的直接 $BFS$ 处理出距离，在同一边的递归处理。 | ||
| - | 注意需要在保证复杂度的情况下，每次的修改不能影响孩子或右半部分。复杂度 $\mathcal{O}(n\log n)$。 | + | 注意需要在保证复杂度的情况下，每次的修改不能影响孩子或右半部分。复杂度 $O(n\log n)$。 |
| 行 193: | 行 193: | ||
| 假设当前最高高度为 $x$，位置在第 $i$ 个，则需要加方块的左端点 $l$ 应当满足 $h_l \geq x - (i - l)$，即 $h_l - l \geq x - i$，在单调栈上二分可以找到最近的左端点；右端点同理可求。 | 假设当前最高高度为 $x$，位置在第 $i$ 个，则需要加方块的左端点 $l$ 应当满足 $h_l \geq x - (i - l)$，即 $h_l - l \geq x - i$，在单调栈上二分可以找到最近的左端点；右端点同理可求。 | ||
| - | 注意到能额外添加的高度不会超过 $n$，因此二分的上界与 $\max \{h_i\}$ 同级，总时间复杂度 $\mathcal{O}(n \log n \log \max \{h_i\})$。 | + | 注意到能额外添加的高度不会超过 $n$，因此二分的上界与 $\max \{h_i\}$ 同级，总时间复杂度 $O(n \log n \log \max \{h_i\})$。 |
2020-2021/teams/i_dont_know_png/neerc2015.1589688863.txt.gz · 最后更改: 2020/05/17 12:14 由 potassium
