10-01杂题选讲 笔记

「CF1016E」

平面上有一个点光源, 以每秒一个单位的速度从 $(x_0, y)$ 沿直线走到 $(x_1, y)$, $y < 0$, $x$ 轴上有 $n$ 条线段会遮挡光线, $x$ 轴上方有 $q$ 个点, 你需要计算出每个点能够被光线直射的总时间.

$n, q \le 10^5$

Solution

求时间就是求总长度,且长度经过相似转以后一定是一段连续的空隙长度和

前缀和+二分处理,最后整体乘上相似比

「CF992E」

以前做过:「CF992E」 Nastya and King-Shamans - 线段树

「CF1019E」

有一棵 $n$ 个点的树, 每条边有两个参数 $a_i, b_i$ , 在时刻 $t$ 一条边的长度为 $a_{i}t + b_i$, 现在你需要求出在 $t = {0, 1, \cdots , m-1}$ 这些时刻树的直径是多少.

Solution

首先$a_i$一定单调不降,变化过程可以用斜率优化维护

考虑边分治,合并信息要用到闵可夫斯基和

闵可夫斯基和:

• 定义:给出两个点集A,B,求点集$C=\{a+b | a\in A, b\in B\}$的凸包
• 解法:求出A,B的凸包,找到A,B一组相加后在凸包上的点,向后按照相邻向量的极角序合并

「CF1028F」

给一个初始为空的整点集, 现在有 $n$ 次操作:

• $1\,\, x\,\, y$ 向点集中插入点 $(x, y)$.
• $2\,\, x\,\, y$ 从点集中删除点 $(x, y)$.
• $3\,\, x\,\, y$ 问至少需添加多少点满足图像关于 $(0, 0), (x, y)$ 连线对称.

$n \le 2 \times 10^5, 0 \le x, y \le 10^5$

Solution

互相对称的两点到原点距离显然相同,即在同一个圆的圆周上

因为点是整点,圆上整点很少,大约只有$O(\sqrt{n})$

维护每个圆上点的集合,每加入或删除一个点就计算这个点和其他点的对称中心并统计答案

复杂度约为$O(n\sqrt n \log n)$,但很难达到上界

「CF995E」

给出三个数 , 你可以对 进行若干次如下操作:

1. $u \leftarrow u+1~mod~ p$
2. $u \leftarrow u - 1~mod~p$
3. $u \leftarrow u^{p-2}~mod~p$

求一种不超过 $200$ 步的方案使得 $u$ 最终变成 $v$.

$0 \le u, v < p \le 10^9 + 9, p$ 是质数

Solution

双向bfs,因为图相当于随机,搜前$\sqrt p$个状态的值,再倒着搜$\sqrt p$个状态

根据生日悖论 $\sqrt p$次就能找到解(约$4*10^{-5}$的概率找不到)

「CF1051G

Link:「CF1051G」Distinctification - 线段树合并 + 并查集