UOJ Round #7 题解

水题生成器

from taorunz

算法一

对于前6个数据$n\le5$，$5!=120$,只有$16$个约数。我们直接用$16^5$枚举这些子集，找到一个和等于$m$的集合即可。

当然，由于$n$很小，你还可以用分类讨论之类的方法乱搞。

期望得分：30分

算法二

对于前14个数据$n\le9$.

我们可以将本问题看成一个背包问题来解。

时间复杂度是$O(d(n!)*m)$的, 其中$d(x)$表示$x$的约数。

期望得分：70分

算法三

本题与阶乘紧密相关，说到把不超过$n!$的数分解成$n$个数的和，最容易想到的就是阶乘进位制。（就是分解成 $\sum_{k}a_k \cdot k!$ 且 $a_k \leq k$）

然而在本题里，用阶乘进位制分解得到的数不一定是$n!$的约数。（例如样例一，阶乘进位制分解为$100=96+4=4 \times 4!+2 \times 2!$，96却不是120约数）

怎么办呢？把阶乘进位制倒过来！

我们令新的进位制的第$k$位的位值为 $n(n-1)\cdots (n-k)$

然后将$m$分解，我们发现分解出来的数都是形如$n(n-1)\cdots (n-k)a_k$的数。而$a_k$是小于$(n-k)$的！

这样$n(n−1)⋯(n−k)a_k$就一定是$n!$的约数，本题圆满解决啦！

期望得分：100分

算法四

不知道阶乘进位制？没关系！我们可以直接贪心！

我们先算出$n!$的所有约数（$n=20$时有$41040$个），然后从大到小依次尝试减去当前数，直到减为零为止。

有趣的是，用这种方法，一定可以在不超过$n$步内减到零！

为什么呢？我们参考算法三，对于当前剩余要造题的难度值之和$m'$ ,我们可以将它表示成反阶乘进位制后，取出最高位的数。这样就可以使得$m'$降低一个（反阶乘进位制的）数量级。而算法四所取出来的数不会比算法三取出的低，所以算法四也可以保证每次使得$m'$降低一个（反阶乘进位制的）数量级。而总共数量级最多为$n$，一定能够在$n$次内减到零。

期望得分：100分

水题出题人

from saffah 大家好我是萌萌哒水题出题人saffah！

这道题目的idea来源是众所周知的APIO2013 tasksauthor。我们将在接下来的分析当中一点点发现这道NOIP好题是如何演变成现在这样的丧病题目的。

子任务1

归并排序卡计数排序，$T$很小。

注意到计数排序的用时与序列的最大元素有关，那么我们只需令$n=1,a_1=2333333$就可以通过这个测试点了。

子任务2

冒泡排序卡选择排序，$T$很大。

这两个算法的时间都是平方级的，而且大概都受到逆序对数的加成。

分别往两个程序里面扔升序序列和降序序列，发现要想冒泡排序卡选择排序，必须是升序，这样能卡一个很小的常数。

其实升序序列和常数序列在这里没什么区别，那么我们往里扔一堆$0$，发现$1991$个$0$可以刚好让选择排序T掉。这个时候的$S$是$1987021$，可以拿6分。

注意到此时选择排序的用时是$2000959$，看起来没有被充分利用。我们只需把序列长度减少$1$变成$1990$，然后把里面的一个$0$变成$1$，使得选择排序的用时刚好超过$2000000$。

我们人肉二分这个$1$放在哪里就可以啦！玩出来发现刚好$S=1986591$。（这2分得的真艰难）

子任务3

归并排序卡快速排序，$T$比较小。

也就是说如果想AC这个子任务，快速排序要比归并排序慢大概20倍，这显然不是卡常数而是卡复杂度。（因为向归并排序和快速排序扔一个随机序列会发现归并排序的常数确实比较大）

注意这个快速排序的基准元素并不是随机选的，而是选择了当前区间的中间元素。根据快速排序的性质，只需使它每次选取的中间元素都是当前区间的最大值或最小值，就能把快速排序卡到平方级。

python代码：

a = range(n)
for i in range(n):
    j = i / 2
    a[i], a[j] = a[j], a[i]

其中的$n$还是需要人肉二分一下的。

总之这样就可以轻松加愉快地通过这个subtask啦！18分到手！

子任务4

计数排序卡冒泡排序，$T$很小。

既然是卡冒泡排序，第一个想到的就是给一个降序序列，到处都是逆序对。

但是这样跑出来以后发现$S=6007$，只能得一个合法分。原因很简单，要想计数排序跑得快，每个数就不能太大。

设序列中所有的数都小于$x$，假设$x$是定值，那么想让计数排序跑得快，就要让$n$尽可能小。

考虑已知$x$如何找到最小的$n$使得存在一个序列让冒泡排序超时。这一步可以二分$n$，转化为问：是否存在一个序列$(n,x)$卡掉冒泡排序。

设这个序列中数$i$出现的次数为$c_i$，那么这个序列一定是降序排列的。注意$n$已经确定了，冒泡排序时间只与逆序对有关，而逆序对等于 $$\sum_{i< j} c_ic_j$$ 也就是 $$\frac12 (n^2 - \sum_i {c_i}^2)$$ 所以我们要最小化 $$\sum_i {c_i}^2$$ 那么就是要让所有的$c_i$尽可能相等。

一个巧妙的方法，已知$n,x$生成一个最优序列：

def gen(n, x):
    a = []
    for i in range(n):
        a = [i * x / n] + a
    return a

说了这么多，总结一下就是：枚举$x$，二分$n$，构造最优卡冒泡序列，再算出对应的计数排序的用时，取最优解。

19分愉快到手！

子任务5

选择排序卡冒泡排序，$T$比较大。

按照上一个子任务的思路直接给一个降序序列，发现$S=1009504$，完全是只有合法分的节奏。

直接套上一个程序跑这个子任务，发现能跑出$x=33, n=1011, S=537365$。瞬间10分到手啦！

我们出现了两位怒虐标答的选手：alpq654321的533650和xywmmd的529079！

根据规则，我们将发给xywmmd UOJ抱枕一个！

在这里只分享一个alpq654321的最开始的做法QAQ……（策爷做法看不懂嘛）

————————以下是alpq654321的神做法————————

要构造一个序列，使得冒泡排序慢而选择排序快，考虑这样构造：

def solve(l , r):
    if l > r:
        return []
    mid = (l + r) / 2
    return [mid] + solve(mid + 1, r) + solve(l, mid - 1)

我们神奇地发现这个序列的性质很好，因为从每个位置开始最小值的变化次数都不会很多，而且逆序对依然是平方级别的。

这样就可以愉快地AC+拿抱枕了。当然，alpq654321还有更神的最终版做法，我们请他亲自来讲……

————————以上是alpq654321的神做法————————

（以下是saffah的手玩历程）

但是我们怎能满足于10分？注意到此时的冒泡用时为$2000301$，我们尝试在这个方案上将逆序对稍微减小一点，那么只需把某个数减$1$。

人肉枚举要减哪个数，发现如果把第一个$16$减去$1$，$S$会变成$536447$，看起来十分靠谱嘛！

然后我们接着减，直到冒泡的时间只超出$2000000$一点点，这个时候发现$S=536443$，就可以愉快地拿到20分啦！

（以下是vfleaking的爬山历程）

但是我们怎能满足于10分？我们像上一个subtask一样，把一个序列用每个数出现次数的数组$c_i$表示。每次随机调整$c_i$，将其中一位+1另一位-1，若变优则接受。

跑若干分钟就可以跑出能拿20分的方案啦！

子任务6

Bogo排序卡快速排序，$T$比较小。

“啥？FML？我没看错题吧？用最不靠谱的排序卡最靠谱的排序？而且$T$还这么小，要Bogo排序比快速排序快大概50倍？简直掀桌报警啦！”

且慢……我们先看看这个Bogo排序的大体思路。

首先它实现了一个线性同余法的随机数生成器。读入数据以后，init了一下随机参数，并用输入的$a[i]$来计算随机初值。每次将两个随机的数交换位置，并更换新的随机参数，直到排好序为止。

看起来很靠谱嘛！

稍加观察就可以发现，所有的模数都是$n$，而且每次迭代都是自然溢出。也就是说，如果$n$取到了$2$的某个幂，就能保证这个所有的运算都是在模$n$意义下正确的（在第一次更换随机参数之前）。

再看初始参数$26648577$和$10108929$，它们的二进制分别是$1 1001 0110 1010 0000 0000 0001$和$1001 1010 0100 0000 0000 0001$。

妈呀！这两个数在$n$是一个不太大的$2$的幂的情况下都是$1$！也就是说，随机数生成器在第一次更换随机参数之前，产生的都是连续自然数！

现在的Bogo排序中的“随机打乱”实际上就变成了这个样子：

for i in range(n):
    j = (i + seed + 1) % n
    a[i], a[j] = a[j], a[i]

其中$seed$仍是由输入序列$a$决定的。

注意这个性质只能持续到第一次更换随机参数之前，所以我们必须一次打乱就将序列排好序。依次代入$2$的各种幂，观察一次打乱后的$counter$值，我们容易确定$n=4096$。

为了使这个“随机打乱”能够一下子排好序，我们构造输入序列的过程就必然是：

n = 4096
a = range(n)
for i in reversed(range(n)):
    j = (i + seed + 1) % n
    a[i], a[j] = a[j], a[i]

我们只需一个$seed$，使得如此生成的序列能卡掉快速排序。由于范围不大，我们可以从$0$到$n-1$枚举$seed$代入快速排序检验，最终能够确定$seed=2048$。

最后的问题是，给出一个序列，要求不改变它的相对大小顺序而使由它产生的$seed$为$2048$。

如果无视“不改变它的相对大小顺序”这一条就很好做了。直接算出由前$n-1$项产生的$seed$，然后枚举最后一项算出最终的$seed$，依次检查是否在模$n$意义下等于$2048$，一定能很快找到答案。

上述算法在$a[n-1]$是$a$的最大值的情况下是正确的。如果$a[n-1]$不是最大值，只需先把$a$中所有比它大的元素都加上一个充分大的数（比如$1000000$），再用上述算法就能解决了。

呼～这样就可以……不是很愉快地拿到30分啦！

这样6个子任务就都解决啦，就能拿100分啦！

什么，你还不满足？

子任务5 EXT

妈妈我想要UOJ抱枕怎么办！

怎么办呢……我们只需要像虐标答的神犇们一样神就可以了……

————————以下是saffah的逗比历程————————

我们观察一下爬山爬出来的方案，稍微好一些的方案当中，$c$数组都是先增后减，并且十分对称。

等等，对称的话，似乎两种排序算法的时间都很好算呀？

对于冒泡排序，只需知道所有$c_i$的平方和，套上子任务4的式子算出逆序对，然后就知道了程序中$a[j] > a[j + 1]$的情况发生的次数，进而算出总用时。

对于选择排序……一个乱七八糟的序列的选择排序用时是很不好算的，但是由于$c$是对称的，设值域是$\left[0, x\right)$，那么显然选择排序的过程就是先把$0$和$x-1$对换，再把$1$和$x-2$对换……

选择排序最难算的就是$a[j] < min$的触发次数，而这在对称情况下就是两个对应位置之间经过的块的个数。也就是说，一个序列的$a[j] < min$触发次数就是 $$\sum_{i < \frac x2} c_i(x-2i) + \sum_{i \geq \frac x2} c_i$$

根据这个次数就容易算出它的选择排序代价了。

这个触发次数似乎可能会比较大？但是冒泡需要算的平方和看起来并不大，之前的方案都在$30000$左右。

考虑动态规划。设$dp[i][j][k]$表示：长度为$i$，值域为$\left[0, j\right)$，其$c_i$数组的平方和为$k$且$c_i$是对称的序列，将它进行选择排序时，$a[j] < min$的最小触发次数。

状态转移：由于$c_i$是对称的，我们考虑枚举$c_0$（也就是$c_{j-1}$），剩下一个长度为$i-2c_0$，值域为$\left[1, j - 1\right)$，其$c_i$数组的平方和为$k-2{c_0}^2$且$c_i$是对称的序列。注意值域是$\left[1, j - 1\right)$与值域是$\left[0, j - 2\right)$是等价的，而多出来的这些数贡献的$a[j] < min$触发次数也是很好算的，所以我们就能愉快地DP了。

$i,j,k$上界该取多大呢？$i$少说也要取$1200$，$j$也要取到$50$，$k$保险起见就取$50000$吧。这样总共需要开$3 \times 10^9$的空间。

嗯，剩下的事就是买一个大内存的电脑了。

靠谱点的做法呢？

滚动数组？我们好像还要记录方案……套用范爷题做法？各种不想写……

注意到，如果$j$是偶数，那么$i$和$k$必须也都是偶数才能合法。对于这种情况可以做一个DP，内存只需要开原来的$1/8$，可以接受。

如果$j$是奇数呢？直接做的话内存是原来的一半，还是不行的。我们只需对$c_{\frac{j-1}2}$的奇偶性进行讨论，这样$i$和$k$的奇偶性就确定了，每种情况内存还是原来的$1/8$。

我们只需要做三个八分之一DP就可以把这个问题解决掉啦！

saffah表示最优跑出了$535274$，实在是再也玩不出更优的了，就把这个定为了送抱枕最低分数线。

任何人有任何感觉更靠谱的想法都欢迎在这里讨论呀～

水题走四方

from Picks

Picks 给的题面，但是他自己并不会做。其它的事情都是 vfleaking 干的。

算法一

对于子任务 1， $n \leq 12$。

我们可以记下当前两个地卜师在什么位置，以及每个结点是否被访问过，然后 DP 就可以了。

可以获得 $20$ 分。

算法二

对于子任务 2， $n \leq 1000$。

记 $f[v]$ 为两个地卜师现在都在 $v$，遍历以 $v$ 为根的子树的最小代价。然后显然应该是一个人等着，另一个人出去到处逛，最后还剩一棵子树的时候，两个人一起往下走。

大错特错！有可能剩一棵子树和一个叶子没访问过，而如果往这棵子树走，将会经过很长一段只有一个儿子的结点的路。那么我们此时可以让这两个地卜师一起往下走，一个走到叶子停下，另一个走到那棵子树中往下第一个有不止一个儿子的位置停下。如果是先到达了分叉点，就等一等那个往叶子走的地卜师走到后瞬移过来。

显然，我们可以枚举最后剩下的子树和叶子分别是哪个，然后 DP 算算代价。当然你也可以注意到，如果已知选哪个子树，显然选最深的那个叶子更优。

我不知道你们有没有一开始想错了，至少我一开始想错了，还以为是水题 = =……

然后你会发现这个算法他过不了样例三！

我觉得大家这时候应该写个算法一然后对拍，就能知道为什么了。但是为啥大家都弃疗了呢？（我好像是 $n = 15$ 的时候狂拍拍出来的，因为反例很稀少）

那么究竟是怎么回事呢 = =……

我们考虑一下，假如有两根很长很长的筷子，我们把用于吃饭的那一头粘起来并作为根结点。那么答案显然是一根筷子的长度。但是如果这两根筷子是劣质一次性筷子，在两根筷子的侧边长了一点点毛刺，这些毛刺比较靠近吃饭的那一端。那么最优解是什么呢？

最优解是：先派个地卜师下去把毛刺都去掉，然后再两个地卜师一起下去分别遍历两根筷子的主干部分。这样大约就只需要一根筷子的长度。而如果用刚才那个算法，会算出来是大约两根筷子的长度。于是这个算法又是错的。

孩子算法老是错，一定是姿势不对。

我们来重新考虑问题。现在有两个地卜师，一个是本体一个是分身，在树上乱逛。注意如果两个地卜师站在一起，在我们眼前一晃其实我们是分不清楚也不用分清楚谁是谁的，我们可以根据自己的需要调换两人的身份。所以对于任意一组移动方案，我们一定可以把这组方案调整成本体从来没有瞬移过的方案。

然后我们考虑本体，他一定是往下走几步，停几步，再走几步，再停几步。如果一组方案最后本体没有停在某个叶子，我们肯定可以让本体追随分身的脚步停在某个叶子。

好，那么现在本体是从根走到了某个叶子 $v$，我们现在考虑其它还没有被访问的结点。我们称根到 $v$ 的链为主链，那么我们就是要让分身来访问主链上支出去的那些子树。我们可以断言一组最优方案一定是这样的：主链上有一些关键结点，分身和本体本来是在一起走的，走到关键结点处，分身会下去访问这个关键点到下一个关键点之间所有支出去的子树的叶子，访问一个，瞬移回来。当还剩下一个叶子的时候，本体和分身一起往下，本体去下一个关键点，分身去叶子。分身到了叶子处就瞬移到本体所在位置。

这是因为，每个支出去的子树的叶子都是要访问的，访问肯定对应着“溜出去”和“瞬移回来”这两个过程，溜出去的位置到该叶子的距离就是时间。显然如果已知你只能选择哪几个地方（即关键点）之一溜出去，那么选择最近的那个最好。（其实不太显然，从一个关键点到另一个关键点，最后一个访问的叶子也可能节约时间，但是也是好证的）

对于“最后一个访问的叶子”，显然取最深的叶子最优。

所以我们用 DP 求出 $f[v]$ 为从根到关键点 $v$ 时的最短时间，然后在每个叶子的 $f$ 中取最小值就可以了。

假设已经知道是哪条主链，设 $d[v]$ 为结点 $v$ 的深度，$d_m[v]$ 为主链上结点 $v$ 往外伸出去的子树中最深的叶子的深度，$d_m[u, v]$ 为主链上结点 $u$ 到结点 $v$ （不包括结点 $v$）往外伸出去的子树中最深的叶子的深度，$d_s[v]$ 为结点 $v$ 的子树中叶子的深度之和，$n_l[v]$ 为结点 $v$ 的子树中叶子的个数。那么我们就能用 DP 求出 $f[v]$ 为从根到关键点 $v$ 时的最短时间。

\begin{equation} f[v] = \min_u\{f[u] + d_s[u] - d_s[v] - (n_l[u] - n_l[v]) \cdot d[u] + \min\{d[v] -d_m[u, v], 0\}\} \end{equation}

其中 $u$ 是 $v$ 的祖先。

然后你 dfs 一遍边 dfs 边 DP 就可以了。

使用暴力就能做到 $O(n^2)$，可以获得 $50$ 分。

算法三

我们仔细观察这个行为：“当还剩下一个叶子的时候，本体和分身一起往下，本体去下一个关键点，分身去叶子。分身到了叶子处就瞬移到本体所在位置。” 这里有一种情况是：关键点到叶子的距离比到下一个关键点短，那么分身瞬移到本体位置后，就会一起向下走。因为最后一次走的叶子一定两个关键点间最深的叶子，所以重逢的位置到下一个关键点一定是没有支出去的子树的。我们不妨把这个重逢的地方也设为关键点。

这样，我们 DP 的时候就可以考虑两种情况：

$v$ 的父亲只有 $v$ 这一个儿子，用父亲的 $f$ 加 $1$ 更新 $f[v]$。
考虑一个 $v$ 的祖先 $u$，且 $d_m[u, v] \geq d[v]$，用“一坨式子”更新。

考虑情况二的不等式：$d_m[u, v] \geq d[v]$。如果最后一个叶子不是 $u$ 伸出去的子树中的，那么遍历最后一个叶子的时候两个地卜师可以一起向下走一段再分开。

于是为什么我们不把这个分开的位置作为关键点呢？答案显然不会更差 —— 首先一起走的部分还是一起走了，而“叶子到关键点距离和”又减少了。所以，我们只用考虑那些 $d_m[u]$ 比后面所有 $d_m$ 都大的 $u$ 进行转移就行了。

注意到，一个 $d_m[u]$ 就意味着子树中至少 $d_m[u] - d[u]$ 个结点，于是我们在 dfs 的时候如果维护一个单调栈记录所有 “$d_m[u]$ 比后面所有 $d_m$ 都大的 $u$”，栈的长度就是 $O(\sqrt{n})$ 的。

时间复杂度 $O(n \sqrt{n})$，可以获得 $80$ 分。

什么？你想起了 NOI2014 的购票去优化 DP？感觉 $O(n \log n) \sim O(n \log^3 n)$ 的算法。得分不明，祝你好运 = =……

算法四

其实你只要接下来注意到，情况二中你只用考虑在 $v$ 上方离 $v$ 最近的，且 $d_m[u] \geq d[v]$ 的 $u$ 就行了。

因为假设 $d_m[u_1] \geq d[v]$，$d_m[u_2] \geq d[v]$，且 $u_1$ 是 $u_2$ 的祖先，$u_2$ 是 $v$ 的祖先。那么从关键点 $u_1$ 到关键点 $v$ 所花的时间一定是不如从关键点 $u_1$ 到关键点 $u_2$ 再到 $v$ 的 —— 因为在一起走的部分还是在一起，而“叶子到关键点距离和”减少了。

所以，其实只要你把暴力DP想清楚了 = =……这题真的就顺流直下，沦为了一个大水题……但是你不多想想，就成了恶心斜率优化题。

你可以 dfs 一下，维护一个 $d_m$ 的单调栈。弹栈的时候由于是基于均摊的，不能再用 while 循环弹了，你可以在栈上二分出新的栈顶指针位置，存下这个地方原来的值，push 进去，然后递归下去。回溯回来的时候把栈顶指针和值复原。

时间复杂度 $O(n \log n)$。本来我想卡掉的，但是常数太小了。T^T……可以获得 $100$ 分。