ARC162 题解

A.Ekiden Race (450)

题意：\(n\) 个人在进行往返跑比赛，其中第 \(i\) 个人在回程前的排名是 \(i\)，总排名是 \(p_i\)，问有多少个人可能成为回程中跑得最快的人？

如果对于 \(i\)，存在某个 \(j>i\)，使得 \(p_j<p_i\)，那么 \(j\) 在回程途中超过了 \(i\)，\(i\) 肯定不能成为答案，否则一定可以。所以就是 \(p\) 的后缀 \(\min\) 个数。

时间复杂度 \(\mathcal O(n)\)。

Code

B.Insertion Sort 2 (1100)

题目相当于每次从序列中拿出相邻两个数，再插到任意一个位置。一个显然的无解情况是逆序对个数为奇数，否则可以从小到大找出 \(i\) 的位置，将它和后一个数插在 \(i-1\) 后，如果 \(i\) 就在最后则把它往前挪一格。

容易发现最后两个数无法操作，但如果逆序对个数为偶数，则它们已经排好序了。所以不用求逆序对个数，直接对 \(1 \sim n-2\) 做一遍看是否已经有序。

时间复杂度 \(\mathcal O(n^2)\)。

Code

C.Mex Game on Tree (1650)

考虑 Alice 的必胜情况。

如果存在一个所有数都已经确定的子树，它的 \(\operatorname{mex}\) 为 \(k\)，那么 Alice 必胜。

如果存在一个子树，只有一个数未确定，且可以通过填一个数使得子树 \(\operatorname{mex}\) 为 \(k\)，则 Alice 必胜。

否则不存在前两种情况，Bob 可以在每次 Alice 填完一个节点后将与其最近的空节点填上 \(k\)（这里最近的空节点指的是拥有与 Alice 节点的最深 lca），那么它们 lca 以上的节点就废了。

时间复杂度 \(\mathcal O(n^2)\)。

Code

D.Smallest Vertices (2550)

先考虑一个弱化问题：给定根和每个点的儿子个数，如何求其生成树个数？

有了根和儿子个数，我们就可以知道每个点的度数 \(deg_i\)，而每个点都会在生成树的 prufer 序列上出现 \(deg_i-1\) 次，所以生成树个数就是 \(\binom{n-2}{deg_1-1,\cdots,deg_n-1}\)。

之后对每个点 \(i\)，求出 \(i\) 作为好节点的生成树个数。

首先应该从 \(\geq i\) 的节点中选出一个集合 \(S\)（需保证 \(i \in S\)），使得 \(\sum_{i\in S}d_i=|S|-1\)，则 \(i\) 子树内的方案数为 \(\dfrac{(|S|-2)!d_i}{\prod\limits_{i\in S}d_i!}\)，子树外的方案数为 \(\dfrac{(n-|S|-1)!d_1}{\prod\limits_{i\notin S}d_i!}\)，令 \(K=\prod\limits_{i=1}^{n}d_i!\)，则总方案数为 \(\frac{1}{K}(|S|-2)!d_i(n-|S|-1)!d_1\)，只与 \(i\) 和 \(|S|\) 有关。

所以设 \(f_{i,j,k}\) 表示 \(\geq i\) 的数中选出 \(j\) 个数，它们 \(d\) 的和为 \(k\) 的方案数，计算答案时需要保证 \(k=j-1\)。注意 \(|S|=1\) 和 \(i=1\) 时需要特判，\(1\) 的子树内需要包含所有点。

时间复杂度 \(\mathcal O(n^3)\)。

Code

E.Strange Constraints (2800)

*2800？*2000！

设 \(c_i\) 为 \(B\) 中 \(i\) 的出现次数，则要求 \(c_i \leq A_i,c_{B_i} \leq A_i,\sum\limits_{i=1}^{n} c_i=n\)。

假设现在某个数的 \(c\) 值为 \(x\)，那么由于第一个要求，这个数的 \(A_i\) 必须 \(\geq x\)，从所有 \(A_i \geq x\) 的数 \(i\) 中挑一个分配给它就行了。

之后要把这 \(x\) 个数都填到 \(B\) 里面，但是由于第二个条件，只能填在那些 \(A_i \geq x\) 的位置 \(i\) 上，从所有 \(A_i \geq x\) 的位置中选 \(x\) 个位置给它就行了。

注意到在之后的过程中，这些已经被分配的数和已经被分配的位置不能再选了，所以按 \(c\) 从大到小考虑，这样决策就有包含性。

设 \(f_{i,j,k}\) 表示目前已经考虑了 \(\geq i\) 的 \(c\)，其中有 \(j\) 个数的 \(c\) 值 \(\geq i\)，它们的 \(c\) 的和为 \(k\)。转移时就枚举有 \(l\) 个数的 \(c\) 值为 \(i\)，\(f_{i+1,j,k} \times \binom{cnt-j}{l} \times \binom{cnt-k}{i,i,\cdots,i} \rightarrow f_{i,j+l,k+il}\)，其中 \(cnt\) 为 \(A_{pos} \geq i\) 的 \(pos\) 的个数，\(\binom{cnt-k}{i,i,\cdots,i}\) 下面有 \(l\) 个 \(i\)。

复杂度看似是 \(\mathcal O(n^4)\) 的，实际上合法状态数和转移数量少，大概上界是 \(n^3\sum\limits_{i=1}^{n}\frac{1}{i^2}\)，故复杂度实际为 \(\mathcal O(n^3)\)。

Code

F.Montage (3200)

考虑这个限制等价于什么：对于任意 \(1 \leq a < c \leq n,1 \leq b < d \leq m\)，若 \(A_{a,b}=A_{c,d}=1\)，则 \(A_{a,c}=A_{c,d}=1\)。

将其表现在网格图上，若存在两个点都是 \(1\)，其中一个在另一个左上角，则它们围成的矩形里必须都是 \(1\)。所以合法的 \(A\) 可以看作有若干个全 \(1\) 矩形并起来，其它全是 \(0\)，并且这些全 \(1\) 矩形大概沿左下至右上分布。

形式化地来说，将空行和空列剔除掉之后，每行的 \(1\) 会形成一段连续区间 \([l_i,r_i]\)，并且有 \(l_{i+1}\leq l_i,r_{i+1} \leq r_i\)（即从 \(n\) 到 \(1\) 递增）。

（引用官方题解的图）

于是就可以 \(dp\) 了，设 \(f_{i,l,r}\) 表示第 \(i\) 行的 \(1\) 区间为 \([l,r]\)，转移用前缀和优化，需要保证没有空行空列。计算答案时再枚举有多少空行空列插进去。时间复杂度 \(\mathcal O(nm^2)\)。

Code