2026年六月算法竞赛选题（二）

[[ slider_text ]]

[[ item.c ]]

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`的最短路径

**算法分析**
![](/media/content_img/EDU191F-01.png)
![](/media/content_img/EDU191F-02.png)

## 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\\}$$

> 算法实现

![](/media/content_img/CF1061-F1.png)
![](/media/content_img/CF1061-F2.png)
![](/media/content_img/CF1061-F3.png)

### 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 希望它尽可能大
求当两人都采取最优策略时，最终锁定的元素数组的美丽值。

![](/media/content_img/cf1061e-01.png)
![](/media/content_img/cf1061e-02.png)

## 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 先手。假设双方都采取最优策略，判定谁会获胜

**算法分析**
![](/media/content_img/CF1056E.png)

## 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**

**算法分析**
![](/media/content_img/CF1105B.png)

### 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$$
谁不能操作就失败

**算法分析**
![](/media/content_img/cf1105-c1.png)
![](/media/content_img/cf1105-c2.png)

### 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`

**算法分析**
![](/media/content_img/cf1106-d1.png)
![](/media/content_img/cf1106-d2.png)

上一篇：2026年六月算法竞赛选题（一）已经是最后一篇啦

看完文章有啥想法