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

[[ 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]`（区间内所有数都要出现）
的区间的最小长度

**算法分析**
### ODT 视角
> 假设说没有修改操作，怎么做？

对于值$$x$$，可以预处理出$$[1\cdots x]$$都出现的最小右端点，记为`need[x]`
考虑每一个数第一次出现的位置`fpos(x)`，那么我们有
```math
\displaystyle
\text{need}(x) = [1\cdots x]\text{都出现最小右端点} = \max_{i = 1}^{x} (\text{fpos}(i))
```
对`need`分析一下性质，不难发现
1）`need`单调不降
2）如果使得$$[1\cdots x]$$都出现的最右**“挡板”**是$$R$$
很有可能$$[1\cdots x \cdots y]$$都出现的**最右挡板**也是$$R$$
换句话说，$$[x, y]$$区间的右端点都是$$R$$，然后再跳跃，然后再保持同一个值
这样的结构，可以用 **ODT（珂朵莉树）**来维护

> 上面的做法，已经处理好了$$l = 1$$时候，$$x \in [1, m]$$每个数都出现需要的最右端点`r = need[x]`
接下来只要考虑$$l \to l+1$$，上述的值会怎么变化，对应地去维护

记$$x = a_l$$，考虑推动$$l \to l + 1$$，下一个$$x$$出现的位置是`npos = nxt[l]`（可以预处理）
那么对于$$\geqslant x$$的一些数，它的`need`值会变化
```math
\displaystyle
\text{need}(\geqslant x\text{的一些数}) = \max(\text{need}(\geqslant x), \text{npos})
```
实际上，会变化的，就是珂朵莉树`split(x)`出来区间$$[x\cdots )$$对应的**前缀子区间**
它们的`need`值会变化，`need < npos`的会被**`npos`推平！**

另外再看上面的公式，因为$$\text{need}$$是**单调不降的**，实际上，只要分裂出$$[x \cdots )$$
然后依次对应珂朵莉树区间$$(li, ri, P = \text{need 值})$$，满足$$P < npos$$的
将它们**推平**，赋值`npos`即可

如果我们能够找到这样需要推平的区间，说明此时$$[l, P]$$就是能够允许的最左的`l`了
再往右推$$l$$，对应的右端点就不是$$P$$了（而是$$npos$$）
那么这个时候珂朵莉树上**被推平的区间**$$[li, ri]$$所需要的区间长度**即将变成**$$npos - l + 1$$
同时也意味着，我们可以$$l$$是当前$$P$$对应的最右左端点
对于$$x \in [li, ri]$$，使得$$[1\sim x]$$都出现的最短区间长度，可以用$$P - l + 1$$来更新
用线段树的区间修改即可维护

#### 算法实现
```bash
struct Tag {
    // 默认值表示 id()
    int cand = inf<int>;

// 与另一个标记合并，相当于 f(Tag)
    // 变换顺序 Tag -> f
    void apply(const Tag &f) {
        chmin(cand, f.cand);
    }
};

// Info 代表节点维护的信息
struct Info {
    int val = inf<int>;

// 将 tag 作用于自身，f(info)
    void apply(const Tag &f) {
        chmin(this->val, f.cand);
    }
};

// 左右儿子的合并
Info operator+ (const Info &a, const Info &b) {
    Info res;
	// 其实这里无所谓，反正最后答案我们要深入叶子节点
    res.val = min(a.val, b.val);
    return res;
}

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

vector<int> a(n+1, 0);
    for (auto &x : a | views::drop(1)) cin >> x;

vector<int> fpos(m+5, n+1);
    vector<int> nxt(n+1, n+1);

for (int i = n; i >= 1; i--) {
        auto x = a[i];
        nxt[i] = fpos[x];
        fpos[x] = i;
    }

vector<int> need(m+5, 0);
    for (int x = 1; x <= m; x++) {
        need[x] = max(need[x-1], fpos[x]);
    }
    // debug(need);

int l = 1, lastv = need[1];
    for (int x = 1; x <= m; x++) {
        if (need[x] != lastv) {
            auto r = x - 1;
            odt.insert(Node{l, r, lastv});

lastv = need[x], l = x;
        }
    }
    odt.insert(Node{l, m, lastv});

// debug(odt);
    LazySegtree<Info, Tag> tr(m);
    for (auto [l, r, P] : odt) {
        // [1..P]
        tr.modify(l, r, Tag{(int)P});
    }

for (int l = 1; l <= n; l++) {
        auto x = a[l];
        auto itx = Split(x);

int npos = nxt[l];

vector< set<Node>::iterator > del;
        int nl = n, nr = 0;

for (auto it = itx; it != odt.end(); it++) {
            auto [li, ri, P] = *it;
            if (P >= npos) break;

chmin(nl, li), chmax(nr, ri);
            // [l, P]
            tr.modify(li, ri, Tag{(int)P - l + 1});
            del.emplace_back(it);
        }
        for (auto it : del) odt.erase(it);

if (nl <= nr) odt.insert(Node{nl, nr, npos});
    }

for (int x = 1; x <= m; x++) {
        auto res = tr.rangeQuery(x, x).val;
        cout << res << " ";
    }
    cout << "\n";
}
```

## 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`

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

看完文章有啥想法