2019-04-10 15:25 已编辑清华大学数据挖掘

关注

【题解】牛客练习赛42

A. 字符串

题目分析

显然，我们要求的答案是 $(\texttt{LCP}(A[l,r],B[l,r]) +1) \times ( \texttt{LCS}(A[l,r],B[l,r]) +1)-1$ 。

那么成为答案的那个区间一定是连续的一段A,B两串相等的子串。否则，若我们选择的不是连续的A,B相等的子串，那么我们可以让选择现在选择区间左右两边相等段更长的那个那段，使答案单调不劣。

B. SHTMYCBDFTT

题目大意

给定一个序列，求一个子串，使得数字的异或和加上所有的数字最大

题目分析

根据异或的定义，可以得到： $b \oplus c \ge b-c$ ，原因是：

$\begin{cases} 1 \oplus 1=0 & 1-1=0 \\\\ 1 \oplus 0=1 & 1-0=1 \\\\ 0 \oplus 1=1 & 0-1=-1 \\\\ 0 \oplus 0=0 & 0-0=0 \end{cases}$

设当前集合 $S$ 的和为 $a$ ，异或和为 $b$ ，有一个元素 $c$ 没有添加

因为 $a+c+(b \oplus c) \ge a+b$ ，所以还可以添加元素 $c$ 进入集合，所以 $S$ 应该是全集

C. 出题的诀窍

题目大意

给定一个二维数组 $\{A_{M,N}\}$ ，求：

$\sum \limits_{i_1=1}^{N} \sum \limits_{i_2=1}^{N} \dots \sum \limits_{i_M=1}^{N} \textbf{SUM} ( A_{1,i_1},A_{2,i_2}, \dots ,A_{M,i_M} ) \pmod {1000000007}$

其中 $\textbf{SUM}(\text{一个序列})$ 表示这个序列中所有不同的数的和，相当于先 $\bf sort,unique$ 再求和

其中 $1 \le n,m \le 2000, 0 \le A_{i,j} \le 10^9$

题目分析

分类考虑所有的权值，对于某个权值，相当于求有多少个选法使得至少选择其中的一个

考虑用总方案减去不合法的，于是就做完了

D. 序列上问题

题目大意

请你求出一个 $1$ ~ $N$ 的排列，使得它正好有 $K$ 个逆序对。

由于存在很多种这样的排列，所以要求出字典序最大的排列。

因为排列可能很长，所以你只用输出**类似于将这个排列放到 $N+1$ 进制下的值**，即 $\sum \limits _{i=1}^{N} p[i]*(N+1)^i \mod \ 10^9+7$ ，其中 $p$ 是你求出的排列。

题目分析

观察字典序最大的排列，发现由四段组成：

第一段是一段从 $N$ 开始的连续下降序列（也可能没有）。
第二段是一个单独的数字。
第三段是一段从 $1$ 开始的连续上升序列。
第四段的开头是第三段的结尾 $+2$ ，略过的数字正好是第二段。

可以二分出第二段那个数字是多少，然后其它三段都是数列求和。

E. 热爆了

题目大意

给定一棵树，点有权值，有 $q$ 次询问，每次给定 $l,r$ ，求所有点权在 $[l,r]$ 之内的点所构成的斯坦纳树的大小（即构成的最小连通块中点的个数）

其中 $1 \leq n \leq 4 \times 10 ^ { 5 } , 1 \leq q \leq 3 \times 10 ^ { 6 } , 1 \leq a _ { i } \leq 10 ^ { 9 } , 1 \leq l \leq r \leq 10 ^ { 9 }$

题目分析

首先问题可以转化为：求有多少个点，它的子树中至少有一个点的权值都在 $[l,r]$ 之间，那么这个的个数减去斯坦纳树的根节点的深度后再加一就是答案了

对于斯坦纳树的根节点，显然就是权值在 $[l,r]$ 中的 $dfs$ 序最小的那个点和 $dfs$ 序最大的那个点的 $lca$

那么现在只考虑计算前者，显然这个答案等于总点数减去有多少个点使得所有子树中的点的权值都在 $(-\infty,l) \cup (r,\infty)$ 之间

首先可以通过离散化使得所有点的权值互不相同，下文只考虑计算前者的个数

对于一个点 $u$ ，如何判断它能对答案产生影响呢？

把所有以 $u$ 为根的子树中所有的点的权值都拿出来，然后从小到大排序，假设是 $a_1,a_2, \dots, a_k$ ，那么它会对答案产生贡献，当且仅当存在 $x,x+1$ ，满足 $a_x \le l-1$ 且 $r+1 \le a_{x+1}$

显然如果存在的话，那就是唯一的

如果可以对于所有的点 $u$ ，把所有相邻的 $(a_x,a_{x+1})$ 作为一个二元组存储起来，那么就可以在最后扫一遍进行更新答案

特别的，对于 $a_1,a_k$ ，需要分别加入 $(-\infty,a_1),(a_k,\infty)$ 这两个二元组

换句话说，这实际上是要生成一些二维平面上的点，然后数一个矩形内的点的个数，这个矩形是以 $(l-1,r+1)$ 为右下角，左上角为 $(-\infty,\infty)$ 的

那么现在问题就剩下了如果把所有的点搞出来，直接搞是不行的，点数在 $O(n^2)$ 左右

发现有很多点都是重复的，于是可以用一个三元组 $(x,y,w)$ 来表示点 $(x,y)$ 出现了 $w$ 次，然后对于每一个点，用线段树维护所有的点的权值

~~这一段可以忽略掉~~

考虑启发式合并，用数据结构维护所有子树的排序后的结果，那么枚举点 $u$ ，然后枚举它的所有儿子，每次把较小的一个暴力拆解，然后一次添加进去，用一个 $set$ 之类的维护排序后的结果就行，更新的话就把左右两个相邻的值进行更新，最后要打上一个集体加一的标记，显然每次插入最多会让平面上的点的个数多一个，因此分析可以得知点数是在 $O(n \log n)$ 范围内

考虑线段树合并，用标记 $T$ 维护所有在子树中产生的点应该添加 $T$ 次，在线段树合并的时候进行标记下放，每次下放的时候用左区间的最大值和右区间的最小值和当前区间的标记来添加一个新的点 $(max,min,T)$

最后处理完所有的 $O(n \log n)$ 个点后，进行二维数点即可

时间复杂度： $O(n \log^2n+Q (\log n+\log Q))$

强制在线的话就套个***树进行二维数点即可

F. 旅行

题目大意

给定一棵树和树上的一些点集，多次询问一个点到某个点集的距离的最小值。

题目分析

我们不妨对每个点集建立虚树，那就相当于从虚树上找到离询问点最近的那个点，再加上虚树上这个点到询问点集中的点的距离的最小值。

那么现在的问题就是如何找到虚树里询问点最近的那个点。

首先，如果询问点不在虚树根的这个子树里，那么虚树的根就是我们要找的那个点，否则肯定就是这种情况：

假设A,B两点是虚树上的相邻的点，C是我们的询问点。

那么我们要找的点肯定是A,B中的一个点。

考虑我们怎么找A点，考虑A点有哪些限制。

A点的DFS序小于C点。
A点是第一个子树包含C的点。

那么对于第一个限制，我们可以直接二分来确定A点的大致范围，对于第二个限制，我们可以用线段树维护每个点

子树内所包含点的DFS序的最大值，然后线段树维护区间最大值，在线段树上二分就能找到A了。

找到A了以后找B的方法也就很简单了，我们对虚树的每个点开个map，若存在虚边 $x \rightarrow y$ ，且原树上x到y路径上的第一个点是z，那么我们令 $mp[x][z]=y$ 。然后我们通过倍增找到 $A \rightarrow C$ 路径上的第一个点 $D$ ，然后查 $mp[A][D]$ 就是B了。