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了，写完感觉神清气爽

• 分类：计算几何

• 题意：给定一个二维坐标系里的简单多边形，$q$ 组询问，每次给定一条垂直于 $x$ 轴的直线，求出根据这条直线翻折多边形后的面积

• 题解：

• 考虑一维线段的翻折，即总长度减去位于翻折线左侧和中点左侧的长度，加上位于翻折线左侧中点右侧的长度

• 一维的做法可以利用微分的思想拓展到二维平面，对于每个端点找出水平线段，根据中点的连线将多边形分成左右两部分，之后扫一遍求积分即可

• comment：微分依然停留在能看懂，做不出的阶段啊QAQ

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

• 题意：给你一棵$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：完美利用了树的重心性质。

• 分类：组合数学，容斥。

• 题意：$n$个人，选出一个非空子集，第$i$个人要求如果他被选出来那么子集的大小必须在$[l_i,r_i]$，同时有$m$个限制，形如第$a_i$个人和第$b_i$个人不能同时被选，问合法的选择方案数量，对$998244353$取模。$(1 \le n \le 3 \cdot 10^5, 0 \le m \le \min(20, \dfrac{n(n-1)}{2}))$

• 题解：如果没有第二个限制，只需要对所有区间差分一下然后枚举人数就完成了。因此我们考虑使用容斥进行计算违反了第二个限制的方案并将其减去。设$f_{S}$为至少包含状态$S$中的矛盾的方案数，其中$S$是一个二进制数，最终答案即为$$\sum_{S=0}^{2^m-1}(-1)^{\operatorname{popcount}(S)}f_S$$我们设不考虑第二个限制，允许自己所在队伍有$i$个人的数量为$c_i$；状态为$S$时所包含的人数为$cnt_S$，他们的区间交集为$[L_S,R_S]$那么有$$f_S=\sum_{i=L_S}^{R_S}\binom{n-cnt_S}{i}$$其中$cnt_S$不超过$2$m，因此我们在$O(nm)$的时间内预处理出$$g_{i,j}=\binom{n-i}{j}$$的前缀和，从而$O(1)$得到$f_S$。最后用总方案数减去不合法方案数即可，总时间复杂度为$O(nm+m2^m)$。

• comment：非常巧妙地在第一个限制的基础上套用容斥解决了第二个限制。

• 分类：树形dp。

• 题意：给定一棵$n$个节点的树，每个节点有两个权值$a_i,b_i$，要求将树分为数条互不相交的链，每条边都必须被划分，点可以重复，且每条链的$a_i$单调（非严格单增或单减），求所有链的$b_i$之和的最小值。$(n \le 2 \times 10^5)$

• 题解：先考虑所有边都各自成一条链，然后再对边进行合并从而减少答案。考虑给边进行定向，由$a_i$小的点指向大的点；如果两个点$a_i$相同那么边的方向任意，需要在后续dp过程中进行讨论。设$f_i$为以$i$为根的子树中若$i$与它父亲的边向下所能减少的最大权值，$g_i$为以$i$为根的子树中若$i$与它父亲的边向上所能减少的最大权值，$S_i$为节点$i$的子节点集合，那么有$$f_i=\max_{S\in S_i}(\sum_{j\in S}f_j+\sum_{j \notin S \operatorname{and} j \in S_i}g_j+ b_i \cdot \min(|S|,|S_i|-|S|+1))$$ $$g_i=\max_{S\in S_i}(\sum_{j\in S}f_j+\sum_{j \notin S \operatorname{and} j \in S_i}g_j+ b_i \cdot \min(|S|+1,|S_i|-|S|))$$ 前面的式子不好处理，我们可以化简得到$$\sum_{j\in S}f_j+\sum_{j \notin S \operatorname{and} j \in S_i}g_j=\sum_{j\in S_i}g_j + \sum_{j \in S}(f_j-g_j)$$ 前者为定值，我们可以将子节点的$f_j-g_j$从大到小排序，设为$sum_i$，同时设$cnt_i$为节点$i$的子节点数，则有$$f_i=\sum_{j\in S_i}g_j+max_{j=0}^{cnt_i}(sum_j+b_i \cdot \min(j,cnt_i-j+1))$$ $$g_i=\sum_{j\in S_i}g_j+max_{j=0}^{cnt_i}(sum_j+b_i \cdot \min(j+1,cnt_i-j))$$ 最后根节点的答案特判一下，即为$$root_i=\sum_{j\in S_i}g_j+max_{j=0}^{cnt_i}(sum_j+b_i \cdot \min(j,cnt_i-j))$$时间复杂度$O(n \log n)$。

• comment：巧妙的链匹配，回忆并理解了牛客dls那场的树上边覆盖。

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

• codeforces 666 div1

见团队训练。