十二月算法竞赛选题（二）

[[ slider_text ]]

[[ item.c ]]

十二月算法竞赛选题（二）

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

数据结构优化dp

## Educational Codeforces Round 165
### D
**[D. Shop Game](https://codeforces.com/contest/1969/problem/D)**
商店有$$n$$件商品，Alice 和 Bob 在玩游戏，Alice 进货一些商品（可以不进货），进货价是$$a_i$$
然后 Bob 从 Alice 进货的商品中去买一些，Bob 的购买价是$$b_i$$
如果进货商品$$\leqslant K$$，Bob 免费拿走所有的商品
否则，Bob **任选**其中的$$K$$件拿走，然后剩下的对应付钱，编号`i`的商品，付给 Alice `b[i]`
现在 Alice 希望最大化自己的利润，而 Bob 目标是最小化 Alice 的利润
求上述条件下，最大化的利润

**算法分析**
> 动态规划

对每一件商品
```bash
earn:  b[i] - a[i]，earn <= 0 的一律不进货
cost:  -a[i]
loss: 如果 Bob 选择白嫖商品，不仅仅 earn 这么多的钱赚不到，还要倒贴 cost = -a[i] 的钱
		cost[i] - earn
```
状态转移如下
```bash
dp(i, B, K)
表示当前考虑商品 i，买/不买，白嫖/不白嫖，最小利润

1.不买，不白嫖
dp(B, K) <-- last(B, K)

2.买，不白嫖
dp(B, K) <-- last(B-1, K) + earn

3.买，白嫖
dp(B, K) <-- last(B-1, K-1) + (earn + loss)

最后的答案是枚举买的商品 for B = K+1 to n
	chmax(dp(B, K))
```

> 动态规划的复杂度显然不对，考虑优化，有没有贪心性质
假设说 Alice 买了$$S$$件商品，需要选$$k$$件来供 Bob 白嫖，Bob 会怎么选？
可以猜到，Bob 的选择方式差不多是固定的

假设说当前$$S$$件商品，如果不让白嫖的话，Alice 可以赚的钱是$$tot$$
如果商品$$i$$被白嫖，$$tot = tot - earn_i - cost_i = tot - (b_i - a_i) - a_i = tot - b_i$$
（不仅原来的利润赚不到，还要倒贴成本$$a_i$$）
那么 Bob 就一定会选择$$S$$中，$$b$$最大的$$k$$个数

那么自然想到，根据$$b$$从大到小排序，划分成两个集合，$$A = [0, k), B = [k, n)$$
先初步这样划分，假设说当前 Alice 能**赚的钱**是`resA, resB`（两个集合分开）
对于$$i \in A$$，这个商品对`resA`的贡献是`-a[i]`（纯倒贴钱）
对于$$i \in B$$，这个商品对`resB`的贡献是`max(0, b[i] - a[i])`

> 但这样不一定是最优的，但可以确定的是，最优解一定是$$\subseteq A$$，扔掉$$A$$中的一些商品
然后再从$$B$$中拿一些元素放到$$A$$中，补齐到$$k$$个

令$$res = resA + resB$$，如果我们选择**扔掉**$$A$$中的商品$$x$$，加入$$B$$中的商品$$y$$，会怎么变化？
```bash
扔掉，resA = resA - (-a[x])
从 B 集合挪到 A 集合,  resB -= max(0, b[y] - a[y]), resA += (-a[y])
```
注意到，如果不考虑$$b_y - a_y \leqslant 0$$的情况，$$res = res + a_x - b_y$$
因为 Bob 决策的确定性，总是偏向于选择`b`较大的，所以$$b_y$$是确定的
就是剩下的元素中$$b$$最大的那个（这一点从大到小排序很容易满足）

那么 Alice 需要最大化它的利润，Alice 要尽可能选$$a_x$$较大的
而$$a_x$$哪里来呢？$$a_x \in A$$，如果要扔掉$$A$$中的一些商品，一定是扔掉$$a_x$$最大的几个
可以用**大根堆**来维护集合$$A$$

考虑枚举每个$$j \in B$$，扔掉$$A$$的堆顶元素，加入商品$$j \in B$$
此时的`res`，然后更新答案

> 坑点

按道理说，在$$B$$集合中，是不是只需要考虑$$b_i - a_i > 0$$的元素呢？
这样会导致最优解错误，为什么呢？
假设说，$$B$$集合中，有一个`(a 很小, b 却很大)`的商品，我们按道理是不会去买这个商品的

但是，我们可以把它加入到$$A$$集合中让 Bob 白嫖，这样只需要花费很小的代价
比如`(a[i], b[i]) = (1, 9999)`，让`bob`白嫖，只需要`-1`的代价
所以枚举的时候，每个元素都要考虑进去
对于每一件商品，按照$$\max(0, b_i - a_i)$$来算贡献才是合适的

## Codeforces Round 1070 (Div. 2)
### D
**[D. Fibonacci Paths](https://codeforces.com/contest/2176/problem/D)**
给定一个有向图，每个点有权值，问简单路径的数量，满足
简单路径至少要有 2 个点，路径上的点，对应的点权，构成广义斐波那契数列
其中`a[1], a[2]`头两项的值任意，其余的项必须满足`a[i] = a[i-1] + a[i-2]`

**算法分析**
> 注意到以下几点性质

1.因为$$a_i = O(10^{18})$$，实际上，可能的斐波那契路径长度，最长是$$O(\log)$$的
2.斐波那契数列，能不能继续扩展，只和最后两项有关

3.如果得到一个很长的斐波那契数列，$$(fib\_1, fib\_2)$$作为头两项，如果从$$i > 2$$截断
那么$$(fib\_{i}, fib\_{i+1})$$作为头两项，仍然构成斐波那契数列

4.斐波那契数列构成的图，是一个 DAG，因为每一项都是单调递增的，不可能有返祖边

> 这样可以设计一个记忆化 dp

拆点，注意到斐波那契的路径长度最长就是$$O(\log)$$，假设说$$v$$可以作为斐波那契的起点
那么符合条件的$$(pre_v, v)$$数量也是$$O(\log )$$的
需要记一下以$$v$$结尾，最后两项的和为`S`的方案数$$dp(v, S)$$
同一个点可能会对应成多个不同链的结尾，有不同的最后两项和
即`(v, s1), (v, s2), ....., (v, sk)`，其中$$k = O(\log)$$

```bash
对于(x, y)，如果 a[y] = s
	(从 x 开始扩展，并且最后两项的和是 s 的方案数) += (从 y 开始扩展，并且最后两项和是 a[y]+a[x] 的方案数)
```
做的时候，可以枚举斐波那契第一项的起点在$$(x, 0)$$，然后**记忆化 dp**
```bash
dfs(x, S):
	for y in g[x], 如果 a[y] = S
		等价于求解以 (x, y) 作为起点，即前两项，最后两项和是 a[x]+a[y] 的方案数
		res += 方案数
```
> 算法实现

```bash
void solve() {
    using pint = pair<int, i64>;
    map<pint, mint> dpv;

auto dfs = [&](auto &dfs, int x, i64 sum) -> mint {
        if (dpv.contains(make_pair(x, sum))) {
            return dpv[ pint{x, sum} ];
        }

auto &res = dpv[ pint{x, sum} ];
        
        sum == 0 ? res = 0 : res = 1;
        for (auto y : g[x]) if (sum == 0 or a[y] == sum) {
            auto add = dfs(dfs, y, a[x] + a[y]);
            res += add;
        }

return res;
    };

mint ans = 0;
    for (int x = 1; x <= n; x++) ans += dfs(dfs, x, 0LL);
}
```
## 2020 ICPC 小米 网络选拔赛
### E
**[Phone Network](https://ac.nowcoder.com/acm/contest/7501/E)**
给定一个长度为`n`的序列`a`，每个点的权值范围都是$$1 \sim m$$，保证每个值都出现过
对每个$$1 \leqslant i \leqslant m$$，询问包含权值`[1, i]`（区间内所有数都要出现）
的区间的最小长度

**算法分析**
> 从暴力 dp 入手

一种直接的想法是，对每个$$x \in [1, m]$$，考虑怎么样使得$$[1, x]$$中每个数都出现？
枚举起始位置$$i \in [1, n]$$，只记录每个数**第一次出现的位置**`pos[x]`
令$$R = \max pos[1\cdots m]$$，然后用$$R - i + 1$$去更新答案即可
如果用`dp`方程表示的话，$$dp(i, x)$$表示以`i`为起点，`[1, x]`**都出现过**的最远右端点
有转移，$$dp(i, x) = \max(dp(i, x-1), lastx)$$

> 要关注的一点就是，从一个点$$i$$开始，满足$$[1, x]$$都出现，右端点**至少要到哪里**？

用`ri`表示对于位置`i`所求的至少的右端点的答案，考虑$$x$$出现的每一个位置
即$$pos[x] = \\{j1, j2, \cdots, jk\\}$$，$$pos_x$$对哪些`i`有贡献？

假设说当前考虑$$p\_j$$，考虑$$p\_{j-1}, p\_j$$
如果$$i \leqslant p\_{j-1}$$，$$p\_{j}$$这个位置的$$x$$**无贡献**，因为起作用的$$x$$在$$p\_{j-1}$$
那么此时**会影响到**的$$i \in [p\_{j-1}+1 \cdots p\_{j}]$$

如果我们从小到大`for`$$x \in [1, m]$$的话，对于起点$$i$$，那么我们应该**已经求出来了**
使得$$[1, x-1]$$都出现的**至少的右端点**`ri`，那么考虑$$p\_{j}$$的加入会如何影响$$i$$的答案（即`ri`）
其实很简单，如果$$ri(i) \geqslant p_j$$，无影响，有影响的话应该有$$ri(i) < p_j$$

那么，$$i \in [p\_{j-1}+1, p\_{j}]$$区间内有**若干**个$$i$$满足，以$$[i\_{?}\cdots ]$$为起点
并且$$[i\_{?} \cdots ri(i\_{?}) = p\_{j}]$$区间内，$$[1, x]$$**均出现**
我们应该选什么样的$$i$$呢？为了使得所求的区间长最小，应该选**最靠右的满足条件的**$$i$$
这个可以用线段树二分找到`max_right`的位置

> 算法设计，线段树

综上所述，我们可以`for`$$x = [1, m]$$每一个$$x$$
从小到大枚举$$x$$出现的每一个位置$$p_j$$

1.考虑区间$$i \in [p\_{j-1}+1, p\_{j}]$$，线段树二分找到满足$$ri(i) < p\_{j}$$的最右端的$$i$$
所在的位置记为$$K$$

2.对$$i \in [p\_{j-1}+1, K]$$的每一个位置，执行区间赋值$$ri(i) = p\_{j}$$
同时还需要更新一下，当前满足$$[1, x]$$都出现的最小长度
`mnlen( [p[j-1]+1, K] 所表示的区间，以及子区间  ) = p[j] - (所表示的区间的右端点) + 1`
（额外地，线段树同时维护一下点所表示的区间，对应的左右端点）

做完之后，根节点的`mnlen`就是答案，线段树维护`mnlen`的最小值
另外我们需要找到$$ri(i) < p_j$$的最靠右的$$i$$，线段树二分一般是考虑`exist or not`
所以还要维护`min( ri(i) )`

#### 算法实现
```bash
void solve() {
    vector<arr> leaf(n+1);
    for (int i = 1; i <= n; i++) {
        auto &[ri, mnlen, l, r] = leaf[i];
        l = r = i;

mnlen = inf<int>, ri = 0;
    }

lazy_segtree<arr, op, int, mapping, comp, id> tr(leaf, n);

vector<int> res(m+1, 0);
    for (int x = 1; x <= m; x++) {
        for (int j = 1; j < pos[x].size(); j++) {
            auto L = pos[x][j-1] + 1;
            auto pj = pos[x][j];

tar = pj;
            auto R = tr.maxRight<fl>(L, pj);

if (R == -1) continue;

tr.modify(L, R, pj);
        }
        if (pos[x].back()+1 <= n) tr.modify(pos[x].back()+1, n, inf<int>);

auto [_, mnlen, _l, _r] = tr.query(1, n);
        res[x] = mnlen;
    }
}
```
线段树定义
```bash
using arr = array<int, 4>;
// [ri, mnlen, l, r]

arr op(arr a, arr b) {
    arr res;
    res[2] = a[2], res[3] = b[3];

res[0] = min(a[0], b[0]);
    res[1] = min(a[1], b[1]);

return res;
}

using pint = pair<int, int>;

arr mapping(int pj, arr x) {
    auto res = x;

auto &[ri, mnlen, l, r] = res;
    ri = pj;
    mnlen = pj - r + 1;

return res;
}

int comp(int f, int g) {
    return f;
}

int id() {
    return -1;
}
```

## Educational Codeforces Round 165
### E
**[E. Unique Array](https://codeforces.com/problemset/problem/1969/E)**
给定一个长度是`n`的序列`a[1...n]`，定义一个子段（必须连续）是独特子段
当且仅当存在一个整数在这个子段中出现**恰好一次**
进行任意次操作，一次操作选择序列中的一个元素，并且用任意的整数去替换它
求最小的操作次数，使得`a`的每个子段都是独特子段

**算法分析**
假设说要改$$p$$这个位置，修改一定会把这个数改成从来没有出现过的数
你改了`p`，那么对于$$l \in [1, p-1], r \in [p+1, n], [l\cdots r]$$区间，及其子区间，就一定都是独特子段
这里好像有一种分治结构，只需要递归处理两侧即可
```bash
solve(1, n)
	solve(1, p-1) + solve(p+1, n)
```
但是如果暴力枚举`p`走下去，复杂度会退化到$$O(n^2)$$

> 考虑有没有什么性质

假设说考虑$$x$$出现的位置，$$p_1, p_2$$，那么$$p_1, p_2$$这两个位置，$$x$$要不要改呢？
其实**未必需要改**，区间$$[p_1, p_2]$$中，虽然$$x$$出现了`2`次
但是$$[p_1, p_2]$$中间，可能会有**只出现一次的数**，那么这个时候$$[p_1, p_2]$$就合法
不需要另外改

> 怎么判断合法与否，考虑每个数$$x$$，以及它出现的位置$$p_1, p_2, \cdots$$，对答案的贡献是怎么样的？

这可以用经典的**扫描线 + 事件**来维护实现

对于$$r = p_2$$（$$r$$可以枚举），实际上要看存不存在合法的`l`的位置

不难发现，对于$$l \in [p\_{i-1}+1, p\_{i}]$$来说，一定是合法的
因为$$x$$可以**被选为只出现 1 次的数**（称$$x$$有`1`的贡献）

而对于$$l \in [p\_{i-2}+1, p\_{i-1}]$$来说，$$x$$是不会有贡献的

> 扫描线事件

于是对于特定的$$x$$出现的位置，每**最后 2 个位置**切割成一段
考虑事件$$r = p_i$$，`evts[r]`

对于`[li, ri] = [p(i-1)+1, p(i)]`，都是有`1`的贡献，`evts[r].emplace_back(li, ri, 1)`

因为我们是依次考虑`x`出现的每个位置，上一段`[p(i-2)+1, p(i-1)]`之前有`+1`的贡献
现在随着`[li, ri]`新位置的加入，对于前一段来说，$$x$$不会再有贡献了
前一段`[lstl, lstr]`（当然段必须存在）的贡献`-1`，`evts[r].emplace_back(lstl, lstr, -1)`

最后做的时候，依次考虑每一个位置$$i$$，先把这个位置的事件全部都加上
查询`[pre+1, i]`的最小值，如果最小值是`0`，说明没有任何数能够贡献**特殊**
（特殊只出现一次）
那么就改$$a_i$$令`ans++`，改完之后，前缀及其子段都是合法的了，令`pre = i`，接着考虑下一段

## Helvetic Coding Contest 2024
### A2. Balanced Unshuffle (Medium)
**[A2. Balanced Unshuffle (Medium)](https://codeforces.com/problemset/problem/1970/A2)**
定义括号序列的平衡度是`(`的数量减去`)`的数量，定义前缀平衡度是`[0...i-1]`前缀括号序列的平衡度
对于每个位置`i`，先计算前缀`[0...i-1]`的前缀平衡度，然后标出他们的位置
接着按前缀平衡度升序排列，如果相同，按`position`降序排列，这个过程称为平衡洗牌
可以证明，合法括号序列的**平衡洗牌**，仍然是一个合法括号序列
并且任何两个不同的平衡括号序列的洗牌总是不同的

现在给定一个平衡括号序列，求它的原像`t`，使得`t`的平衡洗牌等于给定序列

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

## 牛客周赛 Round 122
### D
**[Digital Deletion](https://ac.nowcoder.com/acm/contest/125083/D)**
给定一个序列`a`，另外有一个数的集合$$S$$，将`a`所有子序列的和（不需要连续，包括空子序列）加入$$S$$
这个时候$$S$$有一个`mex`，现在问题是，你删除一些数之后，`S`的`mex`值还是不变
现在问，最多可以删除多少个数

**算法分析**
> 子序列和的`mex`，是可以**递推 + 动态维护的**

假设说，你求出来的`mex = R + 1`，意味着`[0....R]`中所有的数都出现
你加入一个数$$x$$，可能构成的**新出现的数是**`[x, x+1, ..., x+R]`
如果`x <= R + 1`，那么令`R = x+R`，继续
否则说明在`R+1`处断开了，成为了`gap`，`mex`值就是`gap`

## Helvetic Coding Contest 2024
### B2
**[B2. Exact Neighbours (Medium)](https://codeforces.com/problemset/problem/1970/B2)**
有`n`个点，但是不知道具体位置，需要你在`n * n`的网格上，构造具体位置
有一些限制，每个点给定一个`a[i]`，表示说存在**另外一个点**（或者说这个点可以去到另外一个点）
其中，另外一个点和这个点之间的**曼哈顿距离**恰好为`a[i]`
还有一个限制是，每一列最多只能有`1`个点

**算法分析**
medium 版本$$a_1 = 0$$，那么很显然，我们可以让`1`这个点**去往自身**
剩下的点呢？考虑尽可能往`a[1]`靠

不妨令$$a_1 = (1, 1)$$，其他的点**先和`1`放在同一行，然后再慢慢调整**
可以根据$$a$$从小到大排序，然后从左往右依次放

对于当前的第`i`个点，我们就钦定放在第`i`列第`1`行，$$(i, 1)$$，看情况调整
如果`i - 1 = a[i]`，那么让他去往第一个点即可
如果`i - 1 < a[i]`，`extra = a[i] - (i - 1)`，往下移动`extra`个单位，去往第一个点

如果`i - 1 > a[i]`，那么根据我们的放法，此时`[1...i-1]`列都是放满的
无非是他们可能放在不同的行，不一定都放在第一行
这个时候找到`j = i - a[i]`列，看一下这一列的点放在第几行，比如是第$$y$$行
那么去往第`j`个点，当前这个点放在同一行，当前点放置在$$(i, y)$$

> 考虑 Hard 版本

![](/media/content_img/helveticB.png)

### C2
**[C2. Game on Tree (Medium)](https://codeforces.com/problemset/problem/1970/C2)**
罗恩和赫敏在一个`n`个结点的树上玩游戏，medium 版本只有玩一轮
每一轮进行如下，一开始给定一个`u`，表示`u`点放有石子，并且这个节点已经激活
每一步操作，把石头移动到相邻的，**未激活**的节点上，Ron 先手，两人轮流操作
无法操作的一方输掉游戏，假设每个人都采用最优策略

**算法分析**
Medium 版本比较简单，还是比较容易想到的
考虑一条链什么时候是先手必胜的，不难发现 A 先手必胜状态和 B 先手必胜状态相邻交替
以最开始石头放置的位置$$u$$为根进行`dfs`，`dp(x) |= (dp[y] ^ 1)`

Hard 版本呢？多个询问，很自然地想到**换根**
首先，考虑每个点`y`，如果`dp(y) = true`，那么先手的`Ron`一定可以`win`
否则，只能往`y 的父亲 x`走，就要考虑`(y 的兄弟 or fa(x) 的先手必胜状态)`了

和换根`dp`类似，用`up(y)`表示，当前先手的人在`y`处，并且下一步只能往`y`的**子树之外走**
它的先手必胜/必败状态

**在博弈论中换根比较特殊**，考虑树边$$(x, y)$$
`up(y) 先手必败`当且仅当**存在一条（只要一条就够了）路径，使得**$$x$$先手必胜

1）如果`up(x) = true`，那么`up(y) = false`
2）如果`y`的兄弟`yi`中，存在一个点`dp(yi) = false`，那么`up(y) = false`
（这种情形，`Bob`只要通过`x`走到这个先手必败的`yi`点，`Alice`就输了）

其他情况，`up(y) = true`

上一篇：十二月算法竞赛选题（一）下一篇：十二月算法竞赛选题（三）

看完文章有啥想法