八月算法竞赛选题（一）

[[ slider_text ]]

[[ item.c ]]

八月算法竞赛选题（一）

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

回文树 and卷积

## 2025牛客暑期多校训练营9
### C
**[Epoch-making](https://ac.nowcoder.com/acm/contest/108306/C)**
**问题描述**
给定$$n$$个点的有向无环图，每个点有点权，每次可以选择一个入度为`0`的子集删除
代价是子集中点权的最大值，问删完所有的点需要的最小代价，$$n \leqslant 24$$

**算法分析**
最暴力的做法
```math
dp(S) = \begin{cases}
0 & V = \empty \\
dp(S - V) + w(V) & V\text{ 的入度为 0}
\end{cases}
```
枚举所有可能的集合，$$w(V)$$可以$$O(n2^n)$$预处理
直接枚举$$S$$，并且枚举$$S$$的子集$$V$$，复杂度是$$O(3^n)$$的

这种子集 dp 的优化，一般考虑** AND 卷积**
仔细分析一下，一旦我们选择了删去集合$$V$$，它的权值是`w`，那么$$V$$中，所有权值$$\leqslant w$$的点都会一并删去
这启发我们可以根据**权值从小到大排序**，然后删除某个位`j`的时候，所有`< j`的且为`1`的位都要删去

具体来说，先对权值从小到大排序，然后状态压缩，构建依赖关系，$$(U, V) \to (u, v)$$
先将给定的依赖关系，映射到**排序后的依赖关系**，`sta[v] |= (1<<u)`，表示删除`v`，也需要一并删除`u`

记忆化$$dp(S)$$，考虑** AND 卷积**来优化
枚举不在$$S$$中的点`j`，尝试将其加入集合，根据之前的分析，我们不是一位一位的加
而是从低位到高位考虑**一段前缀**，能加入的`j`都加入，这里用`cur`表示当前所有能加入的点
`cur`是**连续的一段，能加入集合中的前缀**，$$dp(S) \to dp(S \mid cur) + w(j)$$

什么样的$$j$$满足呢？
```bash
考虑 j 的依赖关系 sta = sta[j]
sta 中的某一位 ? 是 1，那么 S 中 ? 位也必须是 1，因为依赖要提前删掉
sta 中的某一位 ? 是 0，那么 S 中 ? 可以是 0 也可以是 1

换句话说，sta[j] & S >= sta[j]，这样的 j 才能被加入，cur |= (1 << j)
```

> 优化的核心是，从小到大排序，低位到高位能加入的都加入

## 2025牛客暑期多校训练营10
### F
**[Sensei and Yuuka Going Shopping](https://ac.nowcoder.com/acm/contest/108307/F)**
有$$n$$件商品，每一件商品有一个独特度$$a_i$$，现在要把序列分成**三部分**，对于独特度$$x$$
如果它在**三部分**中都出现了，说明它是普遍的，我们现在想要一种划分，使得普遍的商品数量最多
输出最多的，普遍的商品的数量，以及一个最优划分

**算法分析**
考虑$$x$$每一个出现的位置，$$totpos(x) = \\{j_1, j_2, \cdots j_k, \cdots, j_m  \\}$$
枚举中间的位置，考虑**恰好在这个位置之后切断**，我们记$$j$$最后出现的位置是$$R$$

首先，只要$$j$$不是最后一个位置，那么钦定在$$j$$处切断，$$[j+1\cdots]$$一定会产生一个$$x$$
那么我们枚举$$j$$，考虑用数据结构，维护并查询一个最优的$$i$$，那么$$[i, j]$$就是答案

那么哪些$$i$$满足要求呢？从最左边的$$L(x)$$（即 x 第一次出现的位置）开始到$$j - 1$$都是可以的

考虑用扫描线
```bash
map<int, vector<int> > totpos
totpos[x] = {j1, j2, ..., jm}

对于每一个 x，枚举 j in pos = totpos[x]
	如果 j 不在最左边，那么 [pos[0]...pos[j]-1] 都会 +1 (都可以作为左端点切开)
	考虑从小到大遍历 j，然后一段一段加
	
	每一个 j，[pos[j-1], pos[j]) 都会 +1，这样就不会重复了，封装成事件
	挂载到 evts[ pos[j] ] 上
	
	当 j = pos.back() 的时候，走完了，一整段 [pos[0], pos.back()] 都要 -1，清空
```
在上述过程中，实时维护`最大值`即可

> 注意，上述实现中，每次划分成$$[pos[j-1], pos[j])$$离散的段加入，正好会不重不漏

## 2025牛客暑期多校训练营9
### H
**[Counter Streak](https://ac.nowcoder.com/acm/contest/108306/H)**
一个每日签到系统可以通过调整设备的时区来维持连胜，给定一些在`UTC+8`的提交记录
你可以将其改成`UTC-12`到`UTC+14`中的任意位置，问这样修改之后，最长连胜天数的最大值和最小值

**算法分析**
注意到天数可调整的范围最小也是$$2$$，所以最坏情况，都选偶数天或者都选奇数天，这样最小连胜天数就是`1`

> 在 c++20 中可以使用`chrono`头文件，使用日期类

对于`Date`，可以用`year_month_day Date{y, m, d}`来转化成**日期类**
再通过`sys_days Day = Date`转化成**系统时间**

系统时间是不够我们处理的，转化成**区间问题**，应该考虑**偏差**
定义`year_month_day ephoch{ 0, 1, 1 }`为基准，令`diff = Day - ephoch`
用`x = diff.count()`转化成离散的点来保存

这样，每个记录都映射成了一个具体的值`x`，排序，然后 dp 即可

> 注意到，每条记录中，能够表示的天数，最少是`2`，最多是`3`天

那么这个问题可以考虑`dp`，类似**状态机**类的转移，$$dp(i, 0 \sim 2)$$表示以$$i$$结尾
状态是$$0 \sim 2$$天的最长连续天数

（状态的意思是，当前记录修改成`x0, x1, x2`，处在哪一个`x`）

对于$$i-1$$阶段，枚举上个阶段处在的状态$$j \in [0, 3)$$，若$$j \geqslant |S\_{i-1}|$$，那么不合法
令$$x = S(i-1, j)$$，然后再枚举当前的状态$$k \in [0, 3)$$，令$$y = S(i, k)$$

考虑$$x \to y$$的转移
若$$dp(i-1, j)$$非法，那么很显然$$dp(i, k) \xleftarrow{\max} 1$$

否则的话，若$$y = x$$，说明是同一天，$$dp(i, k) = \max(dp(i-1, j), 1)$$
若$$y = x + 1$$，有转移$$dp(i, k) \leftarrow dp(i-1, j) + 1$$

### I
**[Tree Construction](https://ac.nowcoder.com/acm/contest/108306/I)**
有两棵结构一样的数，边权不同，但都是非负，已知两棵树上**所有节点对**的距离$$D(u, v)$$
给你两个$$d1(u, v), d2(u, v)$$，你只知道这两个距离值，但不确定它们分别属于哪棵树
给定这组被打乱的$$d1(u, v), d2(u, v)$$，要求构造可能的两棵树

**算法分析**

> 先回顾一下**所有节点对最短路径**的 floyd 算法

以**经过的最大编号的节点**作为`dp`的阶段，$$dp(k, i, j)$$表示经过的最大节点编号**不超过**$$k$$，
此时$$(i, j)$$的**最短路径**

对于编号是$$k$$的节点，套路地，分别考虑选/不选
如果不选（不经过）$$k$$，那么就从$$dp(k-1, i, j)$$转移
如果经过$$k$$，那么$$i \to k \to j$$，转移是$$dp(k-1, i, k) + dp(k-1, k, j)$$
```math
\displaystyle
dp(k, i, j) \leftarrow \min(dp(k-1, i, j), dp(k-1, i, k) + dp(k-1, k, j))
```

换句话说，floyd 算法的递推，所有最短路径都使用点集$$A = \\{1, 2, \cdots, k-1\\}$$
然后逐渐扩张这个点集$$A$$，尝试加入点$$k$$，那么决策是，要么完全不经过$$k$$
要么使用$$k$$，$$\min(last(i, j), last(i, k) + last(k, j))$$，然后点集扩张成$$A = \\{1, 2,\cdots, k\\}$$

> 这个问题可以从 floyd 算法借鉴一下思路

如果没有交换的情况，也就是说，所有的$$d1(u, v) = d2(u, v)$$，那么可以考虑**最小生成树**的构造方法
但现在有交换，注意到$$d1(u, v) + d2(u, v)$$是不变的，也就是对**所有节点对而言**，$$d1 + d2$$都是确定的

那么树的形态可以还原出来，根据$$d1(u, v) + d2(u, v)$$，构造最小生成树即可

> 那么下面的问题转化成，如何从最小生成树中，**分裂**出一棵树，使得它每条边的权值恰好是$$d2(u, v)$$

这个可以用 floyd 类似的分析方法，维护**已经被分离出来的点集**$$R$$，然后`dfs(x, y)`，考虑$$x \to y$$
其中令$$w1 = d1(x, y), w2 = d2(x, y)$$，这两个值是问题中**已经给出来的**

考虑递推扩展点集$$R$$，点集中**所有点对**之间的距离应该是已经**维护**好了，分别是$$dp1(u, v), dp2(u, v)$$
递推考虑$$x \to y$$，尝试把$$y$$加入$$R$$集

```bash
w1 = d1(x, y), w2 = d2(x, y)
这是题中已经给出的确定值

for z in 点集 R，考虑 x->y，尝试把 y 加入点集
	令 exp1 = dp1(z, x) + w1,		exp2 = dp2(z, x) + w2
	这是我们所期望的 z-->y 的值，而他们实际的值已经给出了，是 d1(z, y), d2(z, y)
	如果 exp1 != d1(z, y) or exp2 != d2(z, y)，那么需要交换 w1, w2
	
	接着考虑更新 dp 值，把 y 加入 R 并维护
	dp1[z][y] = dp1[y][z] = dp1[z][x] + w1
	dp2[z][y] = dp2[y][z] = dp2[z][x] + w2
```

## AtCoder Regular Contest 203
### A
**[A - All Winners](https://atcoder.jp/contests/arc203/tasks/arc203_a)**
淘汰赛，`n`支队伍，每支队伍有`m`个人，比赛采用循环赛制，进行$$n(n-1)/2$$轮
随机对阵，总是一方获胜，一方失败，每位选手恰好进行了$$n-1$$轮比赛，赢得所有比赛的人将获得完美记录
问最多能有多少个胜者（指获得完美记录）

**算法分析**
一种最直接的想法，是钦定第一队的能力值最强，那么所有比赛都是第一队赢，答案是$$m$$
但很快就发现，当$$n$$很大的时候，这是不对的，因为$$1 \sim m$$你所有获胜位置，都分配给了第一队
那么其他队就没有机会了，同时也发现，每个队伍，win 的人数的上界就是$$m$$

要给其他队伍一点机会
考虑$$n = 2, m$$是偶数的情况，我们发现第一队前一半永远赢，后一半永远输
第二队前一半永远输，后一半永远赢，这样是不劣的
就这个想法出发，不难发现，总共$$n \cdot m$$个人，可以产生$$nm / 2$$个胜者，那我们尝试构造

> 尝试构造

用`win1, win2, ...`分别表示最强的，第 2 强的，以此类推
同时用`lose1, lose2, ...`分别表示最弱的，第 2 弱的，以此类推
```bash
win1  lose1
win2  lose2
.....
```
这样去构造，发现第 1 队的`m / 2`个人可以完胜，第`2`队呢？第二队的`win2`可以战胜剩下的`n - 2`支队伍
但是战胜不了第一支队伍，要想达成完胜，那么就让`win2 <--> lose1`，让第二队的`win2`组和第一队的`lose1`组比
这有点田忌赛马的味道，保证自己有机会战胜所有队伍的同时，也保证其他队伍都有机会能够战胜自己

这样构造，就可以有$$(m / 2) \cdot n$$个人可以完胜

> 那么$$m$$为奇数呢？

不外乎就是多出了一个人，$$m - 1$$可以按偶数处理，多出的这个人，我们钦定他的能力是最强的
分配给第一队，那么他也是可以完胜的，所以此时是$$(m - 1) / 2 \cdot n + 1$$

## AtCoder Beginner Contest 419
### E
**[E - Subarray Sum Divisibility](https://atcoder.jp/contests/abc419/tasks/abc419_e)**
给定一个长度是$$n$$的序列$$A$$，你每次可以将任意元素`+1`，问最少要几次操作
使得任意长度为$$L$$的子序列（必须连续）的**和是$$M$$的倍数**

**算法分析**
考虑$$i \to i+1$$递推，关于长度为$$L$$的子序列，他们的和`mod M`会怎么变化
对于$$i$$，不妨设`S = a[i+1] + ... + a[i+L-1]`，那么从$$i \to i + 1$$递推的时候
```math
\displaystyle
(a_i + S) \equiv 0 (\bmod M), \quad (a_{i+L} + S) \equiv 0 (\bmod M)
```
从而一定有$$a(i) \equiv a(i+L) (\bmod M)$$

因为$$M$$很小，可以暴力打表，$$r = a_i \bmod M$$，暴力每一个位置$$i \in [0, L)$$
钦定这个位置改成了$$val \in [0, M-1]$$（只关心余数），所需要的总代价$$cost(i, val)$$，这个总代价可以暴力计算出来
只需要把$$a_i$$放到$$i \bmod L$$对应的桶中，统计即可

最后做的时候，考虑`dp`，$$dp(i, x)$$表示$$i \in [0, L)$$这些位置，前缀和是$$x$$需要改动的最小代价
枚举上一次的前缀和$$x$$，以及当前$$i$$这个位置，$$\bmod m$$的余数改成$$y$$
转移是$$dp((x+y) \bmod m) \leftarrow dp(x) + cost(i, y)$$

## AtCoder Regular Contest 203
### B
**[B - Swap If Equal Sum](https://atcoder.jp/contests/arc203/tasks/arc203_b)**
**问题描述**
给定一个只有`0/1`的长度为$$n$$的序列$$A, B$$，现在你可以选择**不相交**的区间，用`a, b, c, d`表示
```math
\displaystyle
1 \leqslant a \leqslant b < c \leqslant d \leqslant n \\
\sum_{i = a}^{b} A_i = \sum_{i= c}^{d} A_i
```
然后交换区间$$A[a, b]$$和$$A[c, d]$$，问能不能通过若干次操作，将$$A \to B$$

**算法分析**
明显的无解，就是`a, b`中`1`的个数不一样

考虑**哪些位置需要 0，哪些位置需要 1**

> 考虑需要 0

注意到，可以交换形如`[1]   [0  1]`这样的位置，可以把`0`移动到前缀任意位置
这样前缀需要`0`就解决了

同时，这样的移动，还可以构造出形如
```bash
0 0 0 0 ... 0 1 1 ... 1
0 1 0 1 0 1 0 ... 1 0 1
```
的序列，构造出这样的序列有什么好处呢？形如`0 1 1`，可以交换`[0 1] [1]`，这样形成了`1 0 1`
那么`[1 0] [1]`也就可以交换，这样这个`0`就可以去到后缀任何一个位置，后缀需要`0`也解决了

> 考虑需要 1

因为我们可以构造出`0 1 0 1 0 1...`，那么需要`1`的位置一定是`0`，我们先在这个位置构造出`0 1`的结构
然后将`0 1`和其他位置的任何一个`1`交换即可

换句话说，当`1`的个数$$\geqslant 2$$的时候，总是可以满足

> 考虑`1`的位置仅有`1`

注意到，此时只能交换`0`的段
如果这个`1`在`1 or n`处，不管怎么样都换不去其他位置，所以必须和`b`匹配，否则无解
如果`1`的位置在`[2, n - 1]`，我们可以通过调整前后缀`0`的长度，来把`1`换到任何一个位置
但唯独换不到`1 or n-1`，如果$$b$$中的`1`在这两个位置，就不满足了，其他都可以满足

## Codeforces Round 873 (Div. 2)
### D1
**[D1. Range Sorting (Easy Version)](https://codeforces.com/contest/1828/problem/D1)**
给你一个$$n$$个**不同的数**组成的序列$$a$$

定义一个数组的美丽度$$p_1, p_2, \cdots, p_k$$是使用任意次数的区间排序操作，将数组变得有序
所花费的最少时间
区间排序操作如下
选择$$l, r, \quad l < r$$，将$$[l\cdots r]$$排序，耗时$$r - l$$秒
计算数组$$a$$的所有子数组的美丽度之和，子数组要求连续

**算法分析**
这个问题$$n$$比较小，所以可以$$O(n^2)$$暴力$$[l, r]$$，看一下能否常数时间算出关于$$[l, r]$$的答案
一种比较极端的情况，比如`a[r] = x`
```bash
区间前缀都是 > x
[l, r] = [ > x 的数 ] [x]
```
那么这个时候的答案是$$r - l$$，但是**有时候前缀是无效的**
```bash
[l, r] = [ ... < x 的数 ... ] [... > x 的数 ...] [x]
```
这种情况下，前缀`< x`的数都是无效的，我们应该把`[ ... > x 的数 ... ]`这一段给剔除
这可以用**单调栈实现**，只要`> x`就弹出，这样栈中就保留了`[ x1 < x2 < ... (所有 < x 的数) ]`
这些数都是无效的，所以此时对答案的贡献是`ans += r - l - stk.size()`

接下来考虑怎么去递推，从$$r \to r+1$$，假设新加入的数是`y`，`[.... 左边第一个 < y 的] [y]`
这样`[... 左边第一个 < y]`这部分前缀就是无效的，下面考虑怎么快速递推求出来
如果直接`for`或者再单调栈，那么算法就会退化成$$O(n^2)$$

但注意到，因为你前面排了$$x$$，也就是说`[l ... (< x 的数 i)] [x < x1 < x2 < ... < ?] [y]`
你排序至少要排到`(最后一个 < x 的数的位置 i)`，接着排`y`，要么不排，
要么只能在$$i$$更往左，不可能再往右了，所以只要维护`mx = max(弹出栈的所有元素, a[j] = x)`

你要继续排序$$y$$的话，`{弹出栈的所有元素, a[j] = x}`一定会被再次弹出的，因为针对$$x$$的排序已经弹出了它们
**把最大值重新放到栈中**，要么`mx < y`，不排`y`，要么继续单调栈处理`y`

所以递推转移，只需要把`mx`插入`stack`中即可

### D2
问题复杂一点，此时$$n = 10^5$$，意味着$$O(n^2)$$的算法是无法通过的
咋看好像有一点思路，比如`[c, e, b, a, d] [m, l, p]`（用字母表示相对大小）
发现把`[c, e, b, a, d] [m, l, p]`**两段分别排序**的代价，是要优于整体排序的
```bash
[l...r] 排序的代价 r - l
[l...k] [k+1...r] 排序的代价 (k - l) + (r - k - 1) = r - l - 1
```
可以发现，每存在一个分割点$$p$$，排序的代价就会**减少`1`**，这样可以考虑**反着求**

一开始先令所有子区间都全部排序，代价是
```math
\displaystyle
tot = \sum_{len = 1}^{n}(len - 1) \cdot (n - len + 1)
```
这样，算代价转化成**求方案数**，`ans = tot - (中间存在分割点 p 的子区间的方案数)`

> 什么时候存在分割点？

考虑$$[l, k] \cup [k+1, r]$$，一定是$$\displaystyle \max\_{i \in [l\cdots k]} a\_i < \min\_{i \in [k+1\cdots r]}a_i$$，那么$$k$$就是分割点

这类等式的处理，一般都是枚举，并钦定最小值/最大值为$$a_i$$，$$a_i$$一定要选
然后看哪些区间会以$$a_i$$作为最小值，求出这样的$$[li, ri]$$，继续分析

> 继续分析，考虑成为“分割区间$$[li, ri]$$”的方案数

枚举并钦定$$a_i$$为最小值，那么可行的区间，往左边找到第一个下标$$p$$，满足$$a_p$$是左边第一个$$< a_i$$的
这可以单调栈来求，同样，也可以单调栈求出右边第一个$$< a_i$$的位置，它的前一个位置是$$R$$
那么$$[p+1\cdots i \cdots R]$$都是以$$a_i$$作为最小值的，我们钦定要包含$$a_i$$
所以$$ri$$有几种选择呢？`ri in [i...R]`都可以，$$ri$$有$$R - i + 1$$种选择

那么左边呢？左边是钦定要包含$$a_p$$的，因为$$a_p < a_i$$，这样才能满足分割的条件
但实际上，$$li$$还可以再往左
实际上，左端点就是要找到一个$$li \in [L, p]$$，满足$$\max[L\cdots p] < a_i$$的`min-left`作为$$L$$
那么$$li$$有$$p - L + 1$$种选择，这可以**ST 表维护区间 max，然后二分这个 L，check 函数用 ST表**$$O(1)$$区间查询
线段树二分也是可以的

综上所述，每个$$i$$，都需要减去$$(p-L+1) \cdot (R-i+1)$$

### E
**[E. Palindrome Partition](https://codeforces.com/contest/1828/problem/E)**
子串是指给定字符串中，连续的且非空的一段，偶回文串是长度为偶数的回文串
美丽串，是指偶回文串，或者可以分割成若干个更小的偶回文串的字符串
给定一个字符串`s`，判断美丽子串的数量
比如`abbaaa = {abba} {aa}`，可以拆分成`2`个偶回文串，所以它是美丽串

**算法分析**
这个问题不难写出状态转移方程
```math
\displaystyle
dp(i) = \left( \sum_{j}dp(j) \right) + 1
```
其中，$$[j+1, i]$$是**偶回文串**

但是这样会重复计算，因为一个偶数长度的回文串，可能由长度更小的偶回文串拼接起来
比如`AABBCC`，计算的时候`[AA BB] + [CC]`算了一次，`[AA] + [BB CC]`又被计数一次
怎么样保证不重不漏呢？

**每次只加入一个最短的回文后缀**
对于$$i$$这个位置，只考虑以$$i$$结尾的，**最短回文后缀**的长度
在回文自动机上用$$g$$维护，这里$$g(u)$$针对的是 **PAM 上的点**$$u$$，沿着`fail 树`能找到的最短回文长度
怎么维护呢？
首先$$g(u) = g(fail(u))$$先继承过来，如果发现$$g(u) = 0, len(u)$$是偶数，那么说明$$u$$这个点没有更短的回文后缀
此时$$u$$代表的一整个串就是**最短回文后缀**，所以$$g(u) = len(u)$$

这样维护完了之后，回文自动机在线添加的时候，考虑$$mn(i) = g(last)$$
这样，$$dp(i) = dp(i - mn(i)) + 1$$

上一篇：七月算法竞赛选题（三）下一篇：九月算法竞赛选题（一）

看完文章有啥想法