2020-2021:teams:hotpot:nordiccollegiateprogrammingcontest2015
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:hotpot:nordiccollegiateprogrammingcontest2015 [2020/05/29 17:59] misakatao 更新 |
2020-2021:teams:hotpot:nordiccollegiateprogrammingcontest2015 [2020/05/29 18:03] (当前版本) misakatao 更新 |
||
|---|---|---|---|
| 行 150: | 行 150: | ||
| ===数据范围=== | ===数据范围=== | ||
| - | 点数圆数 $\le 100000$, 坐标 $0 \le xi,yi \le 10000$ ,圆的半径 $ r \le 100 $. | + | 点数 $\le 10^5$, 圆数 $\le 2\times 10^4$, 坐标 $0 \le xi,yi \le 10^4$ ,圆的半径 $ r \le 100 $. |
| ===题解=== | ===题解=== | ||
| - | 本体坐标的范围较大，我们不妨考虑从圆的半径这较小的一维来切入，采取对点每行用一个 $vector$ 来保存，之后对于每个圆，由于只涉及到最多 $200$ 行，对每一行取 $lower\_bound$ 和 $upper\_bound$ 来得到圆覆盖的位置，并采取在开始位置 $+1$， 在结束位置 $-1$ 的方式来标记覆盖的点（因此 $vector$ 里的变量应当是 $pair$）,最后遍历所有 $vector$ 来统计标记前缀和为 $0$ 的点的数量. | + | 本题坐标的范围较大，我们不妨考虑从圆的半径这较小的一维来切入，采取对点每行用一个 $vector$ 来保存，之后对于每个圆，由于只涉及到最多 $200$ 行，对每一行取 $lower\_bound$ 和 $upper\_bound$ 来得到圆覆盖的位置，并采取在开始位置 $+1$， 在结束位置 $-1$ 的方式来标记覆盖的点（因此 $vector$ 里的变量应当是 $pair$）,最后遍历所有 $vector$ 来统计标记前缀和为 $0$ 的点的数量. |
| =====Replay===== | =====Replay===== | ||
| - | 第一小时：tyx,lxh先想A，想出后lxh开始写A，gyp想I。tyx发现C题很多人过，于是A掉了C题，gyp没有相处I转而想E。tyx想出D后gyp优化了其算法并A掉了D题。lxhA错了几次后发现算法有瑕疵，更改后通过A。 | + | 第一小时：tyx,lxh先想A，想出后lxh开始写A，gyp想I。tyx发现C题很多人过，于是A掉了C题，gyp没有想出I转而想E。tyx想出D后gyp优化了其算法并A掉了D题。lxhA错了几次后发现算法有瑕疵，更改后通过A。 |
| 第二小时：gyp想出E但是不会实现，给lxh讲解后lxh开始写E并通过。tyx和gyp想出了G，给lxh讲解后lxh开始写G。tyx,gyp开始看F但没有看懂。 | 第二小时：gyp想出E但是不会实现，给lxh讲解后lxh开始写E并通过。tyx和gyp想出了G，给lxh讲解后lxh开始写G。tyx,gyp开始看F但没有看懂。 | ||
2020-2021/teams/hotpot/nordiccollegiateprogrammingcontest2015.1590746347.txt.gz · 最后更改: 2020/05/29 17:59 由 misakatao
