12.2 模拟赛

题目来源：

• CF316D3
• CF477D
• CF468D

A 队伍分配

考虑建反图。然后问题就变成了把这个图分成两个集合，使得这两个集合内部没有任何边，仅在集合间有边。不难发现这就是在问这是不是一个二分图。

然后由于反图不一定联通，我们相当于是把若干个二分图联通块拼起来。也就是说相当于是有很多个数 $S_R - S_L$ ，每个数的贡献是 $+x$ 或者 $-x$ ，我们需要找到一种选贡献的方法使得最后得到的数的绝对值尽量大。由于显然 $S_R - S_L$ 是 $O(n)$ 的，和也是 $O(n)$ 的，直接背包即可。由于这个背包只需要判断是否可达，也可以直接用 bitset 维护。

但是这个题有两个坑点，不注意很容易爆炸。

• 在建完反图后，由于两个连通块不能有任何一个边，而原图是单向边，所以应该强制把单向边转成双向的。而且出题人非常毒瘤地让你不判这个也能过大样例。
• 如果 $n=1$ ，显然没办法分成两个集合，但是直接做会认为这是一个二分图。需要特判。

复杂度 $O(n^2)$ 。

B 抛球

然后场上因为这个题自闭了。。

显然，答案只和 $1$ 、$2$ 的个数有关。

考虑一共有 $a$ 个 $1$ ，$b$ 个 $2$ 的时候的答案怎么算。可以倒着考虑这个问题，能否通过限制内的 swap 来从某一个排列变换到 $1\dots n$ 。

单独考虑这个排列的所有环。不难发现，如果环里面有不多于两个 $1$ ，那么一定可以解决问题。如果没有 $1$ ，显然可以直接在环上交换。如果只有一个 $1$ ，假设环的长度是 $2$ ，显然可以，就是交换不交换的问题。否则，每次我们把 $1$ 所在的位置应当是的值归位到 $1$ 来， 然后删掉这个位置，得到一个长度为 $n-1$ ，仍然只有一个位置只能交换一次的子问题，于是可以归纳证明。

而如果两个位置是 $1$ ，可以用类似的归纳方法，如果环的长度是 $2$ ，显然直接互换或者不互换即可，如果环的长度是 $3$ ，我们考虑唯一的一个为 $2$ 的位置的值，先把这个值归位，再把这个位置应有的值归位过来即可。不难发现只有这一种情况。于是又可以归纳证明了。

假设有大于等于三个位置是 $1$ ，不难发现这样甚至不能形成一个联通的链，所以不可能把所有数都归为。

我们考虑先给 $1$ 分好组，也就是每个集合要么只有一个 $1$ 要么有两个 $1$ 。这个可以考虑最后一个和之前的哪一个来配对，用一个 $dp$ 来实现

$dp[i] = dp[i - 1] + (i - 1)dp[i - 2]$

会发现往排列里面插东西等价于往环里面插东西。于是接下来插入 $2$ 的时候，我们可以插入到之前任意一个环的任意一个位置后，也可以新开一个环。于是假设到现在我们一共插入了 $i$ 个数，那么接下来这个 $2$ 的插入的方案数量是 $i+1$ 。

于是最后的答案就是

$dp[a] \frac{(a+b)!}{a!}$

复杂度 $O(n)$ 。

C 打印

感觉是一个很容易想的题。。再次暴露出自己 $dp$ 力为 $0$ 。

考虑 $f[i][j]$ 表示最后一段被输出的数是 $[j \dots i]$ 这一段的时候的最小次数，$g[i][j]$ 表示对应的方案数量。

不难发现，转移是 $f[j-1]$ 的一段后缀 $\min$ 或 $g[j - 1]$ 的一段后缀的和。

所以直接拿一个数组维护这个东西即可，一个维护最小值一个维护和。具体来说，设

$F[i][j] = \min_{i \ge t \ge j} f[i][j]\\ G[i][j] = \sum_{i \ge t \ge j} G[i][j]$

然后直接转移即可。这里还需要讨论一下这个后缀最靠后是哪里。不难发现，设当前这段的长度是 $len$ ，那么这个后缀要么是 $[j-len,j-1]$ 要么是 $[j-len+1,j-1]$ 。这个的比较可以直接预处理后缀的两两的 LCP 实现。

于是复杂度 $O(n^2)$ 。

D 树上距离和

我们考虑可能做到的答案上界，是每条边的边权乘上两边的 $siz$ 的较小值。

会发现，在根为重心，且每次选择的 $i,p_i$ 要么有至少一个为根，要么不同子树的时候可以取到这个上界。 CSP 考前证明过可以参考一下，这里就不写了（忘掉了）

我们考虑对 $1\dots n$ 依次选点来确定 $p_i$。如果我们把每个点的权值看成 $2$ ，也就是在 $i$ 的时候，以及 $p_j = i$ 的时候分别会对这个点的权值减少 $1$ ，于是每个根的儿子的子树就有了一个权值，然后我们每次选择两个点后就相当于分别对它们所在的子树减 $1$ 。这是一个非常经典的问题，结论是在 $2\max \le S$ 的时候一定有解。证明可以考虑 $\text{Hall}$ 定理或者归纳。如果用 $\text{Hall}$ 定理，就是考虑一个二分图匹配问题，考虑一个集合内的个数，只要满足 $A_i > S - A_i$ 就意味着不存在完美匹配，也就是说如果 $2A_i \le S$ 对于所有 $i$ 成立，那么就有完美匹配。

现在我们每次进行的操作大概是这样的：考虑当前的点 $i$ ，找到它最小的 $p_i$ 满足如果把 $i,p_i$ 所在的子树大小分别减 $1$ 后仍然满足 $2\max < S$ ，然后把 $p_i$ 这个点从我们维护的集合中删掉。找 $p_i$ 的过程有这么些情况：

• 当前最大的子树卡着上界，也就是满足 $2\max = S$ ，且这个数在最大的子树中，那么我们只需要给这个数所在的子树以及其他树中的最小的点所在的子树分别减 $1$ 即可，这样会让 $\max - 1 , S - 2$ ，依然卡这上界。
• 当前最大的子树卡着上界，且这个数不在最大的子树中，那么一定删除的是最大的子树中的最小的数。
• 当前最大的子树没有卡着上界，那么直接选择当前的树和最小的子树即可，如果这两个是同一个树，那么我们就选择当前的树和次小的子树。

不难发现，第一种和第三种情况可以合并，也就是只有在最大的子树卡着上界，且这个数不在最大的子树的时候删掉最大的子树的最小数，否则一定是第三种情况。

具体实现参考了某份很优秀的 CF 代码。实现大概需要开一个 set 维护每个根的儿子的子树大小以及编号，每个根的儿子的子树内的还没被删的点，以及所有根的子树内的最小的点的最小点。

然后比较毒瘤的地方在于根的处理。因为根是唯一一个可以选自己的东西。比较暴力的做法是直接把根删了，再做一遍。但是其实可以通过优秀的实现判掉。

实现的时候在维护子树的 set 中我们不插入根，但是在维护全局的最小的点的维护中插入根。如果当前考虑的点是根，如果考虑的是第一种转移，显然它不可能选到自己，直接做即可。如果考虑的是第二种转移，那么一定可以和全局最小值匹配（即使这个最小值是根也可以）。找到 $p_i$ 维护的时候一定会把 $p_i$ 在集合中删除。

总的复杂度是 $O(n\log n)$ 。实现的好感觉就是一个非常好的题，实现的不太好就很容易挂。