七月算法竞赛选题（一）

[[ slider_text ]]

[[ item.c ]]

七月算法竞赛选题（一）

发布时间 2025-07-07 作者：zhangminchen 来源：算法小站

状态压缩dp 概率和期望

## AtCoder Beginner Contest 411
### E
**[E - E [max]](https://atcoder.jp/contests/abc411/tasks/abc411_e)**
**问题描述**
有$$n$$个六面骰，每一个骰子的数字分别是
```math
A_{i, 1}, A_{i, 2}, \cdots, A_{i, 6}
```
现在同时投出去，令$$x$$是这$$n$$个骰子朝上的数值的最大值，求$$x$$的期望

**算法分析**
其实并不难，首先考虑离散化，$$(x, dp(x))$$，表示$$x$$作为最终的最大值，出现的概率是$$dp(x)$$，答案就是
```math
\displaystyle
\sum_{x} rm(x) \cdot dp(x)
```
其中$$x$$表示离散化后的值，$$rm(x)$$表示原先的值

那么我们只需要枚举$$x$$作为答案的概率就可以了，对于每个骰子，$$\prod_i \dfrac{cnt_i}{6}$$
其中$$cnt_i$$表示第$$i$$个骰子有几个面$$\leqslant x$$

> 难点在于，枚举$$x$$，你还要继续统计$$\leqslant x$$的$$cnt_i$$，这个复杂度变成$$O(n^2)$$了

![](/media/content_img/abc411-e1.png)
![](/media/content_img/abc411-e2.png)

### F
**[F - Contraction](https://atcoder.jp/contests/abc411/tasks/abc411_f)**
**问题描述**
给你一个无向图$$G_0(n, m)$$，Takahashi 有一个图$$G$$，一开始$$G = G_0$$，同时他还有$$n$$个棋子
一开始棋子$$i$$放在顶点$$i$$上

给你$$Q$$个操作，第$$i$$个操作给定$$1 \leqslant X_i \leqslant M$$，实际上就是第$$X_i$$条边

在图$$G$$上，如果$$(U(X_i), V(X_i))$$这两个棋子在不同的顶点上，并且它们有一条边相连，它们会被合并
合并是指，将他们合并成一个大点，同时原先和$$(U(X_i), V(X_i))$$相连的边全部删掉，和新的大点连边

现在问第$$i$$次操作后，$$G$$的边数

**算法分析**
> 首先考虑$$u, v$$**没有**共同邻居$$|C|$$，答案会怎么变化

假设原来的边数是$$m$$，那么$$m = m - 1$$

> 进一步来看，假设公共邻居集合是$$|C|$$，每一个邻居需要减少`1`条边，另外$$(u, v)$$的重边也要扣除

答案是$$m \to m - |C| - cnt(u, v)$$

> 难点是怎么维护呢？可以考虑**启发式合并**，用并查集维护$$u \in |U|, v \in |V|$$

**启发式合并 + 模拟**即可实现，合并$$(u, v)$$，实际上就是对于$$u \in U, v \in V$$，将$$V \to U$$
1.对于$$v$$中的所有邻居$$w \in g(v)$$，断开$$(w, v)$$，并且维护边数`m -= 1`
2.接着对于$$w \neq u$$，如果$$(w, u)$$还没有连边的话，接上去，`m += 1`

### G
**[G - Count Cycles](https://atcoder.jp/contests/abc411/tasks/abc411_g)**
**问题描述**
给定无向图$$G(N, M)$$，不含自环，但可能有重边，现在要你计算$$G$$中环的个数，对`998244353`取模

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

## Codeforces Round 1034 (Div. 3)
### E
**[E. MEX Count](https://codeforces.com/contest/2123/problem/E)**
**问题描述**
给你一个序列$$a$$和一个值$$k$$，问你恰好删$$k$$个数，会有多少个不同的`mex`取值？

**算法分析**
删除多个数，mex 值变化可能会很复杂，比如说删`4`个数到删`5`个数，可能`mex`值会**跳水**减少

那么针对这种问题，注意到`mex`值最多只能是`[0, n+1]`变化，可以考虑`mex`值在**删几个元素的时候会出现？**
首先可以求出整个序列的`mex`值$$M$$，那么$$[0, M]$$考虑让每个`mex`值出现，要删几个元素？

假设说$$mex = x$$要出现，那么你至少要删掉`cnt[x]`个元素
但其实你还可以多删，但又不能删太多，最多情况下，你必须保证`[0, x-1]`全部都**铺满**，每个位置都恰有`1`个元素
所以最多可以删$$n - x$$个
也就是说，删除元素个数$$c \in [cnt_x, n-x]$$，都会使得答案出现`mex = x`而增加`1`
区间加，这里可以用差分数组

> 特别注意，这题不能 dp

为什么呢？因为$$dp(1)$$表示删除`1`个数，会产生多少个不同的`mex`
比如你删除只出现`1`次的数，`mex = 4`，那么$$dp(1) \to dp(2)$$，`mex = 4`还会保留吗？
不一定的，因为它强制删`2`个数，如果比如`{1, 2, 3}`都只出现了`1`次，你第一次删除导致`mex = 4`
它强制要求你再删一个，那么你一定会删掉`{1, 2, 3}`的其中一个，`mex`值就会发生跳水
`mex = 4`不会再保留了，$$dp(1) \to dp(2)$$的转移关系是**不确定**的

删$$i$$个，会出现多少个不同的`mex`，不能简单地从删$$i-1$$个递推过来

## CodeTON Round 4
### D
**[D. Climbing the Tree](https://codeforces.com/contest/1810/problem/D)**
**问题描述**
蜗牛爬树，从`0`位置开始爬，白天爬`a`，晚上落下`b`，树的高度不知道
给你若干信息，有`2`种不同的类型
`1 a b n`表示当前蜗牛说要`n`天爬到树顶，如果和之前的信息矛盾，那么无视，否则采纳
`2 a b`对蜗牛进行询问，问它要几天爬到树顶？

**算法分析**
实际上就是区间求交，但是一些坑点
1.当`n = 1`的时候，区间长度是$$[1, a]$$，要特判，否则是$$[(a-b)(n-2)+a+1, (a-b)(n-1)+a]$$
2.怎么判断天数是否唯一，给你一个区间$$[L, R]$$判断唯一解？怎么做？**不需要二分**
直接计算爬到$$L$$所需要的天数，以及爬到$$R$$所需要的天数，都可以直接计算，如果$$d1 = d2$$那么就有解

### E
**[E. Monsters](https://codeforces.com/contest/1810/problem/E)**
给定一个无向图$$G(n, m)$$，第$$i$$个点有一个数值是$$a_i$$怪物，对于这样的怪物，你能打败他
当且仅当你曾经打败过的怪物**数量和**$$\geqslant a_i$$
现在你想打败所有的怪物，一开始你选择某个顶点$$s$$开始，因为你之前没有打败过怪物，你必须选择$$a_s = 0$$的点$$s$$
然后你可以在边上移动了，你能从$$(u \to v)$$当且仅当$$v$$上的怪物被击杀了，或者你可以打败它
现在判断你能否打败所有的怪物

**算法分析**
> 和 **[ICPC 2021 上海 H](https://www.ringalgo.com/wiki/17/)** 有点像

两个问题的做法几乎一模一样，对于$$(u, v)$$，建边$$(u, v, w)$$，其中$$w = \max(a_u, a_v)$$
然后对所有$$a_u = 0$$的$$u$$考虑树上倍增，看一下能够吃掉的怪物数量
```bash
auto query = [&](int u) -> int {
	int res = sz[u];

while (u && u != tot) {
		int st = u;
		for (int i = LOG; i >= 0; i--) {
			int to = go[u][i];
			if (to == 0) continue;
			如果当前已经被吃掉的怪物数量，>= wgt[to]，那么这条边可以通过，可以往上走
			if (wgt[to] <= res) u = to;
		}
		
		u 不能再往上抬了，就退出
		if (u == st) break;
		res = sz[u];
	}
	
	return res;
};
```
最后检查`res`是否满足`res == n`即可

## Codeforces Round 1035 (Div. 2)
### D
**[D. Token Removing](https://codeforces.com/contest/2119/problem/D)**
**问题描述**
定义长度为$$n$$的有效序列`a`为，对任意的$$1 \leqslant i \leqslant n$$，有$$0 \leqslant a_i \leqslant i$$
再定义有效序列`a`的权重为$$f(a)$$，满足
```bash
1. 初始时候，存在 [1...n] 这 n 个数
2. 从左到右遍历序列 a，对于第 i 个数，如果 a[i] != 0，那么从区间 [a[i]...i] 选择一个未删除的数删除
如果 a[i] = 0，不做任何操作
3. f(a) 表示序列 a 在上述过程中，最终可以得到不同的删除数的方案数
```
比如$$n = 3$$的序列`[0, 2, 1]`，它对应的$$f(a) = 2$$，你只能从下标`i = 2`开始删（因为`a[1] = 0`不能操作）
```bash
i = 2，选择`[a[2], 2] = [2, 2]`删，只能选 2
i = 3，选择`[a[3], 3] = [1, 3]`删，可以选 {1, 3} 两个数，2 删过了不再选中

所以方案数是 2，{2, 1} , {2, 3}
```
现在给定$$n$$，问对于多有的长度为$$n$$的有效序列`a`，求他们的权重$$f(a)$$之和

**算法分析**
根据数据范围，可以考虑二维`dp`
从左往右 dp，定义$$dp(i, j)$$表示考虑$$i$$位置，还可以选$$j$$个数删除时的方案数
需要枚举上一个位置中，$$[a(i-1), i-1]$$中未被删除的元素有$$j$$个，能不能递推到$$[a(i), i]$$？

> 发现这样不能做，因为$$a_i, i$$的值都是不确定的，你既不知道每一个`a[i]`值是多少
你也不知道当前选的序列`a[1...i]`的长度`i`

![](/media/content_img/cf1035d1.png)
![](/media/content_img/cf1035d2.png)

## Codeforces Round 1036, Div. 1 + Div. 2
### D
**[D. Make a Palindrome](https://codeforces.com/contest/2124/problem/D)**
**问题描述**
给定一个序列`a`和一个值`k`，你可以执行以下操作若干次
选择一个区间`[l, r]`，要满足$$r - l + 1\geqslant k$$
删除区间第 kth 的元素
现在问，经过若干次操作，能不能使得序列变成回文序列？

**算法分析**
**分析1**
注意，每次都删第`k`大，那么最小的第`[1...k-1]`个元素**一定会被保留**

**分析2**
如果这些数已经构成了回文串，那么不需要额外操作了
否则的话，需要为**未配对的数**，找一个区间外的，同样的数加进来配对
你会发现，加进来的数，**他的取值还是这么些！**只不过冗余了元素而已！
总之，一定围绕着**值不超过**`(k-1)th`的数做文章

**分析3**
只考虑把值$$\leqslant$$`(k-1)th`的元素放进来，因为有冗余元素，最后放入的数，大概率会多于$$k-1$$个
![](/media/content_img/cf1036d.png)

上一篇：六月算法竞赛选题（四）下一篇：七月算法竞赛选题（二）

看完文章有啥想法