夏晓光(loveJY)的博客

题目质量真不错

A

计算几何题

对于四个象限都有点的情况

将起点设置为原点,极角排序

终点要最后一个走啊,所以我们把终点旋转到极角最大处就是180度,然后从-180度,第二关键字按照y坐标排序,y轴负半轴优先走y坐标小的即可

这个旋转可以用复数的运算法则,满足模长相乘辐角相加,所以乘上$(cos(x),sin(x))(x是需要旋转的角度)$,进行坐标变换即可

然后如果四个象限并非都有点,此时起点在凸包上

叉法很简单,因为我们会走一个急转弯,没有绕过180度时,我们在经过坐标轴的时候会自闭掉!

所以对于起点在凸包上的时候,我们每次尽量向和当前点斜率最大的走,如果斜率最大的点是n号点就向斜率最小的点走即可

这样每次我们都在凸壳上,就一定能保证最后留给n

B

对于$m\leq 3000$

我们发现关键点只有$O(2m+k)$个,(标签代表的点),这些点拿出来跑01最短路即可

而类似的可以推广这个做法

我们对于每个标签丛用虚点跑一个最短路,其中虚点向所有有这个标签的点连边1

然后我们发现得到的最短路DAG信息可以计算这个标签丛对应点对的答案

具体的,我们标签丛内每个点到其余点最短路要么是跑出来的信息,要么是跑出来的信息减1,减1当且仅当这个点在最短路DAG上能够到达结尾点

于是我们考虑对于这样的关键点分块,每64个分一块,然后跑拓扑图的可达性统计,用ull去存

然后枚举终点对于一个终点能到达的关键点,他们对于答案的贡献是最短路-1,否则就是最短路

复杂度就是$O(k(n+m)+\frac{n(n+m)}{64})$,因为是5e4所以很能过

C

交互题就先咕着了