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

[[ slider_text ]]

[[ item.c ]]

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

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

dp 集合划分

## Codeforces Round 955
### D
**[D. Beauty of the mountains](https://codeforces.com/contest/1982/problem/D)**
给定两个`n * m`的矩阵，第一个矩阵表示山脉，第二个矩阵是`01`矩阵，表示山脉类型
现在可以对任意$$k \times k$$子矩阵进行操作（`k`给定），把区间内所有山的高度`+= c`
注意，`c`可以是负数，现在问能不能使得两类山的高度之和相等（高度之和变成负数也没关系）
输出`yes or no`

**算法分析**
不妨设最开始两种类型的山脉的和分别是$$A, B$$，枚举子矩阵起始位置$$(i, j)$$，因为子矩阵的边长是确定的
这样子矩阵也就随之确定

只需要关注子矩阵内有多少个`0, 1`，比如第一个子矩阵有$$x_1$$个`0`，$$y_1$$个`1`
```math
\displaystyle
A + c_1x_1 + c_2x_2 + \cdots + c_kx_k = B + c_1y_1 + c_2y_2 + \cdots + c_ky_k \\
(x_1-y_1)c_1 + (x_2-y_2)c_2 +\cdots + (x_k - y_k)c_k = B - A
```
不定方程整数解的判定，可以用裴蜀定理，需要$$\text{gcd}(\cdots) \mid (B - A)$$即可

## Codeforces Round 956
### D
**[D.Swap Dilemma](https://codeforces.com/contest/1983/problem/D)**
给定两个序列`a, b`，问能否将他们变得完全相同，每次操作，在`a`中任选两个位置`l, r`
交换$$a_l, a_r$$，同时`b`中任选两个下标`p, q`，满足$$r-l = q-p$$，交换`b[p], b[q]`
可以的话输出 YES，否则输出 NO，其中保证 a, b 各自数组中所有数都不同

**算法分析**
首先，如果有数在`a`中出现，但是在`b`中没出现，肯定不行

考虑$$(a_x, a_y), (b_p, b_q)$$，要想完成交换，**相邻冒泡肯定不劣**
即`a[x], a[x+1] 交换，b[p], b[p+1] 交换`，这样不仅能够达成目标，还能够不影响其他位置的相对顺序

这样，最后的结果，就跟两个序列的逆序对有关

> 如果两个序列的逆序对奇偶性相同，那么一定可以，否则不行

如果两个序列的逆序对相等，那么一定可以，冒泡排序就可以了
否则呢？一定有$$d = |inv(a) - inv(b)|$$，不妨设逆序对数量较小的序列是`a`，`a`先完成排序
那么多出来的`d`个怎么办呢？这`d`个需要靠`a`来**消耗掉**，方法是取长度为`len`的两个有序位置
`swap(a1, a2)`，然后再`swap(a1, a2)`**换回来**，也就是`d`必须是偶数

## Codeforces Global Round 26
### C1
**[C1. Magnitude (Easy Version)](https://codeforces.com/contest/1984/problem/C1)**
给定一个长度为`n`的序列`a`，一开始`c = 0`，对每个`i`有两种决策
```bash
决策1:   c = c + a[i]
决策2:   c = |c + a[i]|
```
问最后操作完能得到的最大值是多少

**算法分析**
简单 dp，因为有负数存在，用`dpmx, dpmn`表示到当前位置，能够得到的最大，最小值
```math
\displaystyle
dpmx(i) = \max(\quad |dpmn(i-1) + x| \quad) \\
dpmx(i) = \max(dpmx(i-1) + x) \\
dpmn(i) = \min(dpmn(i-1) + x) \\
dpmn(i) = \min(dpmx(i-1) + x)
```

### C2
**[C2 Magnitude (Hard Version)](https://codeforces.com/problemset/problem/1984/C2)**
题目描述同上，求出操作后的最大值`K`，问有多少种本质不同的方案，使得最后的$$c = K$$
只要存在一个`i`，使得这个位置用的操作不同，就被视为不同的方案

**算法分析**
在 dp 转移的时候，对于一个位置分为`dpmx[i], dpmn[i]`，方案数记为`waymx[i], waymn[i]`
同样需要开`waymn, waymx`记录一下最大最小值方案，只不过转移的时候，注意`dpmx[i-1], dpmn[i-1]`相等的情况
```math
\displaystyle
dpmx_i = \max \{ |dpmn_{i-1}+x|, \ dpmn_{i-1} + x, \ dpmx_{i-1} + x, \ |dpmx_{i-1} + x| \} \\
dpmn_i = \min \{ dpmn_{i-1}+x, \ |dpmn_{i-1} + x|, \ dpmx_{i-1}+x, \ |dpmx_{i-1} + x| \}
```
对应地，对于**`dpmx[i]`**，考虑四种情况的转移
如果存在`dpmx[i-1] == dpmn[i-1]`，把结果`/ 2`即可
```bash
if (dpmx[i] == llabs(dpmn[i-1] + x)) waymx[i] += waymn[i-1];
if (dpmx[i] == dpmn[i-1] + x) waymx[i] += waymn[i-1];
if (dpmx[i] == llabs(dpmx[i-1] + x)) waymx[i] += waymx[i-1];
if (dpmx[i] == dpmx[i-1] + x) waymx[i] += waymx[i-1];

if (dpmx[i-1] == dpmn[i-1]) waymx[i] /= 2;
```
**对于`dpmn[i]`**也是类似的

## Codeforces Round 955
### E
**[E. Number of k-good subarrays](https://codeforces.com/contest/1982/problem/E)**
**问题描述**
用`bit(x)`表示`x`的二进制表示中`1`的个数
一个数组的子数组`[l...r]`被称为`k-好`的，当且仅当**所有的**$$l \leqslant i \leqslant r$$
都满足`bit(a[i]) <= k`
给定一个长度为`n`，元素从`0`开始的序列`a`，元素是连续的，即`a[i] = i`
其中$$i \in [0, n)$$，计算序列`a`的`k-好`子数组的数量，其中$$1 \leqslant n \leqslant 10^{18}$$
而$$1 \leqslant k \leqslant 60$$

**算法分析**

> 首先有一种比较明显的分治结构，`solve(L, R)`

考虑区间`[L, R]`中有多少个符合条件的二元组`(l, r)`（即子区间），对区间归并
令`[L, R] = [L, mid] + [mid+1, R]`，那么符合条件的区间
要么完全落在`[L, mid]`中，要么完全落在`[mid+1, R]`中，这都可以递归分治分别求解

难的是**横跨左右两半**，即`l`落在左半段`lhs`中，`r`落在右半段`rhs`中，怎么办呢？
那么此时要求`lhs 左半段，[.....l... (后缀全部都要是合法的) mid]`，需要记一下左边的最长的合法后缀
同时记录一下`rhs 右半段，[mid+1, (前缀全部都要合法的)...r....]`，记一下右边的最长合法前缀
于是类似线段树的合并，每个区间维护`最长合法前缀 pre, 最长合法后缀 suf，满足条件的答案`

最后答案的贡献就是
```bash
solve(l, mid) -> Info lhs
solve(mid+1, r) -> Info rhs

return lhs.ans + rhs.ans + (lhs.suf) * (rhs.pre)
// l 的选择有 lhs.suf 种，r 的选择有 rhs.pre 种
```

> 那么可以设计算法，`solve(l, mid, k) + solve(mid+1, r, k)`

表示`[l, r]`中满足**子区间内所有数的 popcnt <= k**的子区间数量
这样做的复杂度是$$O(n \log n \cdot k)$$，因为$$n \leqslant 10^{18}$$，无法接受

> 考虑优化，从$$n$$的二进制位入手，如果形如$$n = 2^i$$怎么做？
假设说$$n$$**最高为`1`的位是**$$m$$

如果用`+`表示** Info 的合并**，那么可以有如下的分治策略
```math
\displaystyle
[0, 2^m) + [2^m, n)
```
这样我们可以用$$dp(l, r, k)$$来求解，$$dp(0, 2^m, k) + dp(2^m, n, k)$$就是答案
但这样做的复杂度是$$O(n\log n \cdot k)$$的
**注意到**，$$dp(2^m, n, k)$$，在$$[2^m, n)$$区间内的数，第`m`位一定是`1`
而题中求的是方案数，所以等价于$$[0, n-2^m)$$内`1`的个数$$\leqslant k-1$$
从而可以写成，$$dp(0, 2^m, k) + dp(0, n - 2^m, k-1)$$

这样分析下去，最后的答案，可以看成$$n = \sum 2^i$$，若干个形如$$dp(0, 2^i, k')$$的值的合并

这样，我们可以记$$f(i, k) = dp(0, 2^i, k)$$，由之前的分析，我们可以知道
```math
\displaystyle
f(i, k) = dp(0, 2^i, k) = dp(0, 2^{i-1}, k) + dp(0, 2^{i-1}, k-1) \\
f(i, k) = f(i-1, k) + f(i-1, k-1)
```
上面这部分可以预处理完成，这样关于$$n$$的计算就可以
```bash
Info ans;

auto k = K;
for i = LOG downto 0:
	if n >> i & 1:
		ans += f(i, k), then k -= 1
```

#### 算法实现
```bash
void solve(int cas) {
    i64 n;
    int K;
    cin >> n >> K;

vector dp(LOG+5, vector<Info>(LOG+5, Info{}));

for (int i = 0; i <= LOG; i++) {
        dp[0][i] = Info{1, 1, 1, 1};
    }

auto calc = [&](int i, int j) -> Info {
        if (j >= 0) return dp[i][j];
        return Info{1LL << i, 0, 0, 0};
    };

for (int i = 1; i <= LOG; i++) {
        for (int j = 0; j <= LOG; j++) {
            dp[i][j] = calc(i-1, j) + calc(i-1, j-1);
        }
    }

int k = K;
    Info ans = Info{};
    for (int i = LOG; i >= 0; i--) {
        if (! (n >> i & 1) ) continue;

ans = ans + calc(i, k);
        k -= 1;
    }

cout << ans.ans << "\n";
}
```
> 特别说明

可能会遇到$$dp(i, j) = dp(i-1, j) + dp(i-1, j-1)$$，$$j - 1 < 0$$的情况
此时意味着，划分成两部分，剩下的**右半部分**，**全都是 0**，所以`calc`要处理这种情况
```bash
auto calc = [&](int i, int j) -> Info {
	if (j >= 0) return dp[i][j];
	return Info {1LL << i, 0, 0, 0}

// 长度为 1LL << i 的区间，所有的位都是 0
};
```
## Codeforces Round 1064 (Div. 2)
### D
**[D. Marble Council](https://codeforces.com/contest/2166/problem/D)**
给你一个多重集合`a`，有元素`a[1...n]`，你需要生成一个新的集合$$S$$
你先把$$a$$划分成若干个不相交的多重集$$x_1, x_2, \cdots, x_k$$
一开始$$S$$是一个空集，然后对于$$x_i$$，你把$$x_i$$中的众数加入到$$S$$中
如果有多个数出现次数相同且等于众数的出现次数，你只需要任选一个加入即可
问能得到多少不同的$$S$$

**算法分析**
> 简单一点，如果每个数都可以允许出现在$$S$$中，怎么做？

不妨设$$5$$**在原序列`a`中**出现的次数是`4`次，实际上，$$S$$中，`5`可以出现$$1\sim 4$$次
```bash
{5, 5, 5, 5} --> {5}
{5, 5, 5} {5} --> {5, 5}
{5, 5} {5} {5} --> {5, 5, 5}
{5} {5} {5} {5} --> {5, 5, 5, 5}
```
只需要给每个数单独开一个集合，然后这个数$$x$$就可以在$$S$$中出现$$1 \sim cnt_x$$次

> 下面考虑隐藏某些数，这个是有一些限制的？什么情况下一个数可以被隐藏？

你要想不出现，就需要用**众数来隐藏**
![](/media/content_img/cf1064d.png)

如果一个数$$x$$被选为众数（也就是说它**最终会出现**在$$S$$中）
就意味着它可以贡献$$sz = cnt_x$$的容量，用来**隐藏其他的数**
这就可以类似`01`背包
```math
\displaystyle
\sum_{t \in T} cnt(t) \to sz
```
看作背包的容量，如果一个数被选为众数，那么背包的容量`sz`增加，否则`sz`不变
可以用$$dp(i, sz)$$，看作背包容量，要求$$sz \geqslant \max cnt(no)$$

> 01-背包

考虑每个数是否出现，如果出现在$$S$$中，它可以出现$$1\sim cnt_x$$次
枚举上一个位置的`sz`
那么$$ndp(sz + cnt_x) \leftarrow dp(sz) \cdot cnt_x$$

若不出现，对`sz`没有贡献，$$ndp(sz) \leftarrow dp(sz)$$

最后并不是所有的`sz`都能作为答案，有限制，因为所有数都不会增加，也不会减少
所以能够用于**隐藏其他数的**`sz`，至少是$$\max cnt(a_i)$$个

否则就必然有一个数$$cnt > sz$$，这个数是无法隐藏的，必须出现在$$S$$中
导致`sz`变大

> 说明

实际上，这里的$$dp(sz)$$表示的是，在最终集合$$S$$中，提供$$sz$$个隐藏位置的方案数

出现的数$$t \in S$$，$$sz = \sum cnt_t$$
这里的`cnt`是对于**最初的序列`a`而言的**，表示说它能贡献这么多**可供藏起来的位置**

如果`sz < maxcnt`，那么必然那个出现次数$$= maxcnt$$的数`mode`
会有最少$$\geqslant 1$$的这个数，无法被隐藏，出现在$$S$$中

> 疑问，这样算会不会漏解

答案是不会
```bash
考虑 {1, 1, 1} and {2, 2} 的情况
如果我们计算 {1} + {1} + {1, 2} + {2} 的贡献

case1:
S = {1, 1, 1, 2}
这样的方案数，在 {1} + {1} + {1} + {2, 2} 中被考虑过了

case2:
S = {1, 1, 2, 2}
这样的方案数，在 {1} + {1, 1} + {2} + {2} 中被考虑过了

所以实际上计算隐藏位置的方案数，只需要将每个数单独划分一个集合来考虑
考虑是否隐藏即可
```

上一篇：十一月算法竞赛选题（一）已经是最后一篇啦

看完文章有啥想法