20250713-飞鹰班夏令营-总结

知识点：LCA（最近公共祖先）

定义：一棵树上两点的公共祖先中，离根节点最远的那个。

求解方法：

1.朴素算法：

每次找深度较大的那个点，让它往上跳，若两点深度相同则一起向上跳，最终第一次相遇的节点就是它们的最近公共祖先。（时间复杂度为 $O(n*q)$，每次查询的复杂度为 $O(n)$）。

2.倍增法：

朴素算法的改进算法。将朴素算法中“走”的步骤转化为“跳”。

预处理出每个节点的第 $ 2^i$ 个祖先，使得每个节点一定能向上跳到它的某个祖先，因为任何数必定能表示为若干个2的整数次幂相加的形式。预处理数组的递推公式为：$ fa[x][i]=fa[[x][i-1]][i-1] $ ，即从x跳了 $ 2^{i-1} $步到达祖先 $ y$，再从 $ y$ 跳 $ 2^{i-1} $ 步到达 $ z $ ，此时便已跳了 $ 2^i $ 步。

“跳”的时候，先将深度较大的点x跳到与另一个点y相同的深度，再同步向上跳，与朴素算法相同，区别在于一次可以向上走多个祖先。当两点已经深度相同，此时最多向上跳 $ log_2 n $ 次便能到达根节点。从 $ x , y$ 出发，从 $ i=log_2 n $ 开始，每次试着向上跳，若 $ f[x][i] ≠ f[y][i] $，则两点都往上跳，以确保不会跳过头，当循环结束时，两点必定是它们最初的最近公共祖先的儿子节点，求解完毕。

测试：

T1：

键盘输入一个高精度的正整数 n（不超过 250 位），去掉其中任意 k 个数字后剩下的数字按原左右次序将组成一个新的非负整数。编程对给定的 n 和 k，寻找一种方案使得剩下的数字组成的新数最小。（注意：去掉若干数字后剩下的数可以存在前导零，而输出时不要输出前导零）

正解：

1.每次从最高位开始，找到第一个比下一位大的数，将其删去，若找不到而还要删x个，则将后x位删去，最后输出。

2.每次找一个尽可能小的数，使其前面所有比它大的数都可以被删去，删去其前面所有比它大的数。

得分：10

原因：采用思路1，但并没有每次从最高位开始，而是继续往后找，且没有正确处理0的情况。

T2：

给定 n,k 和一个长度为 n 的序列，求最长的最大值最小值相差不超过 k 的子段。$ 0≤k≤2×10^9，1≤n≤3×10^6，1≤|x|,|a_i|≤2×10^9) $

正解：

采用双指针（尺取法），初始 $ i=1,j=1$，i表示序列的头节点，$ j$ 表示尾节点，循环时 $ j$ 不断增加，若此时序列不符合题目要求，则使 $ i$ 不断增加，直到序列符合条件或长度为1为止，并记录每次循环中序列的长度，取最大值即为 $ ans$。在循环中维护两个单调队列，记录当前序列中的最大值和最小值进行判断。

得分：20

原因：采用双指针+ST表，时间复杂度 $ O(nlog_2n) $，超时。

T3：

给定一个长度为 $ n$ 的序列 $ a$，要求支持如下三个操作：

1.给定区间 $ [l,r]$，将区间内每个数都修改为 $ x$。

2.给定区间 $ [l,r]$，将区间内每个数都加上 $ x$。

3.给定区间 $ [l,r]$，求区间内的最大值。

$ 1≤n,q≤10^6 ,1≤l,r≤n , 0≤|x|,|a_i|≤10^9$

正解：在线段树的基础上，设置两个tag，一个记录增加，一个记录修改，对于修改和增加的先后，可以这样处理：

·若先增加，再增加，则增加的tag累加即可

·若先增加，再修改，则增加的tag记为0，修改的tag=设定值即可，因为修改操作将增加操作覆盖了

·若先修改，再增加，则修改的tag=设定值，增加的tag=设定值即可

·若先修改，再修改，则修改的tag=后设定的值即可，因为后面的操作将前面的操作覆盖了

注意最大值和修改tag应设为负无穷，因为 $ a_i$ 可以为 $ -10^9$。

得分：0

原因，没想到如何操作tag，遂使用暴力，但因未知原因答案错误，使得原本预期的20分都没拿到。

T4（没做）：

无向连通图  $ G$有 $ n$个点，$ n-1$条边。点从 $ 1$ 到 $ n$ 依次编号,编号为 $ i$ 的点的权值为 $ w_i$，每条边的长度均为 1。图上两点 $ (u,v)$ 的距离定义为 $ u$ 点到 $ v$ 点的最短距离。对于图 G 上的点对 $(u,v)$ ,若它们的距离为 $ 2$，则它们之间会产生 $ w_u\times w_v$ 的联合权值。

请问图 $G$ 上所有可产生联合权值的有序点对中，联合权值最大的是多少？所有联合权值之和是多少？

正解：

分类讨论：

·一个节点的两个儿子节点

·一个节点与其孙子节点

对整棵树进行dfs，求出其 $ max(w_p\times max(w[孙子节点])，max(w_{son_i}\times w_{son_j}))$，即为最大联合权值，将 $max$ 改为求和再 $×2$ 即为联合权值之和（ $(u,v)$ 和 $(v,u)$ 需记两次）。

正在渲染内容...