A. ABC Legacy

记 $c_A, c_B, c_C$ 分别表示每个字母的出现次数, $f_{AB}, f_{AC}, f_{BC}$ 表示每种匹配的出现次数, 那么显然有 $$ \begin{cases} c_A = f_{AB}+f_{AC}\\ c_B = f_{AB}+f_{BC}\\ c_C = f_{AC}+f_{BC}\\ c_A+c_B+c_C = 2n \end{cases} $$ 于是显然可以解出 $f_{AB}=n-c_C, f_{AC}=n-c_B, f_{BC}=n-c{A}$, 即每种匹配的数量是固定的. 考虑所有含有 B 的匹配, 注意到最后还要匹配 AC 型的pattern, 所以我们在选择匹配 B* 的时候, 肯定会尽量选择后缀一段 A 和前缀一段 C, 那么匹配的时候找到第一个能匹配的 B 显然是最优的. 如果最后配不出来, 就是无解.

B. New Queries On Segment Deluxe

留坑

C. Counting Phenomenal Arrays

首先说一下我们在现场的做法: 不妨设 $a_1\leq a_2 \leq \cdots \leq a_n$, 只计数有序的序列数量, 乘上对应的系数即可.

注意到 $a_1a_2\cdots a_n = a_1+a_2+\cdots+a_n \leq na_n $, 所以我们有 $a_1a_2\cdots a_{n-1} \leq n$, 即我们选出的数中, 去掉最大的数, 乘积不能超过 $n$.

而另一方面, 当我们确定了前 $n-1$ 个数后, 我们可以通过解方程 $Px = S + x$ 来求出 $x$ 的值, 因此我们不难设计出一个 dp: 设 $f_{i,j,\pi,\sigma}$ 表示已经填了 $i$ 个数, 上一次填的是 $j$, 目前乘积是 $\pi$, 总和是 $\sigma$ 的贡献总和.

但上述 dp 的复杂度过高, 我们完全无法接受. 但是注意到大多数状态是完全不可达的, 因此我们不妨将上述过程写成一个搜索的形式, 只搜索可能达到的状态. 通过暴力实现搜索, 我们可以轻松通过 $n \leq 1000$ 的数据, 但仍然无法通过本题.

注意到我们可以添加许多剪枝. 其中最重要的一个是, 我们考察当前填出来的状态, 并通过解方程解出此时最后一个数能填啥. 如果这个解出来的值已经小于目前的 $j$, 那么再填下去就没有意义了, 我们直接认为不合法. 同时, 再添加若干个不同的优化(例如不需要去枚举1的数量,最后算答案再计算), 我们便可以轻松通过本题.

上述算法看起来不太科学, 通过地比较侥幸, 那么有没有更靠谱的算法? 当然是有的. 我们还是计算有序序列的数量, 但这次我们规定 $a_1>1$. 我们不妨设 $\varphi(a) = \sum(a) - \prod(a)$, 则我们最终要求 $\varphi(a)=0$. 但注意到, 若 $b_i > 2$, 则必有 $\varphi(a_1 \cdots a_k) \leq \varphi(a_1 \cdots a_{k+1})$, 而初始时我们有 $\varphi(a_1)=0$, 因此我们只要开始填数, $\varphi$ 值就恒小于等于 $0$, 只能在最后填 $1$ 来补救.

由于一个 $1$ 只能恰好将 $\varphi$ 值加 $1$, 所以显然 $\varphi$ 值不能超过 $n$. 我们仿照上述过程实现一个 dfs, 当我们搜出一个 $b_1,b_2,\cdots,b_k(b_1>2, b_i \leq b_{i+1})$, 其积为 $\pi$, 和为 $\sigma$ 时, 我们有 $\varphi(b) = \pi - \sigma$, 显然我们只有在最后填恰好 $-\varphi(b)$ 个 $1$ 才能让他有可能有贡献, 所以我们任取一个不含 1 的序列, 其只有不超过 1 种方法使得其有贡献. 最后我们添加 $k$ 个 $1$ 的方案数即为 $\binom{k-\varphi(b)}{-\varphi(b)}$, 乘上对应贡献的系数即可.

所有元素大于 1, 且乘积不超过 $n$ 的序列非常的少, 通过暴力打表我们可以验证总的可能状态数可以接受, 且我们每次递归都能找到一个对应的解, 故整个过程的复杂度是有保证的.

D. LIS Counting

留坑

E. Flood Fill

首先注意到, 如果两个块 $A,B$ 是相邻的, 那么我们不可能同时将 $A,B$ 均反色. 因此, 我们的操作相当于选一个互不相邻的联通块集合 $S$, 使得最小化 $\sum_{i\in S}f(i) + \sum_{i \notin S}g(i) = \sum g(n) + \sum_{i \in S} (f(i)-g(i))$, 这是一个二分图最大权独立集问题, 所以直接写个网络流就好了.

F. to Pay Respects

首先注意到, 我们的操作可以分为两类, 一类减小 $r$, 另一类不减小.

对于不减小的那一类, 我们考虑最后一次这样的操作在时刻 $T$, 如果存在 $T_0 < T$ 且 $T_0$ 你没有操作, 那么你把这次操作转移到 $T_0$ 显然更优, 这是因为反正你也不能减小了, 不如先操作让对面增长地慢一些.这说明我们第二类操作一定占据了所有操作的一个前缀. 存在一个显然的贪心, 即考虑每个时刻 $i$ 对答案的贡献 $\Delta_i$, 如果这个时刻你操作, 那么如果对面操作, 你的贡献就是 $(n-i+1) \cdot (p+r)$, 否则是 $(n-i+1) \cdot p$, 这是因为你显然不会让对面有值的时候放过它到后面再操作, 所以只有对面是 $1$ 的时候才有可能减小. 这样我们直接排序并取前 $K$ 大, 时间复杂度为 $O(n \log n+K)$.

事实上, 根据进一步分析, 我们显然会从间断点后取一个 $1$ 的前缀操作, 所以我们可以直接做一个类似双指针一样的操作, 一开始取前 $k$ 个, 每次取后面第一个调整即可. 时间复杂度为 $O(n+K)$.

G. Replace Sort

首先将 $B$ 排序, 随后发现我们替换的时候位置显然是单调的. 设 $f_{i}$ 表示将 $A$ 的前 $i$ 个数排序, 且最后一个数不变的最小代价, $g_{i,j}$ 表示将 $A$ 的前 $i$ 个数排序, 且最后一个数替换成了 $B_j$ 的最小代价, $p(x)$ 表示最大的一个 $k$ 使得 $B_k \leq x$.

转移时, 对于 $f$ 直接枚举前面放没放:

• $f_{i} \leftarrow f_{i-1} (A_{i-1} \leq A_i)$
• $f_i \leftarrow \min_{1 \leq j \leq p(A_i)} g_{i,j}$

对于 $g$, 我们注意到如果前面替换成了 $B_k$, 那么这次一定替换成 $B_{k+1}$, 因为填更大的只会让后面的限制变得更严格, 所以:

• $g_{i,j} \leftarrow f_{i-1} + 1 (A_{i-1} \leq B_j)$
• $g_{i,j} \leftarrow g_{i-1,j-1} + 1$

直接做复杂度显然是 $O(n^2)$ 的, 注意到我们可以使用线段树来优化 $g$ 对 $g$ 的转移与 $g$ 对 $f$ 的转移 (只需要区间取min, 区间求min即可. 平移操作没什么用, 加的1全都是全局加). 总的时间复杂度为 $O(n \log n)$.

H. Werewolves

注意到如果一个联通块有贡献, 那么造成贡献的颜色只有恰好一种, 所以我们可以枚举这种颜色, 然后数有多少个有贡献的联通块, 这可以通过一个简单的树上背包 ( $dp_{i,\delta}$ 表示考虑以 $i$ 为根的子树, $i$ 必须选, 出现次数最多的元素减去总元素为 $\delta$ 的方案数 ), 总的时间复杂度为 $O(n^3)$.

注意到 $\sum_{i=1}^n c_i = n$, 而我们枚举颜色 $i$ 做树上背包的时候, size 显然是不超过 $c_i$ 的, 所以我们只需要做大小不超过 $k$ 的树上背包, 它的时间复杂度是 $O(nk)$ 的, 具体之前我讲杂题的时候讲了就跳过了.jpeg

综上, 总的时间复杂度为 $O(n^2)$

I. Colourful Permutation Sorting

留坑

J. Jason ABC

注意到两次操作是一定够的, 我们设 $f_{c,i}$ 表示 $\sum_{i=1}^n [s_i=c]$, 求最小的 $j$ 使得 $\max_{i \in \Sigma} f_{i,j} \geq n$, 随后两次操作把剩下两种不够的字符补齐即可.

所以只需要特判零次和一次操作. 零次操作显然, 一次操作的话, 我们枚举这种操作的是什么字符, 然后在枚举左端点, 右端点显然是单调的, 于是就稍微维护一下就做完了. 时间复杂度 $O(n)$

K. Amazing Tree

首先注意到第一个元素一定是某一个叶子, 不妨设编号最小的叶子为 $x$, 则我们序列的第一个元素必定为 $x$.

不妨设我们 dfs 时的根为 $r$, $x$ 的唯一邻居为 $y$

1. 若 $r = y$, 则我们在访问完 $x$ 后, 相当于从 $y$ 开始依次遍历每一个子树(除了 $x$), 显然我们还是会走到最小的叶子所在的子树内, 就变成了一个根确定的子问题.
2. 若 $r \ne y$, 则相当于要选择一个 $y$ 的子树, 当作根所在的联通块, 显然我们取最小叶子最大的那个子树当根是最优的, 随后 dfs 的时候, 非最大子树的相当于根已确定, 直接走完所有的子树, 剩下的那一个还是需要做类似的过程确定最优的 $r$

L. Primes and XOR? Nonsense

留坑

M. Many LCS

留坑

N. Max Pair Matching

不妨设 $a_i \leq b_i$, 那么 $w(i,j) = \max(b_i-a_j,a_i-b_j)$. 那么最大匹配的权值就是选出恰好 $n$ 个点当作 $b_i$, 另外 $n$ 个点当作 $a_i$, 最大化他们相减的值. 我们可以假设 $2n$ 个点全都选 $b_i$, 那么把一个 $b_i$ 改为 $a_i$ 的代价即为 $a_i+b_i$, 按照代价排序选 $n$ 个最小的减去就是答案.