CVBB ACM Team

2020暑假精选题目

• 分类：线段树， $set$

• 题意：$L \times L$ 的网格平面，其中有 $n$ 的点，每个点在网格的中心。每个点有一个颜色，总共有 $k$ 个颜色，现在求多少个矩形包含了所有 $k$ 种颜色。$n,k \le 2000, L \le 10^9$

• 题解：
  • 首先我们可以枚举矩形的左边和右边所在的 $x$，先固定矩形的左侧边缘 $x_l$，向右侧扫。对于每个点记录 $pre_i$ 为在区间内颜色相同，$y$ 值小于等于自己的点的 $y$ 值；$nxt_i$ 为在区间内颜色相同，$y$ 值大于等于自己的点的 $y$ 值。
  • 考虑先将 $x_l \sim L$ 内部所有点都考虑到。令 $f(i)$ 表示纵坐标为 $i$ 要满足包含 $k$ 个颜色的最低 $y$ 值，显然随着 $i$ 的下降 $f_i$ 是单调不增的，这为下面的操作提供了复杂度的保证。考虑左右侧确定时的答案是多少，$ans = \sum_{i = 0}^{L} (L + 1 - f_i)$，可以用线段树维护 $f_i$ 的和。
  • 现在考虑删除矩形右侧的一列，对于一个点 $i$ 被删除，那么 $pre_i + 1 \sim y_i$ 的点的 $f$ 值显然要和 $nxt_i$ 取最大值，这个也可以用线段树维护，由于 $f_i$ 的单调性，线段树的复杂度是正确的，每次删除后统计答案即可，复杂度 $O(n^2\log(n))$ 。

• comment：写的太容易出bug了，写完感觉神清气爽

• 分类：

• 题意：

• 题解：

• comment：

• 分类：树上问题，树的重心。

• 题意：给你一棵$n$个节点的树，保证$n$为偶数，边权为$1$，问是否存在一个完美匹配，使得两两点之间距离之和恰好等于$k$。$(n \le 10^5, k \le n^2)$

• 题解：我们考虑一条边，它将整棵树分为两部棵子树，大小分别为$x$和$n-x$，两者奇偶性相同。所有两点位于两侧的匹配都会经过这条边，而其它匹配一定是在各自子树内完成的，因此这条边被经过的次数的奇偶性一定和$x$相同，同时也有一个显然的上界$\min(x,n-x)$，设该边贡献的权值为$a$，则有$(x \mod 2 )\le a \le \min(x, n - x)$。

• 我们以树的重心为根，那么除了根节点外，以每个节点为根的子树都小于另一部分，即$\min(x,n-x)=x$，因此对于每一条边我们可以得到公式$\sum (siz_i\mod 2) \le k \le \sum siz_i$，且$k$的奇偶性和$\sum siz_i$相同。下面通过构造证明这个必要条件也是充分的。

• 将根节点的每个子树中的点都和另一个子树匹配，总权值就是$\sum siz_i$，因为重心为根，每个子树大小不超过总体的一半，因此该匹配是存在的。现在我们可以通过如下的方案将总权值减少到不小于$\sum (siz_i\mod 2)$的任意与$\sum siz_i$奇偶性相同的值：

• 我们每次考虑根节点的各个子树，每次都考虑未匹配节点数最多的那个子树，我们每次将该子树中的两个点$x,y$进行匹配（而不是像上述所说各自匹配到根节点另外子树的节点），对最终权值的减少量为$2 \cdot dep_{\operatorname{lca}(x,y)}$，因此我们只需不断地寻找两个合适的点进行匹配，使得最终权值不断减少直到$k$。最后，因为我们每次都相当于让最大子树的节点数减少两个，因此根节点一直都是重心，最后只需将剩余点按dfn序排序，贪心地令$i$和$i+\frac{|v|}{2}$匹配即可（类似2020牛客第二场那题）。

• 具体实现过程我们只需要开个大根堆维护最大的子树，再开个set维护每个子树中存在一个及以上儿子的节点（不然没办法让它成为$\operatorname{lca}$）及其深度，并且每次优先选择最深的点删除即可。

• comment：完美利用了树的重心性质。

• 2020.08.29 Namomo Fish(Easy) Round 1
• 2020.08.29 AtCoder Beginner Contest 177