Loj练习

Published: by Creative Commons Licence

  • Tags:

LOJ136

题意

https://loj.ac/problem/136

题解

最小瓶颈路。做法比较简单,我们维护一个图,初始时没有边加入。之后按边的权重不断将边加入,如果因为边的加入导致两个顶点连通,那么这两个顶点在图中的最小瓶颈路的最大权边一定为该边。

这里可以将每个请求关联到两个端点,之后用并查集维护连通性。如果要合并两个连通块,需要将请求合并,合并之前还需要检查请求。这里可以利用启发式合并的思路,保证合并和检查仅发生$q\log_2q$次。总的时间复杂度是$O(m\log_2m+q\log_2q+n)$,空间复杂度为$O(n+m+q\log_2q)$。

LOJ2542

题意

https://loj.ac/problem/2542

题解

对于一次实验,记随机变量$X_i$表示顶点i第一次被访问时间。记 。那么对于任意$X$的子集$S$,要计算全部顶点都被访问至少一次的时间,应该是: 利用min-max容斥,化作如下形式:

之后利用期望的线性性质得到:

其中 是集合中的顶点第一次被访问的时间。

之后假设我们预先计算出了对于所有$X$的子集的首次访问时间期望,之后对于询问总共时间不会超过: 。现在讨论如何预先计算所有子集的首次访问时间,我们可以利用可以用高斯消元在$O(n^3)$时间复杂度内计算一个子集的首次访问时间,但是这样会超时。我们需要利用树提供的拓扑无环性质,利用一次DFS直接得出期望$O(n\log_2n)$,其中$\log$的存在是因为需要计算逆元。

这样总的时间复杂度为: 。马马虎虎,可以过。

LOJ2169

题目

https://loj.ac/problem/2169

题解

首先更新事件有环,我们将更新事件拆分成两个处理。因此现在只剩下一般的线段树操作了。

我们使用整体二分技术,要应用l~r之间的事件,我们先算出中点m,之后将l~m之间的事件应用在线段树上。之后我们查找每个国家的获得的陨石总数,如果超过就标记,否则不标记。

我们将不标记的国家,对其尝试应用m+1~r之间事件。之后我们撤销之前应用l~m之间事件带来的修改,之后对标记的国家,尝试应用l~m之间的事件。

如果l与r相等,就记录结果。

下面我们证明时间复杂度。复杂度分为两部分,一部分是判断国家是否得到了足够的陨石,我们知道每个区域在每个递归层次都只会统计一次,因此统计区域的总的时间复杂度为$O(m\log_2m\log_2k)$。接下来就是递归的时间复杂度了,假设$T(a,b)$表示处理a个国家和b个事件花费的时间,可以推出:

总的时间复杂度为$O((m+k)\log_2m\log_2k)$。