MOCK PTS 20220107 日志

……

简略题解

A – 小矩阵

高维莫队。如果认为 $n,m$ 同级，复杂度 $\newcommand\bigO[1]{\operatorname{O}\left(#1\right)}\bigO{n^4\sqrt[4]{q}+nq^{\frac{3}{4}}}$，实际上由于 $q$ 远小于理论块间移动次数，不能卡满，实测耗时比上式低一个数量级。

蒲韦坤说将询问 std::shuffle () 一下移动指针即可通过，速度与莫队相当。

B – 多边形

$\text{40 pts}$ – 无禁用交点

我们发现，除开可能存在的直线 $x=x_0$，对于一条固定的直线，其与其他所有直线的交点中，能够出现在凸包上的只可能有两个：横坐标最大/最小的两个（纵坐标最大最小等价）。

考虑求取直线 $l_i:y=k_ix+b_i$ 的上述两个点。观察到与直线 $l_j:y=k_jx+b_j$ 的交点横坐标为 $\frac{b_i-b_j}{k_j-k_i}$，如果我们设点 $A_i(k_i,b_i)$，这其实就是求取过 $A_i,A_j$ 的直线的斜率的相反数。于是我们将 $n$ 条（或者 $n-1$ 条）直线转化为相应的点，求出过它们中每一个的直线的最大/最小斜率（在左上/左下/右上/右下方，分别执行类似斜率优化般逐个将点插入凸包的算法）即可。

如果存在直线 $x=x_0$，我们暴力 $\bigO{n}$ 求它与其他直线的交。最后将得到的 $\bigO{n}$ 个点求二维凸包即是答案。

正解

由于禁用的交点极少（$k\leq 50$ 个），故而我们将受到波及的至多 $2k$ 条不同直线全部重新暴力求取与别的直线的交点，再取合法的最大/最小横坐标。复杂度 $\bigO{kn+n\log n}$。

C – 大乱炖

没人讲也没人会，猜测与多项式与生成函数相关。