元旦三侠的游戏

from keavil

算法一

对于第一个测试点，我们有 $ n = 2 $ 。那么必定有 $ a = 2 $， $ b = 1 $。

显然，无论我们增加 $ a $ 或者是 $ b $，都会违背 $ a^b \leq n $ 的要求。那么这种情况必定是先手必败的。因此直接输出No就能获得$10$分。

算法二

这是一个博弈问题。我们考虑用 $ f_{a,b} $来表示当前的游戏状态。$ f_{a,b} $为 $ 1 $ 表示当前的 $ (a,b) $ 是先手必胜状态，否则表示当前的 $ (a,b) $ 为先手必败状态。

然后我们就可以用记忆化搜索来转移了。注意到 $ a $ 显然不能超过 $ n $，而 $ b $ 不能超过 $ \log n $ 。那么就可以在 $O(n \log n)$ 的时间内处理出全部的状态了。

算法三

注意到，对于一个 $ b $ ，$ a $ 必定不能超过 $ \sqrt[b]{n} $ 。那么我们实际上状态数只有： $ \sum_{b=1}^{\log n} \sqrt[b]{n} $。

而如果一个状态 $ (a,b) $ 满足 $ a>\sqrt[b+1]{n}$ ，那么显然不能再增加$b$了，而我们容易算出 $ \lfloor \sqrt[b]{n} \rfloor$ 这个值，那么我们根据它与 $ a $ 的差的奇偶性就可以直接得出当前状态。

那么，我们的状态数就只有： $ \sum_{b=2}^{\log n} \sqrt[b]{n} $。这个值显然只有 $ O( \sqrt{n}\log n) $ （实际上远小于这个值）

复杂度： $ O(\sqrt{n}\log n) $

元旦激光炮

from vfleaking

元旦快乐！送给大家一道交互式的水题当元旦礼物！

算法一

我们可以用 $n_a + n_b + n_c$ 次询问把整个数组给询问出来，然后排个序求出第 $k$ 小。

可以通过 1 号测试点获得 10 分。

算法二

显然可以二分答案嘛！二分第 $k$ 小的值，然后在三个数组里二分统计小于等于这个值的有多少个。

在长度为 $n$ 的数组里二分需要调用 $\lceil \log_2 n \rceil$ 次，而答案的范围是 $10^9$ 需要二分 $30$ 次，所以总次数最坏是 $30 \times 17 \times 3 = 1530$ 次。显然这离 $2000$ 次调用的限制差得远。

可以拿到每个测试点的 $6$ 分获得 60 分。

如果你特判掉了 1 号测试点使用暴力，那么可以拿到 1 号测试点的 $10$ 分获得 64 分。

算法三

注意到有三个超良心的测试点，其中一个数组是空的，只有两个数组。我们可以假想这两个数组的长度为 $k$，然后这里有一个非常有趣的给两个数组取中位数的算法可以解决此问题。

现在手上有两个数组 $a, b$ 长度均为 $n$ 且 $n$ 为偶数。我们记 $i = \lfloor n / 2 \rfloor$，$j = \lceil n / 2 \rceil$。（这里假设数组下标从 $1$ 开始）

我们比较一下 $a_i$ 和 $b_j$ 的大小。如果 $a_i < b_j$，那么：

• $a_1$ 到 $a_i$ 均比 $b_j$ 到 $b_n$ 要小，这说明 $a$ 中有 $n - i$ 个元素，$b$ 中有 $n - j + 1$ 个元素比他们大，总共 $n + 1$ 个元素比他们大。
• 另一方面，这说明 $a$ 中有 $i$ 个元素，$b$ 中有 $j$ 个元素比 $b_{j + 1}$ 到 $b_n$ 要小，总共 $n$ 个元素比他们小。

所以，我们可以去掉 $a$ 的前 $i$ 个元素和 $b$ 的后 $i$ 个元素而中位数不变，然后递归下去就行了。对于$a_i \geq b_j$ 的情况可以类比。最后递归到 $n = 1$ 时，暴力下就行了。

这样只用 $2 \times (\lceil \log_2 n \rceil + 1)$ 次调用即可解决问题。对于 $k \leq 2 \times 10^5$，调用次数只有 $2 \times 18 = 36$ 次。

结合算法二可以获得 72 分。如果再结合算法一可以获得 76 分。

算法四

当我知道有个算法三的时候我惊呆了……其实我想表演的是另一个神奇的算法。

首先我们把数组的长度扔进垃圾桶！我们想象数组是无穷长的，即在原数组后面补无穷个无穷大。

然后我们取 $l = \lfloor k / 3 \rfloor$。我们来比较 $a_l, b_l, c_l$。我们假设 $a_l$ 是这三个数中最小的。

那么我们看看最多有多少个数比 $a_l$ 小，为了说话方便我们无视两个数相等的情况。$a$ 数组中肯定是 $l - 1$ 个，$b$ 数组中由于 $b_l$ 比 $a_l$ 大，所以最坏情况是 $b_1$ 到 $b_{l - 1}$ 都比 $a_l$ 小，$c$ 数组也是一样。于是最多 $3l - 3$ 个比 $a_l$ 小。所以 $a_l$ 的排名至多是 $3l - 2 < k$。

于是我们可以甩掉 $a$ 数组的前 $l$ 个元素然后 $k = k - l$，递归下去。注意到每次 $k$ 的大小都减少了三分之一，到最后 $k \leq 2$ 时我们可以用暴力 $6$ 次调用解决问题。总调用次数满足递推式 $T(n) = T(n - \lfloor n / 3 \rfloor) + 3$，所以会调用次数不超过 $\lceil \log_{3/2} k \rceil + 4$。

对于 $k \leq 3 \times 10^5$，调用次数只有 $96$，足以解决此题。

可以通过所有测试点获得 $100$ 分。

考试时有一些人想到了这个算法，但是你们基本萌萌哒把边界写残了？只有感动中国人物 liuzurang AC啦～我觉得我的样例给得不弱啊……反正我是用同一个数据生成器生成的……

追击圣诞老人

from wangyisong1996

题目大意

给一棵树，每个点有权值$w_i$ ($w_i > 0$)。

对于第$i$个点给定三个参数$a_i, b_i, c_i$， 第$i$个点只能走向$a_i, b_i, c_i$这三个点在原树中两两之间的路径上的点。

一个长度为$l$的序列$s_1, s_2, ..., s_l$的权值定义为$\sum_{i=1}^l w_{s_i}$， 这个序列中对于任意$1 \le i < l$都要满足$s_i$能走向$s_{i+1}$。

求权值前$k$小的序列的权值。

算法一

暴力枚举所有长度不超过$k$的序列，复杂度$O(n ^ k)$，能通过1, 2号测试点。

算法二

定义$W(A)$表示序列$A$的权值。

我们把所有序列建成一张图，每一个序列向它最后加一个点形成的序列连边。 那么这张图满足堆性质：如果$u$连向$v$，则$W(u) < W(v)$。

用一个优先队列维护已经扩展到的点（序列）。

一开始将所有入度为0的点（长度为1的序列）放入优先队列里， 然后进行$k$次操作，每次操作是弹出优先队列中权值最小的序列（记为$A$）， 然后将$A$连向的所有序列放入优先队列里。 第$i$次操作弹出的序列就是第$i$小的答案。

注意这张图不需要完全建出，只要在访问到$x$这个点时将$x$的出边建出即可。

由于一个点会连向$O(n)$个点， 该算法的复杂度为$O(nk \log nk)$， 能通过1 $\sim$ 4号测试点。

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

算法三

对于上一个算法中图上的每个点，将它的所有出边按权值从小到大排序， 那么就可以用左儿子右兄弟的方法将度数减少为2，这样优先队列中只会被放入$O(n + k)$个点。

由于一个序列最后能加的点只跟这个序列的最后一个点有关， 所以只要将每个点能走到的所有点按权值排序即可。

时间复杂度$O(n^2 + k \log (n+k))$，空间复杂度$O(n^2+k)$。 能通过1 $\sim$ 8号测试点。

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

算法四

上一个算法的瓶颈是将每个点能走到的点按权值排序。

我们可以将每个点能走到的点按权值建一个小根堆， 优先队列中记录这些信息：(权值, 最后一个点, 指向一个堆的指针)。

弹出一个序列$(W, x, H)$时， 只要将$(W + w_{H.l.id} - w_x, H.l.id, H.l)$、$(W + w_{H.r.id} - w_x, H.r.id, H.r)$ 和$(W+w_{Heap_x .id}, Heap_x .id, Heap_x)$放入优先队列即可。

其中$H.id$表示堆$H$中权值最小的点的编号，$Heap_i$表示一个包含点$i$能走到的所有点的堆。

现在问题转化成，对每个$i$求出$Heap_i$。

我们用可并堆（如左偏树）预处理第$i$个点到根的路径上前$2 ^ j$个点的堆， 然后每个点能走到的点可以拆成三条链，于是可以用倍增得到。

时间复杂度$O(n \log ^ 2 n + k \log (n+k))$，空间复杂度$O(n \log ^ 2 n + k)$。 能通过第1 $\sim$ 12号测试点。

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

算法五

考虑算法三， 如果我们能在$O(f(n))$的时间内求得第$i$个点能走到的点中，权值第$j$大的点， 就能在$O(g(n) + k \log (n+k) + k \cdot f(n))$的时间内解决原问题，其中$O(g(n))$的时间用来预处理。

算法三中$f(n) = O(1)$, $g(n) = O(n^2)$。

我们用主席树（可持久化线段树前缀和）来维护$1 \sim i$路径上点的权值，就可以使$f(n) = O(\log n)$, $g(n) = O(n \log n)$。

于是总的时间复杂度为$O(n \log n + k \log (n+k))$，空间复杂度为$O(n \log n + k)$。

能通过1 $\sim$ 16号测试点。 对于$n = 5 \times 10^5$的数据会MLE。

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

算法六

考虑算法四， 对于一条链$(a, b)$，将这条链上的点建成一个堆$H$， 那么$H.id$就是这条链上权值最小的点。 我们将这条链从这个点处断开， 那么剩下的两段分别对应于$H.l$和$H.r$。

我们用一个二元组$(a, b)$表示$(a, b)$这条链的堆， 就不用预处理出算法四中的$Heap_i$了。

复杂度为$O(n \log n + k \log (n + k) + k \cdot f(n))$， 其中$f(n)$为求出一条链上权值最小的点的时间复杂度。

用 倍增 or LCT or 树链剖分（要预处理每条重链的前缀$min$） 都可以做到$f(n) = O(\log n)$。

那么时间复杂度就是$O(n \log n + k \log (n + k))$，跟算法五一样。

如果你用倍增，空间复杂度是$O(n \log n + k)$，很有可能会MLE。

如果你用LCT，空间复杂度是$O(n + k)$的，但是常数太大，很有可能会TLE。

用树链剖分就可以通过所有测试点了。

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