NOI 2023 题解

Copper Loser 的题解……

Day1 T1 方格染色

有一个 \(n\times m\) 的网格，有 \(Q\) 次操作，每次形如有三种：将 \((x_i+j,y_i)\)/\((x_i,y_i+j)\)/\((x_i+j,y_i+j)\) 染色，其中 \(j=0,1\dots L_i-1\)。 第三种操作至多只有 \(5\) 次，问之中有多少个格子被染过色。

扫描线板子题，首先令 \(ans=\sum\limits_{i=1}^QL_i\)，然后考虑如何去掉被重复染色的部分。
对于横线与竖线的，离散化之后使用扫描线求值即可。
由于斜线之后 \(O(1)\) 条，可以将每条斜线和所有其他线的交点算出来，然后去重即可。
时间复杂度 \(O(Q\log n)\)。

Day1 T2 桂花树

给定一棵有 \(n\) 个节点的树 \(T\)，保证一个节点的父亲编号小于它的编号。问有多少个有 \(n+m\) 的节点的树 \(T'\)，满足对于所有 \(1\le i<j\le n\) \(i,j\) 在 \(T\) 和 \(T'\) 上的最近公共祖先相同，对于所有 \(1\le i<j\le n+m\)，\(i\) 和 \(j\) 的最近公共祖先编号 \(\le \max(i,j)+k\)。

对于第一条限制，就确定了 \(T'\) 上 \(1,2\dots n\) 形成的虚树就是 \(T\)。

我们考虑从 \(T'\) 中逐个删除节点得到 \(T\) 的过程。

考虑特殊情况 \(k=0\)，则对于当前最大的节点 \(u\)，不存在 \(1\le i,j<u\)，\(i,j\) 的最近公共祖先为 \(u\)。这也就意味着 \(u\) 至多只有一棵子树，所以可以直接将这个点删去。
反转这个过程，也就意味这我们可以从小到大把节点插在一条树边上，或者挂在一个节点下面，成为它的儿子。假设当前大小为 \(siz\)，则一共有 \(2\times siz-1\) 种方案，所以这种情况的答案就是 \(\prod\limits_{i=1}^m(2n+2i-3)\)，可以直接 \(O(m)\) 计算。

这给了我们一个想法，对于当前要插入的节点其他的节点会是完全相同的，这也就意味着答案可能和 \(T\) 的形态无关，实际上确实是这样的。

考虑回到一般情况 \(k=10\)，仍然考虑从大到小删除，考虑当前最大的节点 \(u\)，由于限制被放宽了，所以它可能会存在若干个儿子。但是，由于公共祖先编号要 \(\le \max(i,j)+k\)，也就意味着它至多只有一个儿子的子树中存在编号 \(<u-k\) 的节点。那么，我们先跳过这个节点的删除，接着删除比它小的节点，由于上面的那一条限制，在删除到某一个编号 \(v \ge u-k\) 的节点时，\(u\) 只剩下一个儿子了，也就可以把 \(u\) 删除了。所以我们考虑在删除 \(v\) 的过程中同时删除掉 \(u\)。

不难发现 \(u\) 都会对应唯一的 \(v\)，\(v\) 也至多只能对应一个 \(u\)。

考虑反过来加入的过程，加入一个节点 \(u\) 时，可能会将一个 \(\le u+k\) 的节点作为父亲捆绑加入，而这种情况下，这一对点只能是放在一条树边上的。

设计 DP 状态 \(f_{i,S}\) 表示当前要加入 \(n+i\) 号节点，在 \(n+i\sim n+i+k-1\) 中已经被加入了的节点集合为 \(S\)。则最终的答案就是 \(f_{m+1,\varnothing}\)。
考虑转移：
如果 \(n+i\in S\)，说明 \(n+i\) 号节点已经被加入了，所以直接跳过，\(f_{i+1,S\setminus \{i\}}\gets f_{i,S}\)。
否则，我们可以按照正常的方式转移 \(n+i\)，也就是 \(f_{i+1,S}\gets f_{i,S}\times [2\times (n+i-1+|S|)-1]\)。
或者可以捆绑一个 \(v\in ([n+i+1,n+i+k]\cap \mathbb{N})\setminus S\) 的节点一起加入，转移为 \(f_{i+1,S\cup {v}}\gets f_{i,S}\times (n+i-1+|S|-1)\)。

时间复杂度 \(O(mk2^k)\)。

Day1 T3 深搜

一棵生成树 \(T\)，以及一个非树边边集 \(E\)，给定若干个关键点，问有多少个 \(E\) 的子集 \(E'\)，使得存在关键点 \(u\)，使得在 \(T\) 中加入 \(E'\) 中的所有边得到的图，\(T\) 可以是一个以 \(u\) 为根的 dfs 树。

是 dfs 树，也就意味着 \(E'\) 中所有的边都是返祖边