算法小站
首页
wiki
新鲜事
文章搜索
网站导航
回忆录
首页
wiki
新鲜事
文章搜索
网站导航
回忆录
登录
注册
算法基础
搜索
数据结构
字符串
数学
图论
动态规划
计算几何
杂项
2026年六月算法竞赛选题(二)
gcd,dp,中位数,主席树,可持久化线段树,排列,构造,博 .....
[[ slider_text ]]
[[ item.c ]]
0
0
2026年六月算法竞赛选题(二)
发布时间
2026-06-29
作者:
秋千月
来源:
算法小站
## Educational Codeforces Round 191 ### F **[F. Shortest GCD Paths](https://codeforces.com/contest/2233/problem/F)** 给定`n`个点的完全图,给定起点`a, b`,对于不同的点`u, v`,`(u, v)`有边,边权是 ```math \displaystyle w(u, v) = \dfrac{\max(u, v)}{\text{gcd}(u, v)} ``` 求`a -> b`的最短路径 **算法分析**   ## Codeforces Round 1037 (Div. 3) ### G2 **[G2. Big Wins! (hard version)](https://codeforces.com/problemset/problem/2126/G2)** 给定序列`a[1...n]`,最大化`med( a[l, r] ) - min( a[l, r] )` **算法分析** 很套路地,枚举`a[i]`作为最小值`minv`,维护出极大的`a[i]`作为最小值的区间`[l, r]` 然后主席树取第`K = cnt / 2`大,但很可惜,这样是错误的 因为实际上,合法的区间是`[l, r]`所有**包含`i`位置的子区间**,子区间缩小,又可能出现更小的中位数 > 怎么进一步做呢? 考虑 easy 版本的做法,二分中位数`x`,对每个`i`,预处理`a[i]`作为最小值的区间`[l, r]` 然后最大子段和`S = max[i, r] - min[l-1, i-1] > 0`,那么`x`就可能成为候选的中位数 主席树呢?主席树很难处理`[l, r]`最大值的问题 回到`easy`版本,线段树维护的是什么呢?二分中位数之后,`>= x 的 +1, < x 的 -1` 得到这样的数组`b`,对`b`求前缀和,线段树维护的是**前缀和数组** > 考虑优化 如果中位数是不变的,假设就是`x`,那么我们枚举最小值`a[i]`,仍可以在$$\log (n)$$的复杂度内 完成对`max[i, r], min[l-1, i-1]`的查询 算法的瓶颈在于说,每次二分`x`的时候,`b`**对应的前缀和数组**会变化 那么一种想法是,**预处理`b`随`x`的变化,**$$x \to x+1$$,`x+1 这个版本从 x 变化而来` 这样二分`x`的时候,我们直接在`x`这个版本的线段树中做查询,查询的方法和 easy 版的一样 > $$x \to x+1$$,对应的可持久化线段树会怎么变化呢? 初始化,`x = 1`,那么`b 数组所有位置都是 +1`,考虑$$x \to x+1$$,在`x+1`这个版本中 原来`值为 x 的位置 = {j1, j2, ..., jm}`,`ver[x+1] = ver[x] 这个版本基于 j 的修改` 那么会怎么变呢?`j`这个值从`+1 -> -1`,也就是说`b[j] -= 2`,**那么前缀和呢?** 前缀和对应**区间修改**,$$[j, n] -= 2$$,在主席树中用**标记永久化**实现 最后二分的时候,直接查询`ver[x]`,按 easy 版本处理即可 ## Codeforces Round 1061 (Div. 2) ### F1 **[F1. Strange Operation (Easy Version)](https://codeforces.com/problemset/problem/2156/F1)** 给定一个长度为 $$n$$ 的排列 $$p$$。你可以进行如下操作任意次(也可以不做): 选择三个互不相同的下标 $$i, j, k$$,满足 $$1 \le i < j < k \le n$$,并且同时满足以下两个条件 $$p_i = \max(p_j, p_k) + 1$$ 并且 $$p_i = \min(p_j, p_k) + 2$$。然后,将 $$p_i$$减去$$2$$,$$p_j,p_k$$ 都$$+1$$ 你的任务是,在任意次操作后,求出可以得到的字典序最小的排列。 **算法分析** > 先翻译题意 对于$$i < j < k$$三个位置,值分别是$$\\{x+2, x, x+1\\}$$,操作之后,$$\\{x, x+1, x+2\\}$$ > 算法实现    ### E **[E. Best Time to Buy and Sell Stock](https://codeforces.com/contest/2156/problem/E)** 一个长度为`m`的数组`b`(其中`m >= 2`)的美丽值定义为 **所有下标对** `i`和 `j` 满足 $$1\le i < j\le m$$时的最大值 $$b_j - b_i$$ 更正式地,其等于 $$\max\limits\_{1\le i < j\le m} (b\_j - b\_i)$$。注意,如果该数组严格递减,美丽值可能为负数。 Hao 和 Alex 在一个长度为`n`的数组`a`上轮流进行游戏 初始时,数组中所有元素都是未锁定的。两人轮流行动,由 Hao 先手。 - Hao 的回合,他选择一个未锁定的`a`中的元素并将其移除。 - Alex 的回合,他选择一个未锁定的`a`中的元素并将其锁定(之后不能再被移除)。 当所有元素都被锁定或移除后,游戏结束 可以证明游戏恰好持续`n`个回合,最终数组中会恰好剩下 $$\left\lfloor \frac{n}{2} \right\rfloor$$ 个被锁定的元素。 Hao 希望最终锁定数组的美丽值尽可能小,而 Alex 希望它尽可能大 求当两人都采取最优策略时,最终锁定的元素数组的美丽值。   ## Codeforces Round 1056 (Div. 2) ### E **[E. Mimo & Yuyu](https://codeforces.com/contest/2155/problem/E)** 有一个$$n \times m$$的网格,列从左到右编号为$$1, 2, \ldots, m$$ 行从上到下编号为$$1, 2, \ldots, n$$。设$$(u, v)$$表示第`u`行第`v`列的网格单元 每个单元格可以包含任意数量的代币,且这些代币之间没有区别 初始时,有`k`个代币,第`i`个代币位于$$(x_i, y_i)$$ 现在 Mimo 和 Yuyu 轮流进行游戏。每回合,当前玩家选择一个当前在网格上的代币$$c$$ 以及一个长度为`p`的由不同单元格组成的序列$$(a_1, b_1), (a_2, b_2), \ldots (a_p, b_p)$$ 1)`c`位于$$(a_1, b_1)$$ 2)对于所有`i`,有$$|a\_{i+1} - a\_i|+|b\_{i+1} - b\_i| = 1$$,即序列中的相邻单元格必须在网格中相邻 3)$$b_1 \ge b_2 \ge \ldots \ge b_p$$,即所有位置的列号按非递增排序(不能离开第 1 列的方向) $$b_p = 1$$,即序列的最后一个位置必须在第 1 列 $$b_1 > b_2$$,特别地,$$b_2 = b_1-1$$ 也就是说 $$(a_1, b_1)$$ 必须是唯一一个位于第$$b_1$$列的单元格。 然后,玩家将`c`从网格上移除 并在$$(a_2, b_2), (a_3, b_3), \ldots, (a_p, b_p)$$上各增加 1 个代币。该回合结束。 无法进行操作的玩家判负。Mimo 先手。假设双方都采取最优策略,判定谁会获胜 **算法分析**  ## Codeforces Round 1105 (Div. 2) ### B **[B. AI Finds Nothing Here](https://codeforces.com/contest/2240/problem/B)** 给定`n, m, r, c`,问$$n \times m$$的`01 矩阵`有多少种,使得**任意**$$r \times c$$子矩阵 都满足**所有元素的 xor 和为 0** **算法分析**  ### C **[C. Nim Game Is XOR Game](https://codeforces.com/contest/2240/problem/C)** Alice 和 Bob 博弈,给定一个数组`a[1...n]`,每一轮要求构造一个数组`b[1...n]` 如果满足`b`**不全为 0**,并且$$b_1 \oplus \cdots \oplus b_n = 0$$,$$0 \leqslant b_i \leqslant a_i$$ 那么构造成功,令$$a_i = a_i - b_i$$ 谁不能操作就失败 **算法分析**   ### D **[D. Decidophobia](https://codeforces.com/contest/2240/problem/D)** 给定一个环,点上的编号是`1, 2, ..., n`,每个点表示一个人,你要送他们礼物,给定`d`,表示窗口大小 对于`第 i 个人`,他能看见`[i-d, i+d]`的人,现在计算 happiness 1)如果第`i`个人收到了礼物,并且他能看到的人中有`x`个人未收到礼物,`happiness`增加$$x\cdot a_i$$ 2)如果第`i`个人未收到礼物,并且他能看到的人中有`x`个人已经收到礼物,`happiness`$$-x\cdot a_i$$ 最大化`happiness` **算法分析** 对于$$i, [i-d, i+d]$$,能看到的人划分成两个集合$$X, Y$$,其中$$X$$表示收到礼物的人,$$Y$$表示未收到礼物的人 那么$$X + Y =$$`窗口内除了 i 之外所有人的集合` 决策`i`是否应该收到礼物,考虑它对**全局`happiness`的贡献**,不收,自然贡献为`0` 如果收礼物呢? 贡献的增长$$2d \cdot a\_i - \sum\_{j \in X} a\_j$$,另外`a[i]`收到礼物,会导致$$Y$$中的人不满 要扣除减少的满意度$$-\sum\_{j \in Y} a\_j$$,不难发现$$\sum\_{j \in X} a\_j + \sum\_{j \in Y} a\_j = $$`窗口除了 i 之外所有人的和` 贡献就是$$2d \cdot a\_i - \sum\_{j \text{在窗口内}} a\_j$$,预处理+滑动窗口可以很轻松解决 ## Codeforces Round 1106 (Div. 2) ### D **[D. Storming Arasaka](https://codeforces.com/contest/2238/problem/D)** 给定`n`,问最小的构造层数,构造的层的约束如下 1)`n`的因子,每个因子都属于某个层,$$L_1, L_2, \cdots L_k$$ 2)对于某个层$$L_i$$保存的**任何一个**数$$x$$,它的因子(除了`1 和 它本身`) 必须保存在之前的$$L[1 \sim i-1]$$层中 3)在每一层,存在一种排列,使得相邻元素的`gcd > 1` 问构造的最小层数`K` **算法分析**  
0
0
上一篇:2026年六月算法竞赛选题(一)
已经是最后一篇啦
看完文章有啥想法
发布评论
5 人参与,0 条评论