算法小站
首页
wiki
新鲜事
文章搜索
网站导航
回忆录
首页
wiki
新鲜事
文章搜索
网站导航
回忆录
登录
注册
算法基础
搜索
数据结构
字符串
数学
图论
动态规划
计算几何
杂项
2026年五月算法竞赛选题(二)
期望,均匀分布,树的直径,莫比乌斯反演,最小链覆盖,树链剖分
[[ slider_text ]]
[[ item.c ]]
0
0
2026年五月算法竞赛选题(二)
发布时间
2026-05-18
作者:
秋千月
来源:
算法小站
树链剖分
莫比乌斯反演
## Codeforces Round 1049 (Div. 2) ### D **[D. A Cruel Segment's Thesis](https://codeforces.com/contest/2140/problem/D)** 给定`n`条线段,用$$[l_i, r_i]$$来描述,一开始都没有标记,如果目前有至少`2`条未被标记的线段 任选两条,把他们标记,并且新增一条标记线段$$[x_k, y_k]$$ 必须满足$$l_i \leqslant x_k \leqslant r_i, \quad l_j \leqslant y_k \leqslant r_j$$ 如果某次操作,剩下落单的,直接标记 求标记线段的长度和,线段长度定义为$$r - l$$ **算法分析** 分为两部分 ```math \text{way1: }(r_i - 2l_i) + (2r_j - l_j) \\ \text{way2: }(r_j - 2l_j) + (2r_i - l_i) ``` 考虑一下什么时候`way2 >= way1`,然后决策哪些线段放左边,哪些线段放右边 放左边的贡献就是$$r_j - 2l_j$$,右边类似 偶数情况就做完了,奇数情况分两种,左边比右边多1,右边比左边多1 针对这两种情况,枚举左边落单的线段,和右边落单的线段,`-(原来的贡献) + (r - l)`来更新答案 ## Codeforces Round 1048 (Div. 1) **[C1. Maple and Tree Beauty (Easy Version)](https://codeforces.com/contest/2138/problem/C1)** 给定`n`个顶点,每个点可以填`0 or 1`,定义字符串,是从根节点到当前节点路径上的字符拼接而成 现在给定`n, K`,要求你填恰好`K`个`0`和`n - K`个`1`,求出所有叶子节点对应的字符串,它们的最长公共子序列长度(不要求连续) **算法分析** 1)最长公共子序列,最大的长度就是`L = mindep(u)` 2)考虑分层来背包,自顶向下,越上面的,越要尽可能把`0`给消耗掉,考虑`dp` 3)同一层的,尽量填相同的,记一下第$$i$$层的节点数`cnt[i]`,$$k$$表示当前用掉了多少个`0` 用可行性`dp`,表示能不能到达这一层 ```math ndp(k) = \max(dp(k)+1, dp(k-cnt_i) + 1) ``` 检查一下`放的 1 和放的 0`有没有超,另外`1, 0`的个数有上界,要设计不合法的状态`-1` 第`i`层的时候,如果`dp(k)`状态可达,那么最长公共子序列长度可以是`i` > hard 版本,$$O(n = 10^5)$$ 实际上这个问题不是一个最大值问题,而是一个**合法性判断**的问题 这样就可以用 **bitset 优化**来求解了 这可以用`bitset 背包`,$$dp(k) = 1$$,表示在当前层$$[1\cdots i-1]$$,存在一种方案,使得恰好用掉了$$k$$个`0` 并且**每一层都是填相同的数**,决策第$$i$$层填$$num_i$$个数,填`0`还是`1` 如果放`1`,那么$$ndp(k) = dp(k)$$ 如果放`0`呢,那么$$ndp(k+num_i) = dp(k)$$,这可以写成$$dp(k) \ll num_i$$ 只不过这个问题有限制,就是`0`的个数不能超过`K`,`1`的个数不能超过`totone` 那么假设枚举有$$k$$个`0`,当前已经考虑过的节点总数是$$sum$$ ```math \displaystyle \begin{cases} 0 \leqslant k \leqslant \min(K, sum) \\ sum - k \leqslant totone \end{cases} ``` 这样得到$$k \in [sum - totone, \min(K, sum)]$$,在这个区间内只要找到一个合法的$$k$$ 当前层`i`就满足,可以用来更新答案 ```bash for (int k = 0; k <= min(sum, K); k++) { ndp[k] = dp[k]; if (dp[k] == 1) ndp[k + num] = 1; } 用 bitset 优化 dp |= (dp << num) ``` ## Codeforces Round 1045 ### D **[D. Sliding Tree](https://codeforces.com/problemset/problem/2134/D)** 给定一棵树,一次操作,选择任意一个`deg >= 3`的点,选定`a, b, c` 以`b`为中心,把`b 中除了 a, c 的,相邻的点`拆下来,接到`c`上 问使得一棵树成为一条链的最小代价,输出你第一次选的`a, b, c` **算法分析** 从直径考虑,抽出直径,如果直径旁有侧枝需要“修剪”,那么修去侧枝的代价是固定的 代价是`cost(u) = u 到 侧枝叶子的距离 dist[u]`,也就是说,需要`dis[u] = |u -> leaf|`这么多操作 才能消除`u`的一条侧枝 归纳,不难发现将树变成一条链的最小代价是$$n - 1 - D$$,其中`D`表示**树的直径** ## 2026“钉耙编程”中国大学生算法设计春季联赛8 ### 1006 **[忠犬PARE公](https://acm.hdu.edu.cn/contest/problem?cid=1204&pid=1006)** 给定两个序列$$a, b$$,求 ```math \displaystyle \sum_{i = 1}^{n} \sum_{j = 1}^{m} \dfrac{\text{lcm}(a_i, b_j)}{\text{gcd}(a_i, b_j)} ``` **算法分析** 比较套路的莫比乌斯反演,原式可以写成 ```math \displaystyle \sum_i \sum_j \dfrac{a_i b_j}{\text{gcd}(a_i, b_j)^2} ``` 枚举$$\text{gcd} = d$$,那么我们要求 ```math \displaystyle \textbf{let } f(d) = \sum_i \sum_j a_i b_j \cdot [\text{gcd}(a_i, b_j) = d] \\ \sum_{d} \dfrac{f(d)}{d^2} ``` 接下来就是**莫比乌斯的套路化简** 枚举$$d$$的倍数,定义 ```math \displaystyle g(d) = \sum_{d \mid d'} f(d') = \left( \sum_{i} a_i [d \mid a_i] \right) \left( \sum_j b_j [d\mid b_j] \right) ``` 那么`for d = 1 to N`,$$g(d)$$可以预处理打表,枚举每一个`d`,枚举$$d$$的倍数 统计一下`cntA(d 的倍数),cntB(d 的倍数)`即可 接着考虑计算$$f(d)$$ ```math \displaystyle f(d) = \sum_{d \mid x} \mu (\dfrac{x}{d}) g(x) ``` 计算$$\sum f(d) / d$$即可 ### 1007 **[向后全速前进](https://acm.hdu.edu.cn/contest/problem?cid=1204&pid=1007)** 有一个长度为$$n$$的序列$$a$$,其中$$a_i$$在$$[l_i, r_i]$$中等概率生成,服从均匀分布 求$$\sum\_{i = 2}^{n} |a\_i - a\_{i-1}|$$的期望 **算法分析** 根据期望的线性,只需要对每个$$i$$,求出$$E(|a\_i - a\_{i-1}|)$$,它符合均匀分布 已知$$X$$在区间$$[A, B]$$上服从均匀分布,那么概率密度函数是 ```math \displaystyle f_X(x) = \begin{cases} \dfrac{1}{B - A}, x \in [A, B] \\ 0 \end{cases} ``` 同理 ```math \displaystyle f_Y(y) = \begin{cases} \dfrac{1}{D - C}, y \in [C, D] \\ 0 \end{cases} ``` 所以联合概率密度是 ```math f(x, y) = f_X(x) \times f_Y(y) ``` 综上所述 ```math \displaystyle E[|x - y|] = \dfrac{1}{(B-A)(D-C)} \int_{A}^{B} \int_{C}^{D} |x-y|dxdy ``` > 多重积分 ```math \displaystyle \int_{C}^{D} |x - y|dxdy = \left[ -\dfrac{1}{2}(x-y)|x-y| \right]_{y = C}^{y = D} \\ = -\dfrac{1}{2}(x-D)|x-D| + \dfrac{1}{2}(x-C)|x-C| ``` 再考虑对$$x$$积分 ```math \displaystyle \left[-\dfrac{1}{6} (x-D)^3 + \dfrac{1}{6}(x-C)^3 \right]_{x = A}^{y = B} ``` > 特别地,如果$$A = B$$,那么就变成一重积分了 ```math \displaystyle \dfrac{1}{D-C} \int_{A}^{B} |y - A| dy \\ \quad \\ =\dfrac{1}{D-C} \dfrac{1}{2} \left[ (y - A)|y - A| \right]_{y = C}^{y = D} ``` ### 1009 **[怪演?二十面?相](https://acm.hdu.edu.cn/contest/problem?cid=1204&pid=1009)** 有`n+2`个格子,每个格子的颜色是红、黑、白,你可以从格子$$i$$跳到格子$$j$$ 满足$$i \leqslant j$$,现在一轮游戏,`A, B`轮流,`A`可以跳红色和白色格子,`B`可以跳黑色和白色格子 跳到`n+1`个格子,一轮就结束了,然后开始下一轮 在一轮中,白色格子可以原地跳,红色和黑色只能经过一次 然后开启下一轮,问最少要多少轮次,可以经过所有的格子至少一次 **算法分析** 如果没有白色格子,那么一轮游戏构成`R -> B -> R -> B -> ...`这样交替的链 答案就是**最小链覆盖** 求最小链覆盖也很简单,维护`cntR, cntB`,如果遇到`B`,那么接在`R`后面,消耗掉`R`,`cntR--` (相当于为`R`找后继) 如果没有`R`可以消耗了,要新开一条链`cntB++`,答案就是`cntB + cntR` 这样就构成了若干不相交的连通块 现在有白色节点,**轮与轮之间,可以通过原地跳`W`来把 “合并不同的连通块”** 让轮数多的连通块,“吸收”轮数小的,这样在完成“大轮”的同时,顺带完成“小轮” ### 1001 **[非凡之星](https://acm.hdu.edu.cn/contest/problem?cid=1204&pid=1001)** 给定`n`个点`m`条边的无向连通图,每条边通过时长是`1 个单位`,一开始`Alice`在节点`1` 而`Bob`在节点`n`,Alice 会从`1`号点走一条最短路到达`n`号点,同时再从`n`号点走最短路回到`1`号点 两条最短路相互独立,第一次选择走的路,不一定第二次一定要走 如果有多条最短路,走任意一条 `Bob`从`n`走到`1`,可以在原处停留`1min`或者移动到相邻节点 并且要满足,不论`Bob`怎么移动,都不会和`Alice`相遇 相遇的定义为:在同一时刻两人到达同一个结点或者同一时刻两人经过同一条边 如果`Bob`能够到达一号点,并且时间严格小于`Alice`**回到`1`号点**的总时间 输出答案,否则输出`-1` **算法分析** > 边权都是`1`,可以通过`bfs`找最短路 两个人同时开始动,对于每个点来说,记录一下`Alice`和`Bob`到达的**时间戳** 也就是距离编号,如果距离编号相等,说明相遇 哪些点`Alice`一定会经过呢?先一遍求出最短路`mindist` 1)从`1`开始`bfs`得到每个点的距离标号`dis1` 2)从`n`开始反向`bfs`得到每个点的距离标号`disn` 一个点$$u$$一定会被经过,当且仅当$$dis1_u + disn_u = \text{mindist}$$ 这样可以标记每个点是不是关键点`key[u]` > 接下来考虑`Bob`的策略,从`n`开始逐层扩展,维护距离标号`D` 如果`Bob`不动的话,是一定会和`Alice`相遇的 但我们发现,`Bob`最优的路径,也是沿着$$n \to 1$$**最短路**走的 贪心地,我们要在`Alice`还没有发现我们的时候,抢先把这些位置都走了 可以用**多源最短路**,什么叫**“还没有发现”** 就是满足$$\text{key}\_u = 1, \quad disn\_u < dis1\_u$$的点$$u$$ 这些点应该被抢占,作为多源最短路的起点 接下去就只能**绕安全区**了,往`key = 0`的区域扩展,执行`bfs` > 最后计算答案,枚举从安全区中哪个点出来,绕回**最短路主干道** 假设说枚举$$u$$是安全区中的点,枚举$$u \to v$$,去往主干道上的点$$v$$ 如果$$D_u + 1 > dis1_v$$,那么和`Alice`一定会错开,沿着`Alice`的来时路走回去即可 答案就是$$D_u + 1 + dis1_v$$ 否则的话,强行冲过去一定会和`Alice`相遇,我们必须在`u`点等待 等待`Alice`走过去之后,我们再走,所以总时间是$$dis1_v + 1 + dis1_v$$ ## Codeforces Round 1044 ### E **[E. I Yearned For The Mines](https://codeforces.com/problemset/problem/2133/E)** 小时候,Steve 渴望进入矿井!他的矿井可以表示为一棵有`n`个节点的树 不幸的是,Steve 的最大死敌 Herobrine 潜入了他的矿井!任何时刻,Herobrine 都正好藏在一个节点里;最初,他可能在任意一个节点。Steve 可以执行以下操作: - `1 x` —— 检查 Herobrine 当前是否在节点`x`。如果在,Steve 就抓住了他。否则,Herobrine 可以选择是否移动到任意一个相邻节点(除了你刚刚检查过的那个)。 - `2 x` —— 摧毁所有与节点`x`相连的边;Herobrine 之后将无法再通过这些边移动。随后,Herobrine 可以选择是否移动到任意一个相邻节点。 请你找出一组不超过 $$\left\lfloor \frac{5}{4} \cdot n \right\rfloor$$ 次操作的方案,使得无论 Herobrine 最初藏在哪里、如何移动,Steve 都一定能抓住他。我们已经证明,在给定约束下总是存在这样的方案。 **算法分析** > 如果是链呢? 对于链的情况,实际上不需要`2`操作了,直接从链的一端“围堵”即可 > 其他情况可以看成若干条链,**连成簇**,簇点是我们需要考虑的,即`deg >= 2`的点 用`dp(u)`表示自底向上传递过来多少条“单链” 如果$$dp(u) = 2$$,但是`u 没有父亲`,那么它在链上 如果`fa[u] != 0`,说明**这条链挂在某个父亲上**,要把这条链切下来,切父亲`fa` (因为是一棵树,**自底向上切链**,每条链最多只可能被挂在一个父亲上,否则就成环了) 如果$$dp(u) \geqslant 3$$,那么`u 这个点由多条链`**簇拥而成**,此时直接切`u` > 切完了之后,整个图就剩下切掉的孤立点和若干条直链 重新建图,`dfs 新图的每条直链`,注意从`deg = 1`的端点开始围堵,这样就做完了
0
0
上一篇:2026年五月算法竞赛选题(一)
已经是最后一篇啦
看完文章有啥想法
发布评论
8 人参与,0 条评论