国家集训队 WF2015 题解

p878567 · 2020-11-13 09:31:54 · 个人记录

CF地址

此题并非独立想出。

首先判掉不相交的情况，然后三分。

可以发现凸包的交的顶点是原凸包边的交点或落在另一凸包边上或内部的顶点，可以求出顶点集再排序。

我们把所有的串按串长排序，并计算相邻两项是否能直接拼接。

如果最多只有一对不能，那么就求出了一组解，直接输出。

否则考虑最后两对不能拼接的位置，设 s_a,s_b 与 s_c,s_d 不能拼接，其中 a+1=b\leq c=d-1。

现在考虑 s_a,s_d 能否拼接。

如果可以，那么直接连接。

否则考虑 [b,c] 中的每一个 x，并计算 s_x 与 s_a,s_d 能否拼接。

都能拼接是不可能的；若都不能，这说明无解。

我们根据 s_x 与哪一个能拼接来确定将其放入哪一部分，显然不同的 x 间总是能够拼接的。

重复操作使得只剩两段，复杂度 O(n^2)。

此题并非独立想出。

令 v(k) 表示询问 k 次后若速度在 v_1 与 v(k) 间不能确定的最小值（我们应当保证大于 v(k) 的都能确定，否则一定不优），n(k) 表示 k 次询问总计将其分为多少段（我们暂不需要关心具体是如何分的）。

考虑第 k+1 次询问，显然询问速度必须小于 \frac{l}{s(k+1)}，这样大于 \frac{l}{s(k+1)}+t 的值必须可以回答，其中大于 v(k) 的已经可以回答，介于这两者之间的就需要通过排列分段位置以确保可以回答，最优时每段长都是 t，这些段内的速度都可以回答。

对余下的段，我们可以把每一段都分成两段，这样可以计算 v(k+1) 与 n(k+1)，当平均段长不超过 t 时即结束。

设第 k 个竖井的横坐标为 x_k, x_0=0,x_{n+1}=w。

考虑在固定除 x_k 外的所有竖井的情况下改变 x_k，并计算答案。

通过复杂的计算发现 x_k=\frac{w^2-h^2}{2w^2}(x_{k-1}+x_{k+1}) 时有最小值。

解这个方程组即可，可以证明解满足单调性。

可以发现，面积为 S 时的答案为 \sum_{i=0}^nd(i)d(n-i)，其中 d(i) 为 i 的约数个数，d(0)=0。

\texttt {FFT}$ 即可，由于答案不大，可以用 $\bmod 998244353$ 的 $\texttt {NTT}

我们为每一条边，计算有多少条边使得他们或者都在同一个环里，或者都不在。

这就是计算删去它后的割边数量，其中这个割边是只删去后增加连通块数量的边。

最终答案为上面得到所有结果的 \gcd。（请自行证明这是最大值。）

直接哈夫曼树。

不同的概率最多只有 \binom{n+3}{3} 种，其中合并两个相同的数最多发生 \log_24^n=2n 次（同时产生这么多的新数），合并两个相同的数总会导致不同的数的数量减 1，故复杂度为 O(n^4\log n)。

按题意模拟即可。

对 \texttt {MOVE} 操作，可以先反向扫描线确定每个矩形最多能移多少格，然后正向扫描线模拟移动过程。