2020杭电多校（第一场）
收获
- 对图可以进行分块：按照度数将点分为“大点”和“小点”——大点是度数 $>\sqrt n$ 的点，不超过 $\sqrt n$ 个；小点是度数 $\leqslant \sqrt n$ 的点。
1004 Distinct Sub-palindromes
- 当 $n=1$ 时，答案是 $26$，即所有字母；
- 当 $n=2$ 时，答案是 $26\times26$，即所有字母任意组合，不同回文子串数为 $2$;
- 当 $n=3$ 时，答案是 $26\times26\times26$，即所有字母任意组合，不同回文子串数为 $3$；
- 当 $n\geqslant4$ 时，答案是 $A_{26}^3=26\times25\times24$。首先考虑 $n=4$ 的情况，此时，我们可以用三个字母构造出不同回文子串数为 $3$ 的序列：$abca$，当固定了前三个位置填 $a,b,c$ 后，第四个位置只能填 $a$，因此是 $A_{26}^3$ 种；考虑 $n=5$，会发现在 $abca$ 的基础上只能填 $b$ 才能仍然保持不同回文子串数为 $3$；同理可推得，要使不同回文子串数保持为 $3$，只能 $abcabcabc\cdots$，因此 $n\geqslant4$ 时答案都是 $A_{26}^3$。
1 |
|
1005 Fibonacci Sum
$\textbf{Fibonacci}$ 数列通项公式：
$\sqrt 5$ 在模意义下就是 $x^2\equiv 5\pmod p$ 的解，二次剩余解之得到：$x=383008016$. 记 $A=\frac{1+\sqrt5}{2},\,B=\frac{1-\sqrt 5}{2},\,D=\frac{1}{\sqrt 5}$，那么 $F_n=D(A^n-B^n)$.
喜闻乐见的推式子时间：
枚举 $j$ 即可。
不过此题卡常，可以有两个常数优化：
- 快速幂的时候指数降幂；
- 从 $E_j$ 到 $E_{j+1}$ 可以 $O(1)$ 递推，不需要 $O(\lg 10^9)$ 重新计算。
1 |
|
1006 Finding a MEX
按照度数将点分为“大点”和“小点”——大点是度数 $>\sqrt n$ 的点，不超过 $\sqrt n$ 个；小点是度数 $\leqslant \sqrt n$ 的点。对于小点，每次询问直接暴力统计，复杂度 $O(\sqrt n)$；对于大点，我们维护一个值域树状数组，存储与它相邻的点的值，那么求 $\text{MEX}$ 可以在树状数组上二分。考虑如何维护：每次更改一个点的值时，就更新与之相邻的大点的树状数组，由于大点不超过 $\sqrt n$ 个，所以一次更改操作也是 $O(\sqrt n)$ 的，这样复杂度就得到了保证。
1 |
|
1009 Leading Robots
首先，那些 $a,p$ 均比某个机器人小的机器人可以扔掉不管了。然后，由于超过别人的机器人一定是 $a$ 更大的，所以我们可以按照 $a$ 升序排序，又已经剔掉了 $a,p$ 均比别人小的机器人，所以现在 $p$ 是降序的。考虑 $t=0$ 时领先的那个机器人（排序后的第一个元素），我们只需要往后找到谁第一个超过它，那么谁就领先，随后再往后找谁第一个超过现在领先的机器人……如此解决问题。
设排序后的机器人序列为：$\{x_1,x_2,\cdots,x_n\}$，则机器人 $x_3$ 先于 $x_2$ 超过 $x_1$ 的充要条件是：$1,3$ 相遇的时间小于 $1,2$ 相遇的时间，即 $\sqrt{\frac{2(p_1-p_3)}{a_3-a_1}}<\sqrt{\frac{2(p_1-p_2)}{a_2-a_1}}$，即 $\frac{p_1-p_3}{a_3-a_1}<\frac{p_1-p_2}{a_2-a_1}$，乘出来后用行列式表达就是：$\begin{vmatrix}1&1&1\\a_1&a_2&a_3\\p_1&p_2&p_3\end{vmatrix}>0$。注意到，假设点 $X_1(a_1,p_1),\,X_2(a_2,p_2),\,X_3(a_3,p_3)$，那么上述行列式就是 $\Delta X_1X_2X_3$ 的有向面积。换句话说，$x_3$ 比 $x_2$ 先超过 $x_1$ 的充要条件是 $\overrightarrow{X_1X_3}$ 在 $\overrightarrow{X_1X_2}$ 的左侧。那么，我们把这些点 $X_i(a_i,p_i)$ 画出来就会发现，答案其实就是求一个凸包（当然处理一下两个机器人重合的特殊情况）。
1 |
|
1012 Mow
这就是一个半平面交的经典题啊，类似 poj3384。
如果 $B\geqslant A$，就全部手动打扫；否则，就用机器打扫它能打扫的所有位置，即圆在这个多边形内部能覆盖的最大面积，然后手动打扫剩下的位置。把所有边往里面移动 $r$，半平面交得到圆心可以到达的区域，那么圆能覆盖的面积就是这个区域面积加上该区域各条边支出去的小矩形面积再加上一个整圆的面积。
只是这道题估计造了些 corner cases 的数据，尽管它保证了逆时针或顺时针输入一个凸多边形，但是直接用总会 WA。后来干脆先求凸包再做就 AC 了。
1 |
|