手机的生产

from wangyisong1996

大家好我是wys，我第一次出UER的题感觉很excited

这题的idea是这样来的： 有一天wys在写OJ（雾），发现一个需要fork()的程序输出了很多奇怪的东西， 然而wys并不懂fork()，于是wys去学(wan)习(shua)了一下fork()， 然后发现fork() && fork() || fork()会把一个程序复制5份 ，非常有趣， 所以就有了这道题。

算法零

对于$n = 1$的情况，答案一定是2。

可以通过第一个测试点获得10分。

算法一

暴力枚举每个fork()的返回值。

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

算法二

显然可以区间DP啊，$dp[l][r][k]$表示区间$[l,r]$返回值为$k$的方案数， 然后找到区间里的运算符就可以DP了。

时间复杂度$O(n ^ 3)$，可以获得70分。

算法三

UER的A题当然是水水的啦！

首先对于只有"&&"的情况，$k$个fork()的表达式会有$k$种方案返回0，$1$种方案返回1。

然后我们就可以把输入的表达式分为若干段，每一段都只有fork()和"&&"， 然后从左到右计算前$i$段的表达式返回值为0和1的方案数就行了。

时间复杂度$O(n)$，可以获得100分。

信息的交换

from jiry_2

大家好这里是JRY！大家从给UER出题的题数就可以看出来我有多业界良心了吧

其实本来这题也是一道生成树相关的题目..不过在交给VFK之后被改了三四版..现在已经面目全非了。

算法一

我们可以枚举每一张图然后 dfs 判断是否满足答案。

时间复杂度 $O(2^{\binom{n}{2}}n^2)$，期望得分 10 分。

算法二

如果把排列 $a$ 看做一个置换，可以发现每一个循环都对应着一个联通块，一张连通图交换之后得到的置换一定只有一个循环，大致的证明可以见算法三。

于是我们就可以把每一个循环分开来考虑，即考虑每一个联通块的贡献。显然最后得到的置换只和这个联通块的 dfs 树有关，我们可以考虑枚举 dfs 树然后计算每一棵满足条件的 dfs 树对答案的贡献。

因为这张图是无向图，所以 dfs 的时候不可能出现横叉边，只要考虑返祖边就好了。考虑一条返祖边 $(u,v)$，令 $w$ 为 $u$ 的孩子 $v$ 的祖先，那么这条返祖边可能存在当且仅当 $w < v$。

所以我们可以对每一个联通块枚举 dfs 树，然后计算可能的返祖边数量累加进答案，时间复杂度是 $O(n^n)$，期望得分 30 分。

算法三

依然把每一个循环分开来考虑，对于一个循环，我们从这个循环最小下标开始 dfs，可以得到一个这个循环下标的排列，例如循环 $(2,4,5,3,1)$ 可以得到排列 $(1,2,4,3,5)$。找规律可以发现，如果这一个联通块是一棵树，那么这一个排列就是这棵树优先递归下标大的孩子的 dfs 序（就叫它逆 dfs 序好了，用 $A$ 数组表示）。

证明可以用归纳法，当一棵树只有一个节点的时候这个结论显然，接着考虑一棵以 $u$ 为根的树，我们把一棵以 $v$ 为根的且 $v$ 的编号比 $u$ 的所有孩子都大的树接在 $u$ 的下面，那么就相当于在开始递归 $v$ 这棵子树的时候把 $v$ 节点的权值与 $u$ 的权值互换，所以原来 $v$ 这棵树逆 dfs 序的最后一个节点在循环中的后继变成了原来 $u$ 这棵树的逆 dfs 序中除了根以外的第一个节点，这样这个操作相当于把 $v$ 这颗子树的逆 dfs 序插入到了原来的根的后面，这样得到的序列仍然是这颗树的逆 dfs 序（我语文比较差大家凑和着看吧）。

如果原问题是求树的计数的话，就可以有一种很简单的 DP 方法了：

令 $f_{i,j}$ 为让逆 dfs 序中区间 $[i,j]$ 成为一个每一棵树都是连续的一段的森林的方案数，那么转移就是:

\begin{align*} f_{i,j}=\sum_{k=i+1}^j [A_i>A_k] \times f_{k,j} \times f_{i+1,k-1} \end{align*}

接着和算法二一样，考虑每一棵可能的 dfs 树对答案的贡献，令 $h_{i,j}$ 为逆 dfs 序的区间 $[i+1,j]$ 中比第 $i$ 个数大的数的个数，那么它的意义就是 $[i,j]$ 作为一棵子树时，可能成为返祖边的边的数量，利用这个修改一下转移方程就可以得到答案了：

\begin{align*} f_{i,j}=\sum_{k=i+1}^j [A_i>A_k] \times f_{k,j} \times f_{i+1,k-1} \times 2^{h_{i,k-1}} \end{align*}

到此我们在 $O(l^3)$ 的内 DP 求得了一个大小为 $l$ 的联通块的答案，总的时间复杂度为 $O(n^3)$，期望得分 100 分，如果你 DP 方程写丑了复杂度多了若干个 $n$ 那就只能得到 70 分的部分分了。

我的语文很差求轻喷555

谣言的传播

from Glaceon08，题目是 vfleaking 造的。

算法一

对于第 1 个测试点，$n \leq 8$，赶紧使用 $O(n^2 \times n!)$ 大法即可。

可以获得 10 分。

算法二

由于 $b$ 是一个排列，可以看出这是个二分图最大权匹配。用 $O(n^3)$ 的时间暴力计算 $i$ 的真理捍卫者是 $j$ 的影响系数，然后用 $O(n^3)$ 或 $O(n^4)$ 的 KM 算法即可。

当然你要是强行树形 DP 我也资瓷。（不过这题要输出方案耶，虽说不太麻烦但是感觉写DP的是勇士）

可以获得 40 分。

算法三

我们进一步分析问题。考虑告诉你 $i$ 的真理捍卫者是 $j$，你怎么计算影响系数呢？

显然好朋友关系形成的是很多个基环内向树的样子。我们设 $f_i$ 为从 $i$ 出发能走到的结点数。

1. 如果 $i$ 和 $j$ 在同一个内向树内，且 $j$ 是 $i$ 的祖先，那么影响系数是 $f_i - f_j + 1$。
2. 如果 $i$ 和 $j$ 在同一个基环内向树内（即看成无向图后，在同一个连通块内），$j$ 在环上，设环长为 $l$ 以及 $i$ 所在内向树的根到 $j$ 的距离为 $s$，那么影响系数就是 $f_i - l + s + 1$。
3. 其它情况答案均为 $f_i$。

显然影响系数和的最大值的上界为 $\sum_{i = 1}^{n} f_i$。现在我们来构造一组达到上界的方案。

对于每个子树（内向树的子树），我们可以让每个父亲选择一个大儿子，把这条边染黑。这样得到了一个树的链剖分，每条链一定以叶子结尾。对于每条链，我们从上到下，把儿子作为父亲的真理捍卫者。然后每条链的结尾都是叶子，我们就按某种顺序把后一条链顶端作为前一条链的结尾的真理捍卫者，最后还剩下内向树的根结点和一个没有真理捍卫者的叶子。

于是我们对于环，绕一圈，把后一个内向树根作为前一个内向树剩下的那个叶子的真理捍卫者。

某种顺序的话，你可以把链按顶端深度排序搞搞……

我的写法是每次把一棵子树合并到父亲上去……记录子树内的那个剩下的叶子，子树的根是没有作为别人的捍卫者的。然后合并到父亲上去的时候接起来搞搞。这样实际上就是某种链剖分。

这样可以发现每个结点的真理捍卫者都没“挡路”，达到了问题的上界。

可以通过每个测试点的第一问获得 50 分。结合算法二可以获得 70 分。

算法四

最小值其实也很简单 —— 取刚才构造的那组解的逆置换就行了。就是原来 $j$ 是 $i$ 的真理捍卫者，现在 $i$ 是 $j$ 的真理捍卫者。

妈呀这为什么是对的？

初始时答案为 $\sum_{i = 1}^{n} f_i$，我们考虑一个真理捍卫者 $j$，设 $i$ 的真理捍卫者为 $j$：

• 如果 $j$ 不在环上且是 $i$ 的祖先那么对答案贡献 $-f_j + 1$
• 如果 $j$ 在环上且和 $i$ 在同一个基环内向树那么对答案贡献 $-l + s + 1$ （符号见前文）

这样就可以以真理捍卫者的视角考虑问题 —— 原来是尽量别让真理捍卫者挡路，现在是尽量让真理捍卫者挡别人的路。

注意到，在叶子上的真理捍卫者无路如何也不可能挡别人的路，所以他们可以自暴自弃了。

所以还是可以链剖分，按链的顺序依次挡路，然后绕环一圈让剩下的叶子依次挡路。

可以通过所有测试点获得 100 分。如果你某个地方写残了或想残了导致算法变成 $O(n^2)$ 的了，还是可以拿 70 分的。