2024上海省赛VP游记&部分简要题解

· · 个人记录

队友是：@•́へ•́╬，@jason_sun。

三人三机。

开场我迟到了一下然后每个人都找了个签子签了，过了 AJE。

然后每个人又找了个签子签了，过了 MKL。

然后我觉得我会了 C 于是开写，想不到结论假了于是换了个结论继续写（伏笔）

队友又开始开桂了，过了 F 和 G，这个时候其实我的题已经在调了。

jason_sun 还在开桂，过了 D，我的题还在调想不到吧。

比赛结束了，我的题还在调想不到吧，gza 这把最大恶人了。

感觉写的确实太憋屈了一点，首先是没注意到 C 直接按照旋转卡壳去做是对的，以及没有很好的时间分配导致 B 开场秒的 toptree 没时间去写。

写一下部分没过的题的题解吧：

B

拆位，转化为权值只有 01。

建出静态 toptree，让簇仅包含下界点，然后维护簇内奇偶路径数和两个界点到簇内点的奇偶路径数即可。

全是板子没什么好说的。

C

三点确定一个圆，所以我们分三种情况：圆单独包含一个点，圆上有两个点，圆上有至少三个点。

由于三点确定一个圆，所以我们只需要 O(n^3) 枚举圆，把剩下的点用旋转卡壳求一个最小正方形覆盖即可。

当然我场上用了一个假结论：正方形和坐标轴所成的角度在 0 \sim 90 度时，最小正方形面积是单峰的。

但是好像数据有点弱，我赛后分 0 \sim 45 和 45 \sim 90 两段三分就过了。

I

求个原根 $g$，我们要对于所有 $t$ 求出 $a^p \equiv t \pmod P$ 的方案数，令 $g^A=a,g^T=t$，那么这个式子就是 $Ax \equiv T \pmod{\varphi(p)}$。 尝试枚举 $x \bmod \varphi(p)$ 的值，$A$ 的值变化可以看做 $x$ 在一个环上走路，暴力走肯定是不行的。稍微优化一下让环上所有点一起走就行了。细节就看 jly 代码吧。