NFLSPC #8 重现赛部分题解

· · 算法·理论

这里的题面顺序可能与真实顺序不一致。

轨道交通

显然能够发现，如果两条线段相交，那么它们在坐标轴上的投影一定相交。

因此先把所有的点放在坐标轴的投影上，这个问题就变成了一维的。

做法一

排序后选择前 n+1 个点，找出其中颜色相同的一对，连接这对点并把前面不同颜色的删除，这样对于剩下 n-1 种颜色，至少有 n 个点，转化为等价子问题。

依次解决即可。

时间复杂度 O(n^2\log n) 。

做法二

排序后依次扫描每一个点，记录下上一个被选的点的 x 坐标，要求新选的点坐标大于上一个点。

时间复杂度 O(n) 。

NFLSPC

有 3 个量未知：数据组数 T、第一张图的点数 n_1 和第一张图的边数 m_1 。

可以发现， T 没啥用。而且如果一组 n,m 可以让数据合法，必然要求接下来的 m 行的 u,v\leq n。

考虑枚举 m_1 ，因为图不一定要联通，因此求出接下来的 m_1 行的 u,v 的最大值 k，则：

k\leq n_1 \leq 2 × 10^5

即 n_1 有 2 × 10^5 - k + 1 种取值。

此后还要判断之后的每一个图是否合法，是否能够用完所有的输入。

直接判断是 O(n^2) 的，预计得分 10pts 。

然后考虑优化，设 ok_i 表示从第 i 行开始到结尾中，是否每一个图都合法。有：

ok_i = \max[i + 1, i + y_i] \leq x_i \land ok_{i + y_i + 1}

之后时间复杂度瓶颈在于静态区间 \max ，可以使用倍增 \text{RMQ} 等方式解决。

使用倍增的最低时间复杂度为 O(line) 。

如何区分北京东路和北京东路

容易发现每次爆炸后炸弹的威力总的期望值 S 不变。

设 E_{k,i} 为第 k 次爆炸后城市 i 的炸弹的威力的期望值。有：

E_{k,i} = \frac{1}{n} × 0 + \sum_{j=1}^{n,j \neq i}\frac{1}{n} × (E_{k-1,i} + \frac{E_{k-1,j}}{n-1})

考虑化简这个式子：

\begin{aligned} E_{k,i} &= \frac{1}{n} × 0 + \sum_{j=1}^{n,j \neq i}\frac{1}{n} × (E_{k-1,i} + \frac{E_{k-1,j}}{n-1}) \\ &= E_{k-1,i} × \frac{n-1}{n} + \sum_{j=1}^{n,j \neq i}\frac{E_{k-1,j}}{n×(n-1)} \\ &= E_{k-1,i} × \frac{n-1}{n} + \frac{S-E_{k-1,i}}{n×(n-1)} \\ &= E_{k-1,i} × (\frac{n-1}{n} - \frac{1}{n×(n-1)}) + \frac{S}{n×(n-1)} \\ &= E_{k-1,i} × \frac{n-2}{n-1} + \frac{S}{n×(n-1)} \\ \end{aligned}

然后我们就可以 O(nk) 转移了。

考虑写出通项公式。

通过找规律和等比数列求和公式得到：

E_{i,k} = \frac{S}{n} + \left(a_i - \frac{S}{n}\right)\left(\frac{n-2}{n-1}\right)^k

时间复杂度 O(n) 。

SFLSPC

是建国以后在周恩来总理的直接关怀下首批成立的 7 所外国语学校之一（同时成立的另外六所学校分别是长春外国语学校、武汉外国语学校、天津外国语学院附属外国语学校、南京外国语学校、四川外语学院附属外国语学校（通称重庆外国语学校）和广外附设外语学校）。

——题面

通过阅读发现 SFLS 和 NFLS 在同一年建立，看图 NFLS 图标可知答案为 1963 。