UOJ Logo vfleaking的博客

博客

UOJ Round #2 题解

2014-12-06 22:18:23 By vfleaking

猪猪侠再战括号序列

算法一

有一个超良心测试点满足 $n \leq 4$。注意到 $8$ 个元素的排列最多 $8!$ 个,所以直接使用 bfs 或者 dfs 搜索,每次对于一个序列枚举所有可能的翻转区间然后搜下去就好了。可以获得 10 分。

算法二

算法一显然太无脑了。考虑翻转操作其实用起来非常不爽,因为牵连的元素个数太多。如果题目允许你每次交换序列中的两个元素的位置,那么其实要好办很多。

于是我们重新设定目标,把目标序列变为一个显然是合法的括号序列,类似这样 “(((())))”。

我们从左往右依次处理原序列的前 $n$ 个括号,如果发现有一个右括号,我们就在右边随便找个左括号。由于左括号和右括号都是 $n$ 个,所以我们总能找到。然后我们把当前位置到那个左括号之间的序列翻转过来,这样当前位置就很开心的成了左括号。翻转过来之后当然中间的括号一团糟啦!不过我们是从左往右考虑,所以我们只用保证当前位置以左是与目标一致的。至于右边嘛,这是以后的事情了。

暴力在右边找左括号,然后再暴力翻转序列就能做到 $O(n^2)$ 了。可以获得 50 分。

算法三

对于算法二,用 splay 维护括号序列找左括号以及翻转就能做到 $O(n \log n)$ 了,可以获得 100 分。不过貌似脑洞太大,没人会这么做。

算法四

好吧其实自己手玩下就清楚了。我们不要“随便找个左括号”,我们就找当前位置右边的第一个左括号。那么当前位置到那个左括号之前肯定都是右括号,翻转过来也就只有两端变了。

好那么怎么找第一个左括号呢?显然第一个左括号的位置只可能越来越靠右,所以在上一次找到的左括号的位置基础上继续往右走就行了。

时间复杂度 $O(n)$,可以通过所有测试点获得 100 分。

另外我题目中说的是 $n$ 的范围哟,不是 $2n$ 的范围哟。爆数组的同学恭喜了,我还是放了你们一马给了 80 分。

跳蚤公路

算法一

题目中说超过 $10^{100}$ 叫发财,说白了就是从 $1$ 走到 $v$ 能歪到某个负权环上去瞎逛。

对于第 1 个测试点数据范围非常小。一个比较容易发现的事实是如果存在负权环,那么一定存在简单负权环(即不经过重复的结点)。于是我们用最暴力的方法搜索出图中所有的简单环,对每个简单环求出 $x$ 系数之和 $k$ 以及 $w$ 之和 $b$,列出它不是负权环的条件 $kx + b \geq 0$。

然后我们对于每个结点找出所有 $1$ 能走到且能走到$v$ 的简单环,把这些条件收集起来就能求出整数解个数了。可以通过 1 号测试点获得 $10$ 分。

要请各位注意的是 C++ 中 -10 / 3 = -3,是向零取整。因为这个被坑的同学恭喜了。

算法二

什么?你说你写不清楚找简单环?没关系,如果你裹得清楚这个算法的其余的部分还是可以得分的!看 6 号测试点,所有的简单环都是自环。做掉这个测试点就能获得 $10$ 分了。如果与算法一结合能获得 $20$ 分。

算法三

到这里我们发现基本思路就是找简单环列不等式。但是简单环个数肯定不会少,所以我们要减少需要考虑的简单环数目。

如前所述,对于每个简单环有个 $k$ 有个 $b$。仔细思考发现,如果 $k$ 相同,肯定是 $b$ 小的那个限制更紧。而 $b$ 就是忽略掉 $x$ 后的长度。

于是我们可以使用 Floyd。我们在 Floyd 的基础上多加一维记录 $k$,用 $f[v][u][k]$ 表示从 $v$ 出发到 $u$ 结束且 $x$ 前的系数为 $k$ 的最短路。这里的最短路是忽略了 $x$ 的。显然我们可以在 $O(n^5)$ 的时间内求出这个数组。然后 $f[v][v][k]$ 就是包含 $v$ 的且 $x$ 前的系数为 $k$ 的最短环长。

后面的部分与算法一相同。可以通过前 5 个测试点获得 50 分。结合算法二能获得 60 分。

算法四

下面来说正解了,这题其实有多种算法。

首先我们刚才玩了那么大一圈最后陷入的 Floyd 的不归路导致无法继续优化。让我们来想想,如果 $x$ 已知,你应该怎么做?

怎么判负环?

我们考虑传统的Bellman的大概思想,就是 $f[t][v]$ 表示至多走 $t$ 步,从 $1$ 号点出发到 $v$ 的最短距离。显然最短路一定是简单路,所以 $f[n - 1]$ 与 $f[n]$ 必定相等。但是如果有负环那么肯定不相等,所以利用这个性质就能检测负环。

好,但是这仅仅只是图中有负环而已,我们还得知道这个负环会牵连哪些结点。我们就找出 $f[n][v] < f[n - 1][v]$ 的所有 $v$ 然后看 $v$ 能走到哪些结点,那么这些结点都在负环上,其它结点则不在。

利用这个想法我们可以很简单地拓展为 $f[t][v][k]$,在原有基础上记录 $x$ 前的系数。然后我们拿出 $f[n - 1]$ 和 $f[n]$ 进行对比。解如下不等式:

\begin{equation} \min \{ kx + f[n][v][k] \} \geq \min \{ jx + f[n - 1][v][j] \} \end{equation}

把 $x$ 的范围解出来然后去更新自己能走到的结点的可行范围就好了。

时间复杂度 $O(n^4)$,可以通过所有测试点获得 100 分。

为了方便数学弱的小白我们多说几句,怎么解那个不等式呢?一定是对于所有的 $k$ 求下面这个范围的交集:

\begin{equation} kx + f[n][v][k] \geq \min \\{ jx + f[n - 1][v][j] \\} \end{equation}

对于每个固定的 $k$,一定是对于所有的 $j$ 求下面这个范围的并集:

\begin{equation} kx + f[n][v][k] \geq jx + f[n - 1][v][j] \end{equation}

于是现在只剩初中数学难度了。

其他算法

好吧我们来讲其他做法。其实仔细思考下 6 号测试点的深层含义,摆明了一副得DAG者得天下嘛。我们可以找到所有的强连通分量缩起来。要知道,只有强连通分量里有可能出现环,而且强连通分量里一旦出现负环,每个强连通分量内的点都可以走到负环再走回来。这意味着强连通分量内每个点的可行 $x$ 范围相同。于是我们可以把强连通分量分开进行考虑,求内部存在负环的范围,然后再考虑对其它强连通分量的影响。(什么你不会求强连通分量? Floyd 一遍求出 $h[v][u]$ 表示 $v$ 是否能走到 $u$,那么 $h[v][u]$ 和 $h[u][v]$ 同时为真时 $v$ 和 $u$ 在同一个强连通分量,这样就 $O(n^3)$ 求强连通分量了,对于此题来说足矣。)

而判断一个强连通分量内负环的取值范围,我们只用建一个超级源点向所有点连权值为 $0$ 的边,然后跑 Bellman-Ford 对于每个结点 $v$ 和每个 $x$ 前的系数 $k$ 求出最短距离 $d$,然后不存在负环的条件就是对于每个 $v$ 都满足 $kx + d \geq 0$。轻松解开就可以了。

(可能有人会问为何要建一个超级源,用强连通分量中任意一个点不行么?当然不行。比如某个点走到负环上需要走 $10^9$ 的距离,但是负环的权值仅为 $-1$。于是就得很久很久之后才会让这个点到自己的最短距离比 $0$ 小。感觉这算法八九不离十了,所以给的大约 80 分。)

UPD:(上面这个算法是错的……T_T……大家还是写算法四吧,质量有保障)

当然了,由于一个环永远只是贡献一个一次不等式,所以 $x$ 的解集肯定是个连续的区间或者空集。如果是连续的区间那么我们可不可以二分呢?或许你会脑洞大开不停地随机 $x$ 直到随机到一个 $x$ 满足不存在负环,然后通过二分求出左右边界。其实这个算法还是能骗不少分的。

树上GCD

算法一

枚举两个点 $u,v$,用 $O(\log n)$ 时间计算 LCA 和 gcd,并更新答案。复杂度 $O(n^2\log n)$。

当然你也可以枚举 LCA,然后往子树方向进行 bfs,由于计算 gcd 是 $O(\log n)$的,所以复杂度还是 $O(n^2\log n)$。

可以获得 10 分。

算法二

随机生成的树的树高为 $O(\log n)$。

枚举 $u$,计算以 $u$ 为 LCA 的所有点对的答案。计算时对 $u$ 的子树 DFS,统计出每个深度 $h$ 上的结点数量 $cnt[h]$。枚举深度 $h_1, h_2$,并将 $cnt[h_1]\cdot cnt[h_2]$ 累加到 $ans[\gcd(h_1,h_2)]$ 中。注意还需把同一个子树内的多余计算给减掉。这样,统计答案的复杂度是 $O(deg[u]\cdot \log^2 n)$,总和是$O(n \log^2 n)$。另外,每个点最多被DFS到 $O(\log n)$ 次,所以DFS的总复杂度是 $O(n\log n)$。

于是总复杂度 $O(n\log^2 n)$。可以获得 30 分。

算法三

我们可以把问题转化为,对于每个 $d$,求出 $\gcd(h_1,h_2)$ 是 $d$ 的倍数的点对的数量。然后用一个 $O(n\log n)$ 的容斥算出最终答案。

第4个数据点中,从根结点挂下来若干条链,长度分别为 $h_1,\cdots,h_k$。$u,v$ 属于同一条链的情况可以方便计算;$u,v$ 不在同一条链上时,LCA即为根结点。对于某个 $d$,第 $i$ 条链中高度为 $d$ 的倍数的点有 $\left\lfloor h_i/d\right \rfloor$ 个;我们要统计 $k$ 条链中选出两条来的乘积总和,可以利用恒等式 $(x_1+\cdots+x_k)^2=x_1^2+\cdots + x_k^2 +2\sum_{1\leq i < j\leq k}x_i x_j$ 求得。

复杂度 $O(n)$。可以获得 40 分。

算法四

考虑点分治,每次取出当前树的中心 $c$。考虑所有 $u \rightarrow LCA(u,v) \rightarrow v$ 的路径经过$c$的点对 $(u,v)$ 所产生的贡献,共有两种情况:

  1. $u,v$ 均在 $c$ 的子树内,此时 LCA 即为 $c$。和算法三类似,只是第 $i$ 条链中高度为 $d$ 的倍数的点的数量需要在处理出 $cnt$ 数组后花 $h_i/d$ 的时间统计,所以复杂度是$O(n \log n)$。
  2. $u$ 在 $c$ 的子树内,而 $v$ 不在。我们把当前树的根节点记为 $root$,$father[c]$ 到 $root$ 的路径为 $father[c]=a_1,a_2,\cdots,a_{k-1},a_k=root$。记 $c$ 下面的子树高度为 $H$,$a_i$ 旁边伸出的子树(即不包含 $a_{i-1}$ 的)的高度为 $h_i$。枚举 $a_i=LCA(u,v)$,那么 $v$ 位于 $a_i$ 旁边的子树中,然后我们仍然枚举 $d$,用 $h_i/d$ 的时间求出 $a_i$ 子树中高度为 $d$ 的倍数的结点数量;但我们还需要知道 $c$ 的子树中有多少点相对于 $a_i$ 的高度是 $d$ 的倍数,也就是说我们要在 $c$ 子树的 $cnt$ 数组中查询下标间隔为 $d$ 的子序列中的元素之和。注意到间隔为 $d$ 时,至多只有 $d$ 种这样的子序列,我们对重复查询进行记忆化。于是对于 $d<\sqrt{H}$,查询的复杂度不超过 $d\cdot H/d=H$,总共是 $\sqrt{H}\cdot H$;对于 $d>\sqrt{H}$,单次查询的复杂度为 $H/d<\sqrt{H}$。

所以一层分治的复杂度是 $O(n\sqrt{n})$的。根据主定理,总复杂度就是$O(n\sqrt{n})$。看起来有点卡常数?不,其实常数很小的。可以通过所有测试点获得 100 分。

见:http://uoj.ac/submission/2785

第二步如果使用比较暴力的方法还是可以通过 5 号测试点的。

其他算法

其实这题也可以用启发式合并做。我们还是可以用容斥转化为求 $d$ 的倍数的个数。如果 $v$ 和 $u$ 之间某个是另一个的祖先,那么显然可以 $O(n)$ 求出贡献到答案里。其它情况,对于 $d \leq \sqrt{n}$,我们可以用dp解决。$f[v][d]$ 表示以 $v$ 为根的子树中深度为 $d$ 的倍数的有多少个,然后在递推过程中更新答案。

对于 $d > \sqrt{n}$,我们每次对于每个点求出数组 $f[v][d]$,表示 $v$ 为根的子树中深度为 $d$ 的结点有多少个。通过启发式合并求这个数组。合并过程中,如果两个子树中最深深度都大于 $\sqrt{n}$,那么才有可能出现同为 $d$ 的倍数的情况。此时暴力对于每个 $d$ 以间距 $d$ 查询并更新答案。由于两个数组长度都大于 $\sqrt{n}$ 这种合并只会出现至多 $\sqrt{n}$ 次,所以总时间复杂度就是 $O(n \sqrt{n} \log n)$。虽然看上去比算法四更卡常数但是其实没有什么办法让它达到上界,于是也可以通过所有测试点获得 100 分了。

见:http://uoj.ac/submission/2786

评论

saffah
沙发
delayyy
沙发
Picks
赞!!!
wyfcyx
Sofa~~~
zhangzj
前排
thomount
我不会说我写的就是SPFA的,还是两次SPFA。。。搞的没有时间第三题(有时间也拿不到分。。。)。 第一题有趣,竟然是可行性问题而不是最优性问题出乎意料啊!有种提交答案的风采!(不知啥时给道提交答案题做做~~)
zangfenziang
还好最后30分钟没被忽悠过来掉rating。。。
Gromah
Orz
Trinkle
第一题不是有最优解吗。。。为什么弄成这样。。。
dmcyer
@
wyfcyx
@vfleaking 为什么spfa被搞出去?

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。