The 3rd Universal Cup. Stage 15: Chengdu 解题集

A. Arrow a Row

我们把整个序列划分成若干个形似 \(\text{>>>>..>>}\) 的连续段，并尝试用一个最右边连通块里最左边的 \(\text{>>>}\) 去覆盖掉左边不和它在一个段里的所有 \(\text{>}\)，如果最右边的连续段长度小于 2 或者没有连续段则肯定无解。

对于在同一个连续段里其他的 \(\text{>}\)，我们拉到最前面做，只要连续段不为 1，就只用找任意一个最左边 \(\text{>}\) 之前的位置作为箭头的左端点一起覆盖即可。

实现时还要注意判断第一个和最后一个不能是 \(\text{_}\)，以及如果只有一个连续段也是无解的。

B. Athlete Welcome Ceremony

最朴素的做法是 \(O(n^4)\) 的，直接记一个 \(f_{i,x,y,z}\) 表示当前在什么位置，每个数各用了多少的方案数，但是这题的关键点在于我们最终需要的状态数不会很多，但是硬优化是没法做的，因此解法应该还需要一步转化。

不超过 \(x\)、\(y\)、\(z\) 看上去就很能容斥，我们尝试用无限制的方案数减去限制一个必须超过上界的再加上限制两个的方案数，限制三个呢？不难发现一定无解，因此不用考虑。

而限制一个或两个必须超过上界则是好算的，此时 dp 状态少若干维度，可以接受，复杂度 \(O(n^3)\)。

C. Chinese Chess

看着不太像题，跳了。

D. Closest Derangement

观察样例，你可以发现 \(n=3\) 的情况下最小权值是 4，且只有两种排列方式，尝试推广，不难发现当 \(n\) 为偶数的时候我们可以做更好，交换相邻的数就能把权值降到 \(n\)，且不难发现这是最优的解法，并只有一种构造方式。

当 \(n\) 为奇数时不难猜到最终序列一定是选取某个长度为 3 的连续的序列并按照 \(n=3\) 的方式作置换，证明就是考虑把序列拆成置换环，环长如果大于 3 则一定是劣的，且你至少得构造一个大于 2 的置换环。

由此，我们就可以用一个长度为 3 的置换表示一个最终的排列，且排列数量只有 \(O(n)\) 种，直接对其进行排序，每次你需要找到两个排列第一个不一样的位置。首先假设两个排列分别为 \((x_1,x_1+1,x_1+2)\) 和 \((x_2,x_2+1,x_2+2)\)，不难发现如果 \(x_1+2<x_2-1\)，那么两个排列中原来权处在 \([x_1+3,x_2-1]\) 中的数新权一定不同，考虑交换对象则容易证明。

因此你只需把 6 个被长度为 3 的置换换到的位置和中间最小的位置拿出来比较一下即可完成排序，中间最小的位置可以 rmq 简单维护。

E. Disrupting Communications

正难则反，考虑算出不包含路径上每一个点的连通块个数，如果你把这些路径上的点去掉，就会发现剩下的点形成了若干个互不相关的联通块，你只需把这些连通块的贡献相加。

而这些连通块基本上都是某个点的子树，除了 lca 的子树外的所有节点构成的连通块，这些都可以用换根 dp 简单求出，然后对树重链剖分一下，对每个点维护轻子树的贡献和，查询的时候直接从重链往上跳即可。

还有一个做法是直接考虑点边容斥，算出包含每个点和每条边的连通块个数，这部分的 dp 与上面是类似的，而且查询的部分更好写，只需维护到根的贡献前缀和。

F. Double 11

首先，对于每个种类，影响其贡献的只有被分到的数总和 \(s_i\) 和个数 \(l_i\)，考虑如果我们确定了这二者该怎么确定 \(k_i\)，你发现我们要在 \(\sum k_is_i=1\) 的条件下最小化 \(\sqrt {\sum \frac{l_i}{k_i}}\)。

直接上柯西，变成 \((\sum k_is_i)(\sum \frac{l_i}{k_i}) \ge (\sum \sqrt {s_il_i} )^2\)，就得到最优解为 $\sum \sqrt {s_il_i} $，接着，如果确定区间长度，那我们肯定是把小的数分到大的系数中，于是每次肯定选择的是连续的一段区间，这样就可以 dp 了。

一股神秘的力量让你感知到这个东西有凸性，先上一手 wqs 二分把选 \(k\) 的限制取消，接着考虑转移函数的性质，这种根号里面带乘积的东西一看就很有单调性，例如某个决策单调性的典题，然后上二分栈优化一下就做完了。

G. Expanding Array

先考虑 xor，你会发现一直对相邻的做 xor 就会把整个序列变成带有 \(a_i \oplus a_{i+1}\)，且原先的 \(a_i\)、\(a_{i+1}\) 和这个数都有相邻的位置。

接着是 or 和 and，由上述结论不难得到 \(a_i\) 和 \(a_{i+1}\) 任意 or、and 和 xor 的八种取值都能得到，于是做完了。

H. Friendship is Magic

花题，不碰。

I. Good Partitions

直接枚举是不好的，考虑一个方案不合法当且仅当某个块里包含一个下降段，那我们不妨把所有下降段都拿出来，然后对选择的方案作若干限制。如果有一个 \((x,x+1)\) 的下降段，那么最终方案只能是 x 的因子。

更好的一点是每次更改数列中的数只会有 \(O(1)\) 个段变化，且枚举一个数所有因子并进行更新是可以接受的，你只要每次操作都更新周围的连续段然后查有多少数满足目前所有的限制即可。

J. Grand Prix of Ballance

按照题意模拟即可。

K. Magical Set

先图论建模，把一个点向他所有点连边，操作相当于有若干个点上有棋子，每次选一个点上的棋子然后往前推一步。可以观察到一个性质：每次我们一定只减少一个质因子，否则慢慢减少或让挡住的棋子走对应步一定不劣。

接着似乎没办法做了，因为你好像没法给这个过程找一个合理的贪心，那不妨直接考虑终态，每个棋子移动到了子 DAG 内的某个节点，我们建二分图，用匹配描述这种关系。

但是我们能直接跑网络流吗？棋子的行走合法性是不是有影响？注意到棋子的编号不同其实对最终答案是没有影响的，因此如果冲突了交换使其冲突的棋子，答案不变且合法，因此可以建图跑最大费用流。

L. Recover Statistics

输出 50 个 A，45 个 B，4 个 C 和一个 1e9。

M. Two Convex Holes

计算几何，哈哈哈，我不做。