六月算法竞赛选题——概率与期望（三）

[[ slider_text ]]

[[ item.c ]]

六月算法竞赛选题——概率与期望（三）

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

概率和期望 构造 最大团

## Codeforces Round 688 (Div. 2)
### D
**[D. Checkpoints](https://codeforces.com/contest/1453/problem/D)**
**问题描述**
有$$n$$个关卡，有一些关卡有存档点，一些没有，从`1-n`开始过关，对于每个关卡，独立地有$$1/2$$的概率通过
也有$$1/2$$的概率失败，如果通过关卡$$i$$，进入关卡$$i+1$$，如果在关卡$$i$$失败，
退回最近一个有存档点的关卡$$j \leqslant i$$，保证关卡 1 一定有存档点
给出$$k \leqslant 10^{18}$$，构造$$n \leqslant 2000$$，同时构造出哪些关卡有存档点
使得直到通关的期望尝试次数是$$k$$

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

根据上面期望的表达式，$$k$$是奇数无解，如果$$k$$是偶数，进行二进制分解
$$k = \sum_i 2^i$$，对于每个$$i > 1$$，考虑放入 checkpoint，比如上一个 checkpoint 是$$p$$
那么在$$p = p + i - 1$$处放入，然后$$p = p+1$$，再放一个

## AtCoder Beginner Contest 410
### D
**[D - XOR Shortest Walk](https://atcoder.jp/contests/abc410/tasks/abc410_d)**
**问题描述**
给定$$n$$个点，$$m$$条边的有向图，可能有环，给定的边是$$(u, v, w)$$
其中$$w < 2^{10}$$，问从$$1 \to n$$的`xor`最小路径长度是多少
注意，可能在换上绕多次，可以多次经过一个点

**算法分析**
> 一开始可能想`SCC`（强连通分量）怎么做，然后转成 DAG 上的 dp 来处理

如果用`SCC`，先求一遍`SCC`，对所有的`SCC`，比如`scc(i)`，只针对`scc(i)`中的节点来建图
遍历这个图，如果`bel(u) == bel(v)`，那么就在`scc(i)`中加入边，`tr[i].addEdge(u, v, w)`
这样，每一个`SCC`缩点之后，里面有一个**局部的图**

很显然，`SCC`之间是`DAG`，可以`dp`的，但是每个`SCC`内部的呢？
内部有环，肯定是不能`dp`的，考虑最短路能不能做？

如果要用最短路的话，需要更换起点的同时，维护点的`dp`值，从堆中弹出的时候
令$$dp(x) = \min(dp(x), dis(x))$$

再`dfs`一遍整个图，对于$$u$$，首先他的最小值就是$$dp(u)$$，其次呢？它还可以在环上绕
相当于起点是$$u$$，起点距离是$$dp(u)$$，执行`dfs`，求出`SCC`中所有节点的最短路
这样绕一下，在`dijkstra`的时候更新维护`dp(u)`

然后对于$$v$$，也是一样的道理，首先是$$dp(v) = \min(dp(v), dp(u) \oplus w)$$
然后$$v$$可以去`SCC`中绕行

> 但很可惜，这样做是错的，**非简单路径，不能用`dijkstra`求最短路！**，为什么呢？
![](/media/content_img/abc410d.png)
> 那要怎么解决？**迭代！**（限制每条边的通过次数），如果$$dis(B) > dis(A) + w$$，但是$$(A, B)$$的通过次数没有超过迭代轮数的限制，我们仍可以让$$B$$进`heap`
只不过这样坐下来，至少要迭代$$n$$轮，复杂度会退化到$$n^2\log n$$

但注意，题中给出的权值很小，$$2^{10}$$级别，启发我们用拆点 + 状态压缩
暴力枚举每一个点，可能的权值和，拆点$$u \to (u, sta)$$，然后对于每条有向边$$(u, v, w)$$，
拆点，建新的有向边，$$(u, sta) \to (v, sta \oplus w)$$，`bfs`一遍，对于$$u = n$$，如果$$(n, sta)$$可达
就用`sta`来更新答案

## Pinely Round 4
**[D. Prime XOR Coloring](https://codeforces.com/contest/1991/problem/D)**
**问题描述**
给定$$n$$个点的无向图，$$u, v$$有边当且仅当$$u \oplus v$$是一个素数
现在要求你给所有节点染色，用最少的颜色，使得相邻的点颜色不同，如果是二分图的话，只要 2 种颜色

**算法分析**
这种问题，首先应该考虑**小规模数据打表**
因为素数的个数是$$O(\log n)$$个，所以可以先打表所有可能的素数
枚举$$x \in [1, n]$$，再枚举所有素数，令$$y = p \oplus x$$，如果$$y \in [1, n]$$的话，那么暴力建图连边

> 不难发现，需要颜色的数量 = **原图的最大团**，而最大团问题是 NP-complete 的，所以一定是打表找规律

对小规模数据，暴力打表求最大团
发现当$$n \in [6, 100]$$的时候，最大团$$|Qmax| = 4$$，于是我们猜想，当$$n \geqslant 6$$的时候，答案是不是都是$$4$$
![](/media/content_img/pinelyround4-d1.png)
![](/media/content_img/pinelyround4-d2.png)

## Codeforces Round 857 (Div. 2)
### C
**[The Very Beautiful Blanket](https://codeforces.com/contest/1802/problem/C)**
**问题描述**
认为一个地毯是鲜艳的，当且仅当它的**所有**$$4 \times 4$$子矩阵满足
```math
\displaystyle
A_{11} \oplus A_{12} \oplus A_{21} \oplus A_{22} = A_{33} \oplus A_{34} \oplus A_{43} \oplus A_{44} \\
A_{13} \oplus A_{14} \oplus A_{23} \oplus A_{24} = A_{31} \oplus A_{32} \oplus A_{41} \oplus A_{42}
```
即左上角`4`个元素的异或和等于右下角`4`个元素的异或和，同理，右上角 = 左下角
现在要你构造一个大小为$$n \times m$$的矩阵`B`，首先它必须是鲜艳的，其次呢，不同数字的数量必须最大

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

可以考虑先构造低位，使得所有$$2 \times 2$$子矩阵$$\oplus = 0$$，然后根据一对$$(i, j)$$
在不同的高位引入$$1$$

## Codeforces Round 1033 (Div. 2)
### C
**[C. Divine Tree](https://codeforces.com/contest/2120/problem/C)**
**问题描述**
构造一个$$n$$个节点的有根树，根也需要你自己构造指定，定义$$d(i)$$是从根节点到$$i$$简单路径中
所有编号的最小值，再给定一个$$m$$，使得$$\sum\_{i = 1}^{n} d(i) = m$$，不存在输出`-1`

**算法分析**
最少和最多，不难想，$$\min = n$$，是一条链，$$\max =  1 + 2+\cdots + n = \dfrac{n(n+1)}{2}$$，是星形图

> 对于其他情况呢？怎么构造？**先找根！**
![](/media/content_img/cf1033c.png)

上一篇：六月算法竞赛选题——概率与期望（二）下一篇：六月算法竞赛选题（四）

看完文章有啥想法