九月算法竞赛选题（一）

[[ slider_text ]]

[[ item.c ]]

九月算法竞赛选题（一）

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

并查集 状态压缩dp 分层图

## Codeforces Round 901 (Div. 2)
### C
**[C. Jellyfish and Green Apple](https://codeforces.com/contest/1875/problem/C)**
有$$n$$块青苹果，每块的重量是`1kg`，现在需要将其平均分给$$m$$个人
你可以进行若干次操作，每次选择一块青苹果，将其分成两块更小的青苹果，每块的重量都是原来的一半
现在问，最少需要多少次操作，使得每个人获得的苹果总重量都相同，如果无法实现平均分配，输出-1

**算法分析**
因为苹果的总量不变，所以每个人分到的苹果数量就是$$\dfrac{n}{m}$$，比如最后一个例子
每个人分到$$\dfrac{3}{4}$$，那么问题转化成，能否将$$\dfrac{3}{4}$$写成若干$$\sum\dfrac{1}{2^i}$$

不难发现，可以先让$$r = n \bmod m$$，将$$\dfrac{r}{m}$$化简之后，$$m$$**必须是 2 的幂**，否则无解

> 难点在于，怎么计算切割次数？

实际上可以模拟，令`tot = r`，如果$$tot \neq 0$$，不管怎么样，$$tot$$个苹果都必须对半切
答案的贡献是`ans += tot`，然后呢？此时又相当于，对$$tot \times 2$$个苹果尝试重新分配给$$m$$个人
即$$(tot, m) \to (2tot, m)$$，令$$tot' = 2tot$$，还需要$$tot' \bmod m$$个苹果，在下一轮中重新分配
这样迭代即可

### D
**[D. Jellyfish and Mex](https://codeforces.com/contest/1875/problem/D)**
给定一个由$$n$$个非负数组成的序列`a`，你会执行下面的操作$$n$$次
选择一个$$a_i$$删除，然后将`m += mex(a)`，现在问如果每次操作都是尽可能最优的
能够得到**最小的**$$m$$是多少？

**算法分析**
如果原序列没有`0`，那么答案就是`0`，否则呢？假设有$$k$$个`0`，因为要删$$n$$次
所以当这$$k$$个`0`都被删掉之后，剩下的值都是`0`了
于是，我们至少要有$$\geqslant k$$个非`0`的贡献

我们只考虑`[0, 1, 2, ..., MEX-1]`这几个数，手动模拟之后，发现最终的答案和每个数的出现次数有关
区别就在于说，$$mex$$值一开始是`MEX`，然后变小，**跳跃到某个值**之后，然后变成`0`
这个过程可以用动态规划来实现，以最后一个样例
```bash
3 2 2 1 1 0 0 0

(1) del 1, mex = 4
4: [3 2 2] [1] [0 0 0]

(2) del 1, mex = 1
1: [3 2 2] [0 0 0]

(3) del 0, del 0, mex = 1
1: [3 2 2] [0]

(4) del 0, mex = 0
之后都是 0

上述结果是，4 + 2*1 + 1 = 7
```
于是我们$$dp$$来处理这个跳跃的过程，$$dp(i)$$表示$$MEX \to i$$全部都删完了，当前的`mex`值是$$i$$
所需要的最小代价

然后枚举$$i$$跳到哪里，假设说下一步跳到$$j \in [0, i-1]$$这个位置，那么在我们把$$j$$删光之前
都会有$$i$$的贡献，我们先`del j`一共$$cnt_j - 1$$次，这几次贡献都是$$i$$
然后再删除`j`，此时`mex = j`，贡献是$$j$$，所以转移方程是（$$i$$从最初的 mex 往小了枚举）
```math
\displaystyle
\forall j \in [0, i-1], \quad dp(j) \leftarrow dp(i) + i \cdot (cnt_j - 1) + j
```

### F
**[F. Jellyfish and EVA](https://codeforces.com/contest/1875/problem/F)**
现在两个人从城市`1`要到城市`n`，给定的图是有向图
假设说现在两个人在城市$$u$$，两个人都会选择从$$u$$出发尚未被摧毁的道路，假设两个人选择的道路分别是$$v_1, v_2$$
如果$$v_1 = v_2$$，那么就能顺利到达$$v_1$$，否则$$(u, v_1), (u, v_2)$$两条道路被摧毁

如果从$$u$$出发，所有道路都被摧毁，那么任务失败
每次选择道路的时候，Jellyfish 都知道 Asuka 会随机选择道路，现在问，如果 Jellyfish 每次都最优选择道路
任务成功的最大概率是多少？

**算法分析**
首先，针对 DAG，很容易写出状态转移方程
```math
\displaystyle
dp(u) = \sum_{v \in G_u} dp(v) \cdot p(u, v)
```
不难发现，度数是确定的，也就是$$p$$相对来说是确定的，这样转移就仅仅取决于$$dp(v)$$的优先级
注意到$$p$$仅仅和$$u$$的**出度**有关，也就是说，一共有$$i = deg_u$$个数，选出`第 jth` 个数的方案数？（概率）

而这个问题中，类似**斯特林数**的递推，一共$$i$$个数，选到第`j-th`个数的概率是确定的
这个概率用$$g(i, j)$$来表示

如果$$j = 1$$，很显然$$g(i, 1) = \dfrac{1}{i}$$

如果$$j > 1$$呢？我们只考虑最后一次的操作，两个人分别选了什么数？
首先你要选到$$j > 1$$，就意味着你选不到$$[1\cdots j-1]$$，这些数都被删掉了
只考虑最后一次选了哪些数？首先 Jellyfish 一定选优先级是`1`的数，然后对方从$$> 1$$的数中选一个

1）如果选的是$$? \in [j+1\cdots i]$$的数，那么选中这些数的概率是$$\dfrac{i-(j+1)+1}{i} = \dfrac{i-j}{i}$$
接下来呢？$$j$$的优先级只减少`1`，子问题是在$$i-2$$个数中，选`(j-1)-th`

所以转移是$$\dfrac{i-j}{i} \cdot g(i-2, j-1)$$

2）否则的话，选$$? \in [2, j-1]$$中的数，选中的概率是$$\dfrac{j - 2}{i}$$
转移是$$\dfrac{j-2}{i} \cdot g(i-2, j-2)$$，此时`jth`的优先级变化了，你删掉`2 个`比`jth`小的数
那么接着你只需要找到第`(j-2)-th`的即可

```math
g(i, 1) = 1 / i \\

g(i, j) = \dfrac{j-2}{i} \cdot g(i-2, j-2) + \dfrac{i-j}{i} \cdot g(i-2, j-1)
```

将`g`数组预处理出来，然后呢？考虑`dp`，可以`dfs`先把$$u$$邻接的点的`dp(v)`先算出来
然后按照`dp`值，从大到小排序

对于`for j = 0 to G[u].size()-1`，令`v = G[u][j]`
转移就是$$dp(u) += dp(v) \cdot g(d_u, j+1)$$
最后$$dp(1)$$就是答案

### E
**[E. Jellyfish and Math](https://codeforces.com/contest/1875/problem/E)**
给定`5`个数$$a, b, c, d, m$$，一开始时候$$(x, y) = (a, b)$$，现在需要进行若干次操作
使得$$(x, y) = (c, d)$$，每次操作，可以进行以下之一
```math
x = x \textbf{ and } y \\
x = x \textbf{ or } y \\
y = y \oplus x \\
y = y \oplus m
```
问最少要执行多少次，才能使得最后到达$$(c, d)$$

**算法分析**
这个问题，很像最短路，如果不难发现位与位之间是独立的，如果对于第`i`位
对$$(a_i, b_i, m_i, c_i, d_i)$$压状态，不难发现一个位的状态有`32`种，那么总的代价是$$32^{30}$$，是承受不了的

一种比较自然而然的做法是，不要存这么多状态，有一些状态是可能达不到的

注意到，虽然每一位是独立的，但是题中位运算操作是**整体进行的**
也就是说，如果某些位出现了$$(a_i, b_i, m_i) = (0/1, 0/1, 0/1)$$
比如说`(ai, bi, mi) = (aj, bj, mj) = (0, 1, 0)`，那么$$i, j$$这两个位，能够到达的所有$$(c_i, d_i)$$都是一样的
不可能说是$$i$$这个位变换后到$$(c, d)$$，但是$$j$$这个位却变换到$$(e, f)$$
这种无解的情况，可以特判

> 来看状态压缩

注意到这里的状态$$(a_i, b_i, m_i)$$只需要$$2^3 = 8$$种，考虑它能走到的状态$$(c_i, d_i)$$有$$4$$种
可以称$$(a_i, b_i, m_i) \to (c_i, d_i)$$**建立了映射关系**，这种映射关系的状态压缩
```bash
(ai, bi, mi) with (ci, di)
```
可以考虑** 8 位 4 进制数**，这样复杂度就是$$O(4^8)$$，可以先预处理

这样做的时候，每一位可以单独出来看，假设说考虑$$(a_i, b_i, m_i, c_i, d_i)$$
就可以考虑`mask`，在`mask`的第$$k = (a_i, b_i, m_i)$$位，$$k \in [0, 8)$$
这一位的值置为$$v = (c_i, d_i)$$

每一位都这样考虑，我们就可以知道，所有出现过的$$(a_j, b_j, m_j) = (0/1, 0/1, 0/1)$$的终点应该走到哪里？
应该走到$$(c_j, d_j) = (0/1, 0/1)$$

这些信息就都压缩在了值`mask`中

但要注意，`mask`中，可能有一些位，即若干$$(a, b, m)$$组合**没有出现过**，那么这一位的值应该额外标记
所以应该用`5 进制`，`{0, 1, 2, 3}`表示$$(c_i, d_i)$$组合，而$$4$$表示这一位是空的，没有用到

对于没有用到的位，它转移到`{0, 1, 2, 3}`任何一个都是可以的，我们可以用`bfs`暴力打表状态的转移

> 然后考虑转移

具体的转移，可以打表所有$$5^8$$的状态，可以看成是一个**多源最短路**
枚举所有可能的$$(0/1, 0/1, 0/1) = (x, y, mi) = K$$，一开始的时候，第$$K$$位放$$(c_i, d_i) = (x, y) = v$$
因为此时$$(x, y, mi, x, y)$$对应的状态，它是初始状态，步数是`0`，将所有这样的状态存起来
```bash
let K = (x, y, m_i), v = (x, y)
mask += (5^K) * v
```
初始时候`dist[mask] = 0`，然后`bfs`，按照题中给出的条件模拟，具体来说
```bash
state = 队首元素，state 的第 K 位对应 (ai, bi, mi)

枚举 K in [0, 7] = (ai, bi, mi) = (0/1, 0/1, 0/1)，然后看一下 state 第 K 位的值 val
那么 (c, d) = (x, y) = (val >> 1, val & 1)

然后根据操作的类型，模拟 (x, y) --> (nx, ny)

最后返回新的状态
nsta = 在第 K 位的值置为 (nx, ny) = nval
```
这样就能够让`state -> nstate`转移了

> 特别地

注意到，有些位可能**没有用到**，那么这些位可以是`{0, 1, 2, 3}`任意的数
做完`bfs`打完`dist`表之后，枚举$$[0, 5^8)$$所有状态，从小到大
若这一位是`4`，那么尝试用`{0, 1, 2, 3}`来更新它
```bash
for state = [0, 5^8) 所有可能的状态，枚举 K = [0, 7] 每一位
	取出 state 在第 K 位上的值 val，如果 val = 4
	for x = {1, 2, 3, 4}，chmin(dist[state],  dist[state - (x << K)])
	（这里的左移，是针对 5 进制意义下的）
```

这样，最后的答案就是把题中给定的数，每一位可能出现的**数位对**给压缩起来
一开始`need = 44...4`，然后对于$$K = (a_i, b_i, m_i)$$，令`need`的第$$K$$位，置为$$val = (c_i, d_i)$$
求`dist[need]`就是答案

> trick

本例在实现的时候用到了一个技巧，把所有可能的状态都压缩到一个`mask`，至于那些**未出现的状态**
先不去管它，对`mask`进行整体转移，这样**出现的那些位**，它的转移情况都打表出来了
至于未出现的那些位呢？它的值可以任意放，做完一遍状态转移之后，再考虑将这些位放上任意的值
再取一遍最小值即可

## Codeforces Round 902
### D
**[D. Effects of Anti Pimples](https://codeforces.com/contest/1877/problem/D)**
**问题描述**
给定一个序列`a[1...n]`，所有元素一开始都是白色的，现在选择一个或者多个不同的索引
并且将索引上的颜色染成黑色，之后，你只要选择了某个$$i$$，那么**所有**下标是$$i$$的倍数的$$j$$
都会被染色成为绿色，现在定义分数，是所有染成黑色 and 绿色的下标的值$$\max a_i$$
问所有染色方案，对应的可能的分数的和

**算法分析**
不难想到，以题中的样例为例，算贡献，`ans += 19 * (19 作为最大值的方案数)`

如果钦定下标$$i$$一定要染成黑色，那么`for i 的倍数，取 max = 19`，此时的贡献至少应该是$$\geqslant 19$$
但不一定能取到`19`，如果你选其他一个黑色位置，这个位置的**价值**$$> 19$$，就不行了

所以可以先一轮预处理，把每个位置$$i$$
定义$$b_i = $$`i 钦定染成黑色，此时对答案的价值` = $$\max a_j$$，`j 是 i 的倍数`
比如样例中，$$b_i = 19$$，那么我们只要关心$$\leqslant 19$$的数有多少个，当然下标不能和$$i$$重叠了
假设说有$$c$$个，答案就是$$ways = 2^c$$（每个位置可以选或者不选）

为了保证不重不漏，可以对$$b$$进行排序，那么下标$$i$$处，$$\leqslant b_i$$的数就有$$i-1$$个
答案就是$$2^{i-1}$$

### E
**[E. Autosynthesis](https://codeforces.com/contest/1877/problem/E)**
给定一个长度是$$n$$的序列`a`，一开始所有元素都没有被圈出来，一次操作中可以圈出一个元素
同时允许多次圈出同一个元素
在完成所有操作之后，会构造一个序列$$r$$，由所有**未被圈出的**`a`中的元素，按照索引顺序组成
同时还会构造另一个序列$$p$$，其长度等于操作次数，$$p_i$$表示第$$i$$次操作中，被圈出元素的下标
现在要通过若干次操作，使得序列$$r = p$$，请输出序列`p`，或者报告不可能

**算法分析**
尝试从建图的角度来考虑，$$i \to a_i$$建一条有向边，不难看出，构成了一个**基环树**
注意到，每个点，$$(u \to v)$$有两种决策，一种选出点$$v$$，一种选入点$$u$$

1) 首先，对于入度为`0`的点$$i$$来说，它是不能出现在最终序列中的，因为没有一个`a[?]`会等于$$i$$
所以，对于入度为`0`的点来说，只能选**出点**，也就是对于有向边$$(i, j)$$
`vis[i] = 1`，表示`i`这个点选出点，也就是`(i,  ?)`，`i`不能被选，而应该选上`?`

2) 另一方面，如果`(?, to)`中，`?`被选上了，那么就意味着，`a[?]`值要被圈出来删掉
换句话说，如果`(?, to)`选了**入点**，那么它的邻接点**只能选出点**

根据以上分析，可以先拓扑排序，求出每条边选出点还是入点，这样选到最后，就只剩下简单环了

> 考虑简单环

处理到最后，这就是一个基环树森林，每个森林有一个简单环
对于简单环上的点，找到`vis[i] = 0`的点`i`，进队列，再进行一次拓扑排序，相当于选择了一个入度为`0`的点
然后按照上面的方法处理即可
```math
? \xrightarrow{-1} i \xrightarrow{+1} v
```
标记为`-1`，表示应该选`i`，标记为`+1`，表示应该选`a[i]`，如果既标记为`-1`又标记为`+1`，无解
否则的话，按照标记的模拟，选出最后的点即可

## AtCoder Beginner Contest 422
### F
**[F - Eat and Ride](https://atcoder.jp/contests/abc422/tasks/abc422_f)**
给定一个$$(n, m)$$的无向图，每个点有点权，当你访问节点$$i$$的时候，你的体重会增长$$w_i$$
当前你的体重是$$X$$，你要通过边$$(i, j)$$的代价，恰好是$$X$$
现在对所有$$v \in [1, n]$$，输出从`1`到这些点耗费的最小代价

**算法分析**
不难想到，如果要想代价最优，不可能走回头路，根据数据范围，可以猜到是$$O(n^2)$$的拆点
可以这样设计状态，$$(1, c)$$表示当前在$$1$$这个点（起点），还需要再经过$$c$$条边
而终点状态呢，$$(i, 0)$$表示到达了$$i$$点，不需要再经过边了

假设说从$$u$$出发，还有$$c$$条边要走，那么$$w_u$$贡献了$$c$$次，代价$$+c \cdot w_u$$

这样就设计状态，原图就转为了一个 DAG，可以 dp
```bash
初始化，最开始在 1 这个节点，可能有若干条边需要经过
for c = 0 to n:		dp[1][c] = 0;

for i = n - 1 downto 1
	for u = 1 to n, for v in G[u]
		then chmin( dp[v][i-1], dp[u][i] + w[u] * i )
```

### 分层图最短路
**上述的问题，实际上是分层图最短路模型**
分层图最短路模型，一般设计状态$$dp(i, u)$$，表示在第$$i$$层，或者经过了$$i$$条边
此时到达$$u$$点的最优代价，存在转移
```bash
for i = 0 to n-1, i-th level:
	for auto [u, v] : edges:
		chmax( dp[i+1][u],  dp[i][v] + cost(level i to level i+1)  )
```
特别地，分层图 dijkstra 可以如下来写
```bash
template <typename T>
class Graph {
public:
	
	void dijkstra(int s, vector<pint> &edges) {
        priority_queue<pair<T, int>, vector<pair<T, int>>, greater<pair<T, int>> > heap;
        dis.assign(_n+5, vector<T>(_n+5, inf<T>));
        dis[0][s] = 0;
        heap.push({dis[0][s], s});

auto dijkstra = [&](int i) -> void {

while (heap.size()) {
                T expected = heap.top().first;
                int x = heap.top().second;
                heap.pop();
                // if and only if, when dis[x] == exactly shortest path!
                if (dis[i][x] != expected) continue;

for (auto id : g[x]) {
                    auto [from, to, cap] = e[id];
                    int y = x ^ from ^ to;
                    if (dis[i][y] > dis[i][x] + cap) {
                        dis[i][y] = dis[i][x] + cap;
                        heap.push({dis[i][y], y});
                    }
                }
            }

if (i < _n) {
                dis[i+1] = dis[i];
                for (auto [u, v] : edges) {
                    chmin(dis[i+1][u], dis[i][v]);
                    chmin(dis[i+1][v], dis[i][u]);
                }

for (int u = 1; u <= _n; u++) {
                    if (dis[i+1][u] < dis[i][u]) heap.push({dis[i+1][u], u});
                }
            }
            return;

};

for (int i = 0; i <= _n; i++) {
            dijkstra(i);
        }
    }
	
};
```

## Codeforces Round 1005 (Div. 2)
### E
**[E. Mycraft Sand Sort](https://codeforces.com/contest/2064/problem/E)**
**问题描述**
给定一个排列`p`和序列`c`，在一个重力环境中，从上往下第$$i$$行，从左往右排列着$$p_i$$个颜色为$$c_i$$的方块
这些方块受到重力的影响，会往下掉，问有多少个不同的$$(p, c)$$，使得掉落的结果和初始时候相同

**算法分析**
> 观察一，第一列是不会变的

这意味着，如果需要交换行（交换排列），只能交换**颜色相同的两个不同的值（长度）**
所以可以对每种颜色$$c$$单独考虑，看一下对应的位置有几种长度可以选择？
比如说第一个位置有$$|sz|$$可以选，然后$$sz \cdot (sz-1) \cdots 1 = (sz)!$$，大致是这样
然后对每个$$c$$的答案$$\times$$起来

> 观察二，什么时候，$$i, j$$可以交换

首先，如果是连续的一段相同颜色，比如$$[l, r]$$都是同一种颜色，那么这个区间内的元素都可以互相交换
对于这样的块，可以用并查集维护，然后一个元素一个元素考虑过去
对于$$k$$位置的元素，它有$$|sz|$$种选择（$$sz$$是并查集的大小），然后再把$$k$$从并查集中**删掉**
考虑$$k+1$$位置的时候，它恰好有$$|sz| - 1$$种选择，这样恰好能够维护答案

> 观察三，对于中间相隔不同颜色的块呢，$$(i, k, j)$$中间隔了一个不同颜色的$$k$$，能否交换？

手动模拟一下，发现如果$$p_k > \min(p_i, p_j)$$，是不可以交换的，**不合法的**
（在纸上画图即可发现，交换之后会产生**不同颜色的拖尾**）

所以如果$$(i, j)$$**不可交换**，当且仅当
```math
\displaystyle
\begin{cases}
c_k \neq c_i \\
k \in [i, j] \\
p_k > \min(p_i, p_j)
\end{cases}
```

> 怎么计算？

我们发现$$(i, j)$$之间，$$< \min(p_i, p_j)$$的段，都是没有影响的，可以直接删掉
于是可以考虑按长度$$p_k$$从小到大去枚举，维护完答案之后，把这个长度的段删掉

根据之前的分析，我们需要维护**连续的，颜色相同的条**组成的联通块，然后按`len`从`[1...n]`考虑
假设我们当前考虑$$a_1 = len = 1$$，它所在的位置是$$i$$（注意是排列，位置是唯一确定的）

能够和$$i$$交换的，一定是$$i$$往左往右，**连续的，颜色相同的块**
因为是排列，任何一个其他的块，它的长度都会比$$len = 1$$来的大，$$i$$能交换，除非这些块颜色和它相同

即能交换的块，是$$i$$往左往右，颜色和$$i$$相同的块，中间不能被任何其他颜色不同的块阻隔
（因为其他任何颜色的块，长度都比它长，只要阻隔了，就换不过去了）

> 这启发我们用链表 + DSU 来维护

预处理的时候，并查集合并相邻的，颜色相同的段
接着，从小到大考虑$$len = 1 \to n$$的段，假设说当前的位置$$i = pos(len)$$
往左往右，和$$c_i$$颜色相同的段的个数，恰好是`dsu.sz( find(i) ) = cnt`，那么$$i$$这个位置恰好就有$$cnt$$种选择

考虑完之后，将$$i$$这个位置删掉，**并查集删，链表也要删，**这样接下来的`len`如果不和$$i$$相邻没影响
如果和$$i$$相邻，是$$i+1$$，此时`dsu.sz`恰好$$-1$$，符合要求的结果

具体来说
```bash
ans *= dsu.sz
then dsu.sz -= 1, and erase(i)
```
当并查集$$sz = 0$$的时候，说明$$i$$这个位置左右都没有连续的，相同颜色的段了，并且$$i$$也被删除了
这时候就意味着，链表中，$$l(i)$$和$$r(i)$$的元素，可以**尝试合并了**
和上面分析的一样，如果$$col(l_i) = col(r_i)$$，就可以合并$$l_i, r_i$$

此时，$$j = l(i)$$ 相当于**新的**$$a_1$$，继续如上过程

### 算法实现
```bash
void solve(int cas) {
    int n;
    cin >> n;
    vector<int> p(n+1, 0);
    for (int i = 1; i <= n; i++) cin >> p[i];

vector<int> c(n+1, 0);
    for (int i = 1; i <= n; i++) cin >> c[i];

DSU<int> dsu(n+5);
    vector<int> l(n+5, 0), r(n+5, n+1);

auto erase = [&](int i) -> void {
        l[r[i]] = l[i];
        r[l[i]] = r[i];
    };

map<int, int> pos;
    for (int i = 1; i <= n; i++) pos[p[i]] = i;

for (int i = 1; i <= n; i++) {
        l[i] = i - 1;
        r[i] = i + 1;
    }
    for (int i = 1; i <= n; i++) {
        if (i - 1 >= 1 && c[i-1] == c[i]) dsu.merge(i - 1, i);
    }
    
    mint ans = 1;
    for (int len = 1; len <= n; len++) {
        auto i = pos[len];
        auto rt = dsu.find(i);

ans *= dsu.sz[rt];

if (--dsu.sz[rt] == 0) {
            auto L = l[i], R = r[i];
            if (L >= 1 && R <= n && c[L] == c[R]) dsu.merge(L, R);
        }

erase(i);
    }

cout << ans << "\n";
}
```

## Codeforces Round 902
### F
**[F. Lexichromatography](https://codeforces.com/contest/1877/problem/F)**
**问题描述**
给定一个包含`n`个元素的序列`a`，现在要将序列中每个元素染色成红色或者蓝色，满足以下条件

- 允许把所有元素染成同一种颜色

- 要求序列`a`中没有任何不平衡子数组，也就是说，值为`k`的蓝色元素和红色元素个数，绝对值之差`< 2`

- 将所有蓝色元素按顺序组成一个子序列，红色元素也组成一个字序列，蓝色字序列字典序严格小于红色子序列

```bash
B R R B B R R B
1 3 1 2 3 2 3 3

考虑 B
1 2 3 3
考虑 R
3 1 2 3
满足条件
```
现在问染色的方案数

**算法分析**
> 首先，不平衡

这个限制很容易满足，对于同一个值为$$x$$的元素，它的染色方案一定是**红蓝交替**
所以看有几个不同的元素，假设有$$cnt$$个，每种不同元素的染色有$$2$$种，方案是$$2^{cnt}$$

考虑第一个限制，手动模拟后发现，如果字典序不同
```bash
3(R) 3(R) 3(R)
3(B) 3(B) ?(B)
```
此时值为`x`的数的个数一定是奇数，而染色的方案又是`RB`间隔，所以此时合法的方案是唯一的
将染色方案`RB`对换即可，原来染`R`的变成染`B`，原来`B`的变成`R`

注意到，只要字典序不同，（每一种元素单独考虑）那么`R B`染色方案，肯定是一半合法，一半不合法

所以答案大概是$$\dfrac{2^{cnt} - ways}{2}$$

> 考虑字典序相同的 RB 序列的方案数 ways

首先，如果存在一个值，出现的次数为奇数个，那么很显然`ways = 0`，此时直接输出答案
否则，每个值出现的次数都是偶数

考虑简单的情况，如果两个**不同的值**，它们出现的位置分别是$$[l1, r1], [l2, r2]$$，其中$$a(l1) \neq a(l2)$$
这两个线段彼此不相交呢？

如果彼此不相交，$$val1$$所在的下标集合$$(k\_1, k\_2, \cdots, k\_{m1})$$
和$$val2$$所在的下标集合$$(p\_1, p\_2, \cdots, p\_{m2})$$彼此独立
每一个集合看作一个**块**，可以得到`block`个不相交的块，$$ways = 2^{block}$$

从独立的块的角度，来分析相交的情况
```bash
l1 l2 r1 r2
R R  B B

R:		l1  l2
B:		r1  r2
此时恰好满足

l1 l2 r1 r2
R  B  B  R

R:		l1  r2
B:		l2  r1
此时呢？注意 a[l1] != a[l2]，不符合字典序相同这一个前提
```
所以**相交的块**，一旦确定了`l1`染什么颜色，那么一整个块的染色方案都被锁死了，每个块贡献的方案数是`2`

再来看包含的块
```bash
l1 l2 r2 r1
R  R  B  B

R:		l1  l2
B:		r2  r1
不符合字典序相同的条件

l1 l2 r2 r1
R  B  R  B

R:		l1  r2
B:		l2  r1
同样也不符合条件
```
所以字典序相同的情况，只有可能是线段之间相交，而不会是包含

先特判一下，存在包含的情况，如果存在不同值的下标区间相互包含，`ways = 0`
否则，可以用**并查集**合并之前说的**独立相交的块**，答案是$$(2^{cnt} - 2^{block}) / 2$$

> 最后只需要考虑这个块数`block`怎么求

可以预处理每个颜色出现的相邻位置，打表成线段$$[l_i, r_i]$$，然后`for i = 每一条线段`
考虑$$j = i+1 \cdots$$开始，**极大的相交段**，这些段恰好组成一个块

如果$$l_j \leqslant r_i$$，那么可能构成极大相交段，check 一下右端点
如果$$r_j \leqslant r_i$$，那么就发生包含的情况，不合法$$way = 0$$，否则就合法

考虑$$(p, q) = (l(b\_{j-1}), l(b\_j))$$，将$$a_p, a_q$$并查集合并，最后统计的时候
`dsu.find(val) == val`，就意味着一个新的块，`block++`

注意更新的时候，要同时维护$$ri = \max(ri, rj)$$

**这样的写法要注意的细节比较多**
实际上，可以这么来写，对每个不同的值，记一下`cnt[ a[i] ]`，表示它出现次数是奇数还是偶数
如果是奇数，把它放到$$R$$集合中，否则把它放到$$B$$集合中，同时维护一个全局`sgn = maxv`

如果当前的值，出现奇数次，那么就`sgn += 1`，否则就`sgn += 0`，动态维护`sgn`
```bash
sgn -= (cnt[ a[i] ] % 2 != 0)
cnt[ a[i] ] += 1
sgn += (cnt[ a[i] ] % 2 != 0)
```
这样当且仅当$$sgn = maxv$$的时候，表示**走完了一个块**，$$p \in [j\cdots i]$$假设说构成完整的块
将块中的值$$a[p-1], a[p]$$并查集合并，`tot`记一下一开始并查集有多少个不同的数，如果成功合并了，`tot -= merge(a[p-1], a[p])`

**判断字典序是否相同**，直接看$$R = B$$是否满足，如果满足，那么$$ways = 2^{tot}$$
最后带入$$(2^{cnt} - ways) / 2$$计算即可

**算法实现**
```bash
const int N = 2e5;

void solve(int cas) {
    int n;
    cin >> n;

vector<int> a(n+1, 0);
    int mx = 0;

map<int, int> cnt;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        chmax(mx, a[i]);
        cnt[a[i]] += 1;
    }

int tot = cnt.size();
    mint res = power(mint(2), tot);

bool hasodd = false;
    for (auto [key, num] : cnt) {
        if (num % 2) {
            hasodd = true;
            break;
        }
    }

if (hasodd) {
        cout << res / 2 << "\n";
        return;
    }

DSU<int> dsu(N+5);
    vector<int> R, B;
    int sgn = mx, j = 1;

vector<int> num(N+5, 0);
    for (int i = 1; i <= n; i++) {
        auto x = a[i];
        if (num[x] % 2 == 0) R.emplace_back(x);
        else B.emplace_back(x);

sgn -= (num[x] % 2 != 0);
        num[x]++;
        sgn += (num[x] % 2 != 0);

if (sgn == mx) {
            for (int p = j; p + 1 <= i; p++) {
                dsu.merge(a[p], a[p+1]);
            }
            j = i + 1;
        }
    }

int same = 0;
    if (R == B) {
        for (int x = 1; x <= N; x++) {
            if (!cnt.contains(x)) continue;

if (dsu.find(x) == x) same += 1;
        }
    }

if (same != 0) res -= power(mint(2), same);
    
    auto ans = res / 2;
    cout << ans << "\n";
}
```

上一篇：八月算法竞赛选题（一）下一篇：九月算法竞赛选题（二）

看完文章有啥想法