JZTXT

AtCoder Regular Contest 162

发布时间 2023-06-19 15:32:41作者: Scintilla06

A

答案即后缀最小值个数。

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

提交记录：Submission #42717665 - AtCoder Regular Contest 162

B

发现操作不改变逆序对个数奇偶性。

逆序对个数为奇数则无解；为偶数则可以直接模拟。

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

提交记录：Submission #42718848 - AtCoder Regular Contest 162

C

如果 Alice 不能一次成功，那 Bob 可以在 Alice 想使得 \(\text{mex} = k\) 的那个子树中填一个 \(k\)。

所以 Alice 必胜当且仅当存在使用至多一次操作就能填满且 \(\text{mex} = k\) 的子树。

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

提交记录：Submission #42720225 - AtCoder Regular Contest 162

D

如果确定了每个点的 \(\deg\)，容易使用 prufer 序列求出生成树个数。

考虑 \(u\) 作为 good 点出现了多少次。枚举 \(u\) 子树中有哪些结点，直接计算即可，这需要背包求出 \(> i\) 的点中取 \(j\) 个，\(\deg\) 和为 \(k\) 的方案数。

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

提交记录：Submission #42729090 - AtCoder Regular Contest 162

E

按照出现次数从大到小填数。

设 \(f_{i, j, k}\) 表示填完出现次数 \(\ge i\) 的数，已经填了 \(j\) 种数，共有 \(k\) 个数的方案数，则转移时可以放的数和位置的个数均已确定，直接枚举并使用多重组合数计算即可。

算算复杂度，发现是 \(\sum_{i = 1} ^ n n \cdot \frac{n}{i} \cdot \frac{n}{i}\)，因为 \(\sum \frac{1}{i^2}\) 是收敛的，所以时间复杂度为 \(\mathcal{O}(n^3)\)。

提交记录：Submission #42738742 - AtCoder Regular Contest 162

F

我感觉还是有点难的吧，不知道为啥大家都觉得简单。

一个观察：假设每行每列均有 \(1\)，则对于 \(1 \le a < c \le n, 1 \le b < d \le m\)，若 \(A_{a, b} = A_{c, d} = 1\)，则对于 \(\forall i \in [a, c], j \in [b, d]\)，均有 \(A_{i, j} = 1\)。

于是 \(1\) 出现的位置可以使用两条从 \((0, 0)\) 到 \((n, m)\)、没有重合边的轮廓线刻画，设 \(f_{i, a, c}\) 表示两条轮廓线走了 \(i\) 步之后横坐标分别为 \(a, c\) 的方案数，转移显然，可以求出所有 \(i \in [0, n], j \in [0, m]\) 的答案，乘上把全为 \(0\) 的行列补上的方案数求和即可得到原问题答案。

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

提交记录：Submission #42741022 - AtCoder Regular Contest 162