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

[[ slider_text ]]

[[ item.c ]]

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

发布时间 2026-06-22 作者：秋千月 来源：算法小站

状态机

## Codeforces Round 1102 (Div. 2)
### F
**[F. Vessels, Heights and Two Versions (Hard Version)](https://codeforces.com/contest/2234/problem/F)**
给定一个`n`个元素的环，每个位置表示一个装水的容器，容器的盛水量用`w[i]`来表示
但是每个位置给你限制`h[i]`，如果`w[i]`盛水容量超过$$> h_i$$，那么水会流到`w[i mod n + 1]`中去
同样，如果`w[i mod n + 1]`盛水容量超过`h[i]`，水也会流到`w[i]`中去

换句话说，如果`w[i]`想要空的，那么要求`w[(i-1) mod n]`的水不超过`h[(i-1) mod n]`（实际上是后缀最大值）
这样水流不过来，同时呢，`w[(i+1) mod n]`的水不超过`h[i]`，这样后面的水也流不过来

现在要你回答，对`i = 1, 2, ..., n`如果$$w_i = 0$$，即`i`容器是空的，$$w_1 + w_2 + \cdots + w_n$$
最多能装多少水

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

### D
**[D. XOR, Expression and Two Binary Numbers](https://codeforces.com/contest/2234/problem/D)**
给定`K`，存在一个序列$$a[1 \sim 2^K + 1]$$，序列中的每个数的值都是一个`n`位二进制数

其中$$a\_1$$和$$a\_{2^K+1}$$是给定的，通过`K`步操作来确定所有元素，每次操作执行如下

假设说当前$$p_1 < p_2 < \cdots < p_m$$已经完成填充

对$$j \in [1, m-1]$$，执行赋值操作$$a\_{\frac{p(j) + p(j+1)}{2} } = a\_{p(j)} \oplus a\_{p(j+1)}$$

所有的填充操作**同时进行**

要求计算$$x\_1y\_1 + x\_2y\_2 + \cdots + x\_{2^K+1}y\_{2^K+1}$$
其中$$x\_i$$表示第`i`个数二进制`1`的个数，$$y\_i$$表示`0`的个数

**算法分析**
![](/media/content_img/cf1102-d.png)

### E
**[E. Vlad, Misha and Two Arrays](https://codeforces.com/contest/2234/problem/E)**
一开始有一个未知的排列，对每个`i = [1..n]`，给定$$1 \leqslant l \leqslant r \leqslant n$$
表示排列中有多少个$$(l, r)$$组合，满足`p[l...r]`的最小值等于`p[i]`
然后我们把这个方案数，赋值给$$a_i$$

现在给定`a[1...n]`，要你猜出初始的排列`p`，当然这样的排列并不总是唯一的
输出合法排列的方案数，或者报告不存在

**算法分析**
![](/media/content_img/cf1102-e1.png)
![](/media/content_img/cf1102-e2.png)

### G
**[G. Stripe, Token and Two Players](https://codeforces.com/contest/2234/problem/G)**
博弈论，两个人玩游戏，有一条包含 $$n+1$$ 个格子的纸带，格子编号从 $$1 \sim n+1$$
初始时，在`1`号格子上有一个力量值（power）为`1`的标记物（token）
并且在 $$1, 2, \dots, n$$ 号格子上分别写着数字 $$a_1, a_2, \dots, a_n$$

两名玩家轮流，在一个回合中，当前玩家必须按顺序执行如下操作
假设当前标记物在`i`，可以将标记物的力量值增加$$[0, a_i]$$的任意整数
然后玩家将标记物向前移动任意一个不超过其力量值的正整数步，确保执行此移动后标记物不会越出纸带界限

经过某次移动后，标记物正好落在`n+1`号格子上的玩家赢得游戏
问谁会获胜

**算法分析**
![](/media/content_img/cf1102g1.png)
![](/media/content_img/cf1102g2.png)
![](/media/content_img/cf1102g3.png)

## Educational Codeforces Round 191
### E1, E2
**[E1. Permutation Transmission (Easy Version)](https://codeforces.com/contest/2233/problem/E1)**
给定一个长度为`n`的排列，发送一个字符串数组，大小为`topbit(n)`
每个串的长度为`n`，构成`s[i][j]`的矩阵
其中，`S[0] = (p[0]的第 0 位， p[1]的第 0 位，p[2]的第 0 位.... p[n-1]的第 0 位)`构成

但是，字符串的顺序是乱的，比如`p = [3, 1, 2, 4]`，你会收到串
`1100, 1010, 0001`，但是现在不知道哪个字符串对应哪个特定的比特位
也就是说，你可能以`1010, 0001, 1100`的顺序收到这些字符串

现在这些字符串给定，你需要输出对应多少种不同的原始排列
当然也可能数据是错的，不存在有效的排列，输出`0`

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

### 算法实现
```bash
auto dfs = [&](auto &dfs, const vector<int> &C, const vector<int> &B, int m, int x) -> i64 {
    auto hasone = [&](int b) -> bool {
        return ranges::any_of(C, [&](int c) { return s[b][c] == '1'; });
    };

if (x == 0) {
        for (auto b : B) {
            if (hasone(b)) return 0;
        }
        return fac[B.size()];
    }

// leading 0
    int topb = topbit(x);
    size_t lzero = m - topb;
    auto nB = B | views::filter([&](int b) { return hasone(b); }) | ranges::to<vector>();
    if (B.size() - nB.size() != lzero) return 0;

i64 ways = fac[lzero];

// chose for curb
    int C0one = (topb > 0 ? 1LL << (topb - 1) : 0);
    int curone = x - (1LL << topb) + 1;

auto can = [&](int b) -> bool {
        return ranges::count_if(C, [&](int c) { return s[b][c] == '1'; }) == curone;
    };
    auto canexpt = [&](int b) -> bool {
        for (auto b2 : nB) {
            if (b2 == b) continue;
            bool ok = ranges::count_if(C, [&](int c) { return s[b][c] == '0' and s[b2][c] == '1'; }) == C0one;
            if (!ok) return false;
        }
        return true;
    };

int choseb = -1, cnt = 0;
    vector<int> nC;
    for (int b : nB) {
        if (!can(b)) continue;
        bool ok = true;

if (topb > 0 and !canexpt(b)) ok = false;

if (ok) {
            if (choseb == -1) {
                choseb = b;
                nC = C | views::filter([&](int c) { return s[b][c] == '1'; }) | ranges::to<vector>();
            }
            cnt += 1;
        }
    }
    if (cnt == 0) return 0;
    ways *= 1LL * cnt;

// dfs next
    auto nnB = nB | views::filter([&](int b) { return b != choseb; }) | ranges::to<vector>();
    i64 ways2 = dfs(dfs, nC, nnB, topb - 1, x - (1LL << topb));
    ways *= ways2;

return ways;
};
```
## leetcode 第 507 场周赛
### 最大总价值
**[最大总价值](https://leetcode.cn/problems/maximum-total-value/description/)**
给定两个序列`v, d`，以及一个整数`m`
可以任意，多次选择下标，但是所有下标总的选择次数不得超过`m`
如果重复选择下标`i`，第`t`次，获得的价值是`v[i] - d[i] * (t - 1)`，`t`从`1`开始计数
求能够获得的最大总价值

**算法分析**
每个物品$$v_i, v_i - d_i, v_i - 2d_i, v_i - 3d_i, \cdots$$
然后要求前`m`大的和（如果出现某个数$$\leqslant 0$$就抛弃）

正常的做法是`K`路归并，用大根堆，维护堆的大小$$\leqslant m$$
但这里$$m$$的大小是$$10^9$$，怎么办？

可以二分一个`tar`，$$[v_i, v_i - d_i, \cdots, tar]$$这样，构成一个**池子**
其中这个`tar`要满足，所有元素被选择次数$$\leqslant m$$，并且`tar`要尽量靠右（尽量小）

这样`>= tar`的就可以直接算出来，池子里的直接取走，用等差数列算代价
看一下这样还够不够`m`，不够的，再像上述那样用**大根堆**归并即可

## Educational Codeforces Round 191
### D
**[D. Goods on the Shelf](https://codeforces.com/contest/2233/problem/D)**
给定一个长度为`n`的序列`a`，其中`a[i]`表示商品的颜色
我们说序列是正确的，当且仅当颜色相同的商品，组成一个连续的区块
现在允许你**最多交换一次**，问能不能使得序列是正确的

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

## Codeforces Round 1104
### E
**[E. Permutation Commutation](https://codeforces.com/contest/2237/problem/E)**
给定一个排列`a`，和一个不完整的排列`b`，`b`中的一些数丢失，用`-1`表示
现在需要构造排列`b`，满足$$a(b(i)) = b(a(i))$$，要使得`b`的字典序最小

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

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

看完文章有啥想法