猜数

算法一

直接暴力枚举所有可能的 $a, b$ 然后判定。可以得30分。

算法二

由于 $a, b$ 都是 $g$ 的倍数，而 $ab = gl = n$，所以当然 $l$ 也是 $g$ 的倍数。

既然如此，我们可以暴力枚举所有 $l / g = st$ 的拆分，然后 $a = gs, b = gt$。

于是暴力枚举所有 $l / g$ 的约数，是 $O(\sqrt{l / g})$ 的。可以得60分。

算法三

其实根本不用枚举约数。

考虑最小值。只看 $n = ab$ 这个限制，根据均值不等式，最小值显然在 $\\{a = \sqrt{n}, b = \sqrt{n}\\}$ 时取到。而根据题目条件，这显然是一组合法解。所以最小值就是 $2 \sqrt{gl}$。

考虑最大值。只看 $n = ab, a \geq g$ 这两个限制。显然最大值在 $\\{a = g, b = l\\}$ 时取到。而根据题目条件，这显然是一组合法解。所以最大值就是 $g + l$。

这样好好写就能获得 $100$ 分。

精度问题

有人可能会写：

ans_min = (long long)sqrt((double)g * l);

这样会被卡精度，因为double大概只有15位10进制有效数字。只能得到60分。

解决方法是：

ans_min = (long long)sqrt(l / g) * g;

当然有人可能直接long double保平安了……

跳蚤OS

算法一

对于前3个点，数据范围非常非常小，打最裸的暴力就能获得30分。

算法二

对于第4到6个点，所有文件夹都位于根目录下。

所以其实就是个简单的字符串查找问题。可以使用哈希或者Trie或者map得到30分。

结合算法一就能获得60分。

算法三

尽管你可能会用map去优化裸暴力，但是很不幸，是不能得到更多的分数的。

我们来说算法三。我们可以用一个Trie树存下所有的文件夹路径字符串。（把根目录的路径字符串当作空字符串）

然后，对于每个结点，我们增加一个 $go$ 指针。当 $go$ 不为空时表示这个位置是个快捷方式并指向真实路径字符串在 Trie 中对应的结点。

于是我们可以读入字符串，然后顺着Trie树走。当下一个字符是 “$\texttt{/}$” 或者已到达字符串结尾时，尝试从 $go$ 指针跳转。

for (int i = 0; i < len; i++)
{
    int c = charcode(s[i]);
    if (!p->next[c])
        p->next[c] = new node;
    p = p->next[c];
    if (s[i + 1] == '\0' || s[i + 1] == '/')
    {
        if (p->go)
            p = p->go;
    }
}

询问时要输出，我们就不断往父亲方向跳，得到当前真实路径的字符串。

这样查询一次的时间复杂度是 $O(L)$，其中 $L$ 是字符串长度。可以获得100分。

当然你也可以用字符串哈希来做，把每个文件夹作为哈希表中的一个结点，并设置 $go$ 指针跳转。选用那种好用的哈希函数（比如字典序哈希 $\sum_{i}{s_i {31}^i}$ 这种），就可以很方便地在添加字符后仍能知道哈希值。同样也能得到100分。

这是一道喜闻乐见的良心大水题。

DZY Loves Graph

算法一

每一时刻维护当前的边集，然后每一时刻后跑Kruskal计算答案。

时间复杂度$O(n^2 \alpha(n))$，期望得分30分。

算法二

考虑只有加边的情况，那么当图联通后第一次有了最小生成树，然后最小生成树保持不变直到最后，所以只要判断何时图联通然后跑一次Kruskal计算答案即可。

时间复杂度$O(n \alpha(n))$，结合算法一期望得分50分。

算法三

考虑没有Return操作的情况，那么问题就来了，怎么删除一条边。

可以考虑在并查集的时候使用按秩合并的策略，那么每一次加入一条边时对并查集森林新插入的边将一直保持不变直到这条边被删除。

由于操作数目为$m$，所以加入的边数至多为$O(m)$，所以我们只需要对于每一条删除的边把对应的并查集中的边删掉即可。

时间复杂度$O(n \log{n})$，结合算法一、二期望得分70分。

算法四

分析题目的特点，我们发现：插入边的权值是递增的。而我们在做Kruskal时插入的边边权也是递增的。如果我们不考虑Delete和Return操作，则我们发现所有操作就是做一遍Kruskal的过程。

但是现在有Delete操作和Return操作，应该怎么办？

考虑在做Kruskal时怎么表示当前的状态。我们可以用当前并查集的情况以及当前已经加入最小生成树中边的权值和。如果我们对于每一个操作都把这两个记录下来的话，我们就可以发现Delete操作和Return操作就相当于把当前的并查集以及边权和用之前版本的替代。

可持久化！

于是我们可以用可持久化并查集来维护每一个操作的状态。接下来我们要解决的问题是：1.可持久化并查集怎么实现。2.怎么知道删除$k$条边后是哪一个版本。

先解决第一个问题：

并查集的本质就是数组，于是我们需要把数组可持久化，对于这一点可以使用主席树来实现。需要注意的是：在修改的时候不能路径压缩。

因为路径压缩时存在一种情况使得一次路径压缩时花费的时间是$O(n)$级别的，只要我们用Return操作不断退回执行这个操作，总复杂度就会退化为$O(n^2\log{n})$。

于是我们可以采用按秩合并的策略。即每次把深度较小的树合并到深度较大的树下，然后更新深度。这样树深是$\log{n}$级别的。由于我们所有的资料都是从主席树中读取，所以这样的时间复杂度是$O(m\log^2{n})$，空间复杂度是$O(m\log{n})$。

接下来我们解决第二个问题：

我们发现所有的操作构成了一棵树型结构，在这个结构中每个节点是一个操作后的状态，父子关系的定义是：父亲加入一条边后可以到达儿子的状态。于是我们发现删除$k$条边相当于退回当前的第$k$祖先。

考虑用倍增来实现。

每当我们新建一个节点，我们把它的$2^i$祖先都更新出来，这样时间复杂度是$O(m \log{m})$，空间复杂度涉及$O(m \log{m})$。

综上所述，我们可以在时间复杂度$O(m \log^2{n})$，空间复杂度$O(m \log{n} + m \log{m})$下实现（可能导致MLE），结合算法二三期望得分80-100分。

算法五

作为标准的NOIP选手，你可以无视掉算法四。可持久化当然不是UOJ Easy Round难度。

在算法三中，我们实现了Delete和Add操作，那么如何扩展到Return操作存在的情况下呢？

考虑使用类似离线的做法，很显然我们在做第$i$个操作的时候可以知道第$i+1$个操作是否是Return操作。

如果第$i$个操作是Add操作，那么第$i+1$个操作是否是Return并没有太大的影响，因为加入一条边和删除一条边的时间代价都是$O(\log{n})$。

如果第$i$个操作是Delete操作，那么分情况考虑：

1. 如果第$i+1$个操作不是Return操作，那么就用算法三的方法删掉这些边。
2. 如果第$i+1$个操作时Return操作，我们可以事先存下使用当前权值前$k$小的边时最小生成树大小直接输出即可。

综上所述，我们可以在时间复杂度$O(n\log{n})$下实现，期望得分100分。