2020-2021:teams:i_dont_know_png:neerc2015
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:i_dont_know_png:neerc2015 [2020/05/16 20:53] nikkukun add solutions |
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)$。 |
| 行 68: | 行 68: | ||
| ==== 题目描述 ==== | ==== 题目描述 ==== | ||
| - | 给一个 $n$ 个点的多边形的三角剖分，边长均为 1 。 $q$ 次询问，每次询问两点间距离。 $n,q\le 10000$。 | + | 给一个 $n$ 个点的多边形的三角剖分，边长均为 $1$ 。 $q$ 次询问，每次询问两点间距离。 $n,q\le 10000$。 |
| ==== 解题思路 ==== | ==== 解题思路 ==== | ||
| 行 76: | 行 76: | ||
| 分治，每次将多边形尽可能均匀地分成 $A,B$ 两部分，询问中两点分别在两边的直接 $BFS$ 处理出距离，在同一边的递归处理。 | 分治，每次将多边形尽可能均匀地分成 $A,B$ 两部分，询问中两点分别在两边的直接 $BFS$ 处理出距离，在同一边的递归处理。 | ||
| - | 注意需要在保证复杂度的情况下，每次的修改不能影响孩子或右半部分。复杂度 $\mathcal{O}(n\log n)$。 | + | 注意需要在保证复杂度的情况下，每次的修改不能影响孩子或右半部分。复杂度 $O(n\log n)$。 |
| 行 100: | 行 100: | ||
| 有个蛤蟆想要从左岸跳到右岸，其中有一些石头 $(n\le 1000)$ ，他还拿着一块石头可以放下来。每次只能跳到石头上，手里的石头只能用一次。问从左岸跳到右岸最长的一步最短需要多长。 | 有个蛤蟆想要从左岸跳到右岸，其中有一些石头 $(n\le 1000)$ ，他还拿着一块石头可以放下来。每次只能跳到石头上，手里的石头只能用一次。问从左岸跳到右岸最长的一步最短需要多长。 | ||
| + | {{.:potassium:neerc15_pic_1.jpg?500}} | ||
| ==== 解题思路 ==== | ==== 解题思路 ==== | ||
| 行 192: | 行 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.1589633582.txt.gz · 最后更改: 2020/05/16 20:53 由 nikkukun
