2016，好好做人。

如大家所见这场 round 比往常的 UR 都要难一点...因为考虑到下一次正式比赛是 WC，所以就放了比较难的题目当做是给大家 WC 的赛前模拟啦。

[Upd] C题的题解可以戳这里

元旦老人与汉诺塔

By jiry_2

算法一

可以发现每一个状态下你能进行的操作最多只有 $3$ 种，所以可以直接搜索每一步的选择然后判断是否和目标状态相同。

时间复杂度 $O(3^{m}n)$，期望得分 $30$ 分。

算法二

输入格式有一定的启发作用，可以发现汉诺塔的合法状态只有 $3^n$ 种，我们开一个数组进行 DP，状态是当前的步数以及状态，然后直接转移就好了。

时间复杂度 $O(3^{n}m)$，结合算法一期望得分 $50$ 分。

算法三

嗯..把算法二改成记忆搜就好了。

时间复杂度 $O(3^{n}m)$，期望得分100分。

讲道理

为了避免这道题被贴上“玄学题”的标签，接下来我们来讲讲道理。

因为存在一种叫做 meet in middle 的东西，我们可以分别从 $S$ 和 $T$ 出发搜 $\frac{m}{2}$ 步，之后再合并，所以接下来我们分析的时候就当做 $m\le 50$。然而实际上这玩意根本没有什么卵用，所以标算并没有加上这个优化。

考虑每一座塔，如果我们要移动它的第 $i$ 个盘子，那么我们必须先把前 $i-1$ 个盘子移动到另外的某一根柱子上，最后再把这个盘子放到最后剩下的柱子上。即使不考虑其他两根柱子上原有的盘子的影响，我们也需要 $2^{i-1}$ 次移动。

因为有 $m\le 50$，所以我们最多只能移动到每一根柱子上的第 $6$ 个盘子。因此可能发生移动的盘子最多只有 $18$ 个，在整个过程中汉诺塔能够达到的状态最多只有 $3^{18}$个。这样我们就得到了一个状态数的上界：$3^{18}m$，大约在 $2\times {10}^{10}$左右。

换一种方式分析可以得到更好的结果。考虑这样的一个汉诺塔：第一根柱子上有 $6$ 个盘子，剩下两根柱子上都没有盘子。我们对每一个 $i\in [0,m]$ 用 BFS 预处理出这个汉诺最少需要 $i$ 步达到的状态数 $d[i]$，那么原问题的状态数一定不超过 $\sum _{i+j+k\le m}d[i]d[j]d[k](m-i-j-k)$。这个式子的含义是：我们枚举每一个柱子上的盘子最后的状态，然后用它们分别在不考虑另外两根柱子的情况下达到这个状态的步数之和当做三个柱子同时存在时的最短步数（因为前者一定小于后者所以这样只会增加统计到的状态数），把汉诺塔每一个状态对记忆搜时的状态数的贡献累加起来就可以对状态数得到一个估计。这个式子的结果好像是在 ${10}^7$ 到 ${10}^8$ 之间，已经是可以接受的范围了。

上述的分析都使用了不同程度的放缩，实际上的状态数远少于分析出来的状态数：用算法三直接进行记忆花搜索的时候状态数只有 ${10}^5$ 级别。如果有老司机能分析出更低的上界，欢迎来和我讨论。

其他

大家可以发现这一场的数据非常良心..

测试数据都是随机的，我只在ex数据里加入了一些构造数据。

而且，大家仔细一点就可以发现，最后两个样例的输出是一样的，这是一个非常重要的提示owo不知道大家有没有看到呢。

总而言之这题还是非常良心的是吧..我也不知道为什么，如果我不拿出点实际行动，总有人以为我是毒瘤。[手动滑稽]

元旦老人与丛林

By shanquan2

题解By jiry_2

算法一

直接枚举每一个可能的边集进行判定。时间复杂度 $O(2^{m}m)$，期望得分 20 分。

算法二

我们在一棵树上加了很少的边，于是我们可以考虑把这张图上无用的点和边给删掉。

可以发现度数小于等于 $2$ 的点是否存在是没有影响的，因为在删掉这个点以及它连出去的所有边之后，如果新图不是丛林，那么原图一定也不是丛林；反之如果新图是丛林，我们可以把新点分别加到两棵森林中：一条边就随便挑一颗森林连进去，两条边就分别连到两棵森林中，这样得到的就是原图拆分成两棵森林的方案，所以原图也是丛林。

于是我们可以每一次找一个度数小于等于 $2$ 的节点把它删掉，那么我们可以最后剩下的图的边数很少（和 UER#4 C 题类似），直接暴力枚举就好了。期望得分 40分。

算法三

观察第三个 subtask，因为每一个点的度数都不小于 $4$，所以可以得到 $m\ge 2n$，显然是无解的，只要输出 No 就能得到这 $10$ 分啦。

算法四

实际上第三个 subtask 是拿来提示标算的。我们可以发现如果原图存在一个非空子图满足 $|E|>2|V|-2$，那么显然无解。实际上存在这样的一个结论：如果图 $G$ 的每一个非空子图都满足 $|E|\le 2|V|-2$，那么它一定是丛林。接下来我们来考虑证明这一个结论：

尝试归纳法，当 $n=1$ 的时候，这张图一定是丛林。

假设所有点数小于 $n$ 的满足结论中条件的图都是丛林。现在，我们来考虑一张 $n(n>2)$ 个点的满足条件的图 $G$，令它度数最小的节点为 $u$，那么 $u$ 的度数只可能为 $0,1,2,3$（原因见算法三）。其中当 $u$ 的度数小于等于 $2$ 的时候，可以用算法二中的方法进行构造。所以我们只考虑 $u$ 的度数是 $3$ 的情况。

对于一个非空子图，如果满足有 $|E|=2|V|-2$，那么我们就把它称作是满的子图。

引理一：对于图中任意两张相交（至少存在一个公共点）的满子图，那么它们的并也一定是满的。

证明：假设这两个子图分别是 $(V1,E1),(V2,E2)$，令 $V3=V1\cap V2,E3=E1\cap E2,V=V1\cup V2,E=E1\cup E2$，那么 $(V3,E3),(V,E)$ 一定都是原图的子图，我们需要证明的是 $|E|=2|V|-2$。

因为 $|E|\le 2|V|-2$，所以 $|E1|+|E2|-|E3|\le 2(|V1|+|V2|-|V3|)-2$，又有$|E1|=2|V1|-2,|E2|=2|V2|-2$，所以 $-|E3|\le 2-2|V3|$。

又因为有 $|E3|\le 2|V3|-2$，所以可以得到 $|E3|=2|V3|-2$，因此 $|E|=2|V|-2$。

接着，设和 $u$ 相连的三个点分别为 $a,b,c$。令 $G$ 在删掉 $u$ 以及那三条边之后的图是 $G1$，由假设，$G1$ 是丛林。

引理二：$a,b,c$ 中至少存在一对节点 $(x,y)$，使得 $G1$ 中不存在同时包含 $x$ 和 $y$ 的满子图。

证明：考虑反证法，假设存在分别包含 $(a,b),(a,c),(b,c)$的满子图，由引理一，我们可以把这三个图并起来，这样就得到了 $G1$ 的一个同时包含 $(a,b,c)$ 的满子图。我们把删掉的 $u$ 和那三条边加入这张子图中，这样就得到了 $G$ 的一个子图。此时这个子图满足 $|E|=2|V|-1$，矛盾。因此引理二得证。

于是，我们可以在 $G1$ 中加入一条连接 $(x,y)$ 的边得到 $G2$，不难发现 $G2$ 依然满足结论中的条件，所以 $G2$ 也是丛林。我们可以构造出 $G2$ 拆分成的两棵森林，其中一定有一颗包含了新加入的边 $(x,y)$，我们删掉这条边，然后再这棵森林中加入边 $(u,x),(u,y)$，再把最后剩下的一条边加入另一棵森林中，于是就得到了 $G$ 拆分而成的两棵森林。所以 $G$ 是丛林。

到此，我们就愉快的证明了这个结论辣owo

于是问题就转化成了判断当前的图是否存在一张非空子图满足 $|E|>2|V|-2$。这个问题可以转化成最大权非空闭合子图：

新建一张 $n+m$ 个点的图 $G3$，其中前 $n$ 个点的权值是 $-2$，后 $m$ 个点的权值是 $1$。如果在 $G$ 中第 $i$ 条边连接的点是 $u_i$ 和 $v_i$，那么就分别连上 $i+n$ 到 $u_i$ 和 $v_i$ 的边。我们只需要判断 $G3$ 的最大权非空闭合子图的权值是否大于 $-2$ 就好啦。

当然直接当做最大权闭合子图来做是不行的，因为当最大权非空闭合子图的权值小于 $0$ 时，最大权闭合子图的权值就是 0。

我们可以强制选取某一个点，即把某一个点的权值设为 0。这样如果存在一个包含这个点的子图满足 $|E|>2|V|-2$，那么这个子图的权值就变得大于 $0$ 了。我们可以枚举这个点，跑 $n$ 次网络流，这样就能检验辣。

如果你使用 dinic 的话，因为这张图是二分图，所以时间复杂度 $O(nm\sqrt{n})$，期望得分 80 分。

算法五

其实优化起来很简单，我们发现相邻两次最大流之间只有两条流量为 $2$ 的边发生了变化，所以直接用退流搞就好啦。

时间复杂度 $O(\sqrt{n}m+nm)$。

其他

在比赛中 myy 大致猜到了这题的结论，但是可惜的是他用最大权密度子图来判断了QAQ于是就非常遗憾的 FST 了。[手动蜡烛]

元旦老人与数列

By xyz111 和 jiry_2

严格上来讲这道 C 题的难度并没有 B 题高，但是因为是一些黑科技，所以就放到了 C 题。

因为这题是我们营员交流的一道例题，所以在 WC 之前我就先不放题解了，给我们的营员交流留一丝悬念，希望大家谅解qwq

对这题有兴趣的同学可以看一下 2015 年多校第二场中的 Gorgeous Sequence 一题获得一些启发owo