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

[[ slider_text ]]

[[ item.c ]]

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

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

差分 字符串 Z函数

## Codeforces Round 956
### E
**[E. I Love Balls](https://codeforces.com/problemset/problem/1983/E)**
Alice 和 Bob 在玩球，有`n`个球，其中有`k`个特殊球，每个球有权值
Alice 先手，一个回合随机选一个球，并且将权值加到自己的得分上，初始得分都是`0`
被选中的球会被删除，如果能选中特殊球，并且游戏中还剩至少一个球，那么该玩家继续
否则轮到对方操作，问 Alice 和 Bob 的期望得分

**算法分析**
> 不难发现，两个人的期望得分，一定是所有球的权值之和，现在只考虑 Alice
先假设说没有特殊球

这个怎么算呢？考虑**每个球是否对 Alice 有贡献**
注意到，对于当前的球，只有把它放在奇数位上，它才会对 Alice 有贡献，球和球之间是独立的
并且概率都是相等的，一共有$$n - k$$个特殊球，有$$\lceil \dfrac{n-k}{2} \rceil$$ 个奇数位置
所以对于每个球，都是**等概率的**，$$p = \lceil \dfrac{n-k}{2} \rceil / (n - k)$$

那么答案就是$$\sum p \cdot a_i = p (\sum a_i)$$

> 那么特殊球呢？

考虑特殊球什么时候有贡献，用**插板法**，考虑将特殊球插入普通球的空位中
Alice 拿到特殊球，**意味着他一定能拿到紧随其后的普通球**，也就是说
能被 Alice 拿到的特殊球，一定在**能被 Alice 拿到（奇数位置）的普通球**前面的空位中

一共有$$(n - k + 1)$$个空位（包括最后一个空位，特殊球后面不接任何普通球也是可以的）
能被 Alice 拿到的**空位编号**，也必须是**奇数**

每个特殊球仍然是等概的，$$p_s = \lceil \dfrac{n-k+1}{2} \rceil / (n - k + 1)$$
答案是$$p_s \cdot sum_s$$，其中$$sum_s$$表示特殊球的权值之和

## 2025 ICPC 武汉
### H
**[H. Restore the Array](https://qoj.ac/contest/2609/problem/14726?v=1)**
交互题，给你一个长度为`n`的序列，数是两两不同的，但是不知道每个数具体的值是多少
可以询问最多`2n - 2`次，每次询问`? c`，`c`你自己选
交互器会返回一个值`res`，值是$$\max(a_i \oplus c)$$，要你还原数组`a`

**算法分析**
之前用**位分治**来解决过这个问题
但是给定一个数`c`，查询已有集合中，$$\oplus c$$最大的数，有经典做法，就是`01-trie`

> 用 01 字典树来解决这个问题

首先`ask(0)`可以得到`max`，再`ask(max)`又可以得到一个数
将它们插入字典树，不难发现
**具有公共前缀 + 分岔点**

> 考虑最高位分叉点（从高位往低位第一个分岔点），一边往`0`走，一边往`1`走

假设说我们还原出了数$$x，y$$，分叉点所在的位是$$p$$，$$x_p = 0, y_p = 1$$
现在就考虑$$x$$，**注意到**
```bash
1) 从最高位到 p 位
ask:  [111...1] [00...0] xor x = ( [topbit....p 位] 和 x 的高 p 位一样的数 )
ask(x ^ ( ~0U << p ))

这样一定能问出一个前缀 [top...p] 和 x 一样的数

2) 接下来就看后缀，[p+1...0] 位，假设存在一个数和 x 的前缀一样，但不知道，记为 ?
就取低位后缀看

[00...0] xor x = (x 的后缀)
[00...0] xor ? = 问出来的数 = (单单看后缀几位的最大值)
```
换句话说，每一个分叉点，我们都可以问出**前缀和 x 相同，后缀**就看**截断**`[p+1...0]`这几位能够得到的最大值
当然问出的最大值可能和$$x$$相同，那也就意味着再往下都不会有分叉点了

否则问出的数一定$$\neq x$$，并且$$> x$$，构成前缀和$$x$$相同的数的**上界**
随着分叉点的下移，这个上界不断减小，直到$$x$$

问出来一个数就插入 01-trie 中，对$$y$$也是如此

> 具体看算法实现

从高位往低位找分叉点，比如第$$bit$$位是$$c$$，trie 树指针用`p`表示
如果`tr(p, c) = nullptr`，就动态开点，同时若发现`tr(p, !c) != nullptr`，说明`bit`就是分叉发生的位
这时候，对于$$x$$，要查询`x xor (~0U << bit)`
对于$$y$$，要查询`y xor (~0U << bit)`

为了方便获取`x, y`具体值到底是多少，每一次动态开点的时候，就标记一下这个点对应的具体值是多少

后续每插入一个新的数，都会导致分叉点下移

> 因为我们已经把最大的数找出来了，而我们再一次`ask(max)`，那么$$(\oplus \max)$$最大的数
必然是**和`max 0-1`分叉在最高位的数**
沿着某个分支下去，我们再询问的数，依然是前缀和`x`都一样，**后缀截断`[00...0]`**这`bit`位中
和`x 截断低 bit 位`**分叉相对也在最高位的数**
这样做下去，就导致分叉点一定从高位到低位不断下移的

可以用一个队列来存下需要`ask`的数，每`ask(x)`，就`insert(x ^ ask)`
在`trie`和答案数组中同步插入

`trie`中每插入一个新的数，就寻找新的分叉点，并且询问新的`x, y`对应的分叉位
往下还有没有数没有找到，把对应的`ask`的数再放入队列中，直至队列为空

#### 算法实现
**Trie 树部分**
```bash
namespace Trie {
    const int N = 1e5 + 5;
    const int MASK = (1U << 30) - 1;
    int LOG = 30;
    int trie[N * 32][2];
    
	// 需要维护的，树中的分叉点，具体对应的值
	// 以及当前可能会新加入的，需要询问的一些数 cand
    i64 val[N * 32];
    queue<int> cand;

void insert(i64 x, int t = 1) {
        int p = root;
        sz[p] += t;
        for (int i = LOG; i >= 0; i--) {
            int u = x >> i & 1;
            if (!trie[p][u]) {
                trie[p][u] = newNode();
                val[ trie[p][u] ] = x;

if (trie[p][!u]) {
                    int x = val[ trie[p][u] ], y = val[ trie[p][!u] ];
                    int askx = (MASK & (x ^ (~0U << i)));
                    int asky = (MASK & (y ^ (~0U << i)));
                    
                    cand.push(askx), cand.push(asky);
                }
            }
            p = trie[p][u];
            sz[p] += t;
        }
    }
};
```
**solution 部分**
```bash
void solve(int cas) {
    int n;
    cin >> n;

using namespace Trie;
    set<int> res;
	
    auto mx = ask(0);
    insert(mx), res.insert(mx);

cand.push(mx);

while (cand.size() && res.size() < n) {
        auto x = cand.front();
        cand.pop();

auto xmax = ask(x);
        // debug(getmx(x));
        auto exist = xmax ^ x;

insert(exist), res.insert(exist);
    }

out(res);
}
```
**Trie 树技巧**
分叉点会变化的时候，需要动态开点
在动态开点的时候，可以打标记，标记这个点对应的原来的值是多少
方便做后续的处理

## Codeforces Global Round 26
### D
**[D. "a" String Problem](https://codeforces.com/contest/1984/problem/D)**
给定一个由小写字符组成的字符串$$s$$，请问有多少个非空字符串`t != "a"`，使得可以将$$s$$分成若干子串
满足，每个子串要么是`t`要么是`"a"`，至少要有一个子串等于`t`
划分的意思是$$s = t_1 + t_2 + \cdots + t_k$$

**算法分析**
> 咋一看好像和周期有关

和周期有关的问题，想到两个方面，`border`以及`Z 函数`
1)`周期 + border = n`（这里周期和 border 都是指长度）

2) Z 函数
2.1 字符串下标假设说从`0`开始，`[0...i-1]`构成一个最小整周期
那么有$$i + Z(i) = n$$

2.2 本质不同的子串，可以增量构造，`S`每次加入一个字符`c`
令`t = reverse(S + c)`，对`t`求前缀函数
那么加入这个字符`c`，对本质不同子串的贡献是` += |t| - Zmax`
其中`Zmax`表示`t 中所有位置 i`，对应的$$\max Z(i)$$

> 这里用前缀函数（Z 函数）来求解，满足条件的划分应该是什么样的？

找到所有非`a`的字符，处理出它们第一次出现的位置，用`l, r`分别表示位置的最小值，最大值
那么$$t$$至少应该是`s[l, r]`这么长，当然可能会更长

划分模式是`(若干 a) + t + (若干 a) + t + .... + t + (若干 a)`

假设说最小的划分单位是$$t$$，考虑可能有如下符合的情况
1) `t`后面不接`a`，只会在`t`前面接上若干`a`
2) `t`后面接上若干`a`，同时也会在`t`前面接上若干`a`

**情形一**
如果`t`后面不接`a`，只可能在`t`前面接上若干`a`，构成一个合法的新的`t`
注意到`t + (若干 a) + t`，预处理出从某个下标`i`开始，最多有连续的几个`a`
那么`t`前面最多能接多少个`a`呢？假设说是`can`个

对于特定的`t`，考虑`t`与`t`之间间隔的`a`
`can = min(间隔的 a 的个数，包括 S 中最开始的前缀 a)`，那么对答案的贡献是`can + 1`
`+1`是因为可以不加任何`a`，如果要加`a`就可以在前面加`[1...can]`个

**情形二**
如果是`t`后面接着`a`呢？形如`[a...a] + t + [a...a]`，实际上
令`t = t + [a...a]`作为新的`t`，枚举`t`的长度这很容易，在新的`t`中考虑，前面最多能加几个`a`

> 把模式算出来之后，就考虑判断合不合法

什么时候合法呢？注意$$S$$要处理一下，去除前导`a`，求出前缀函数
枚举$$t$$（实际上是一个前缀），从小到大枚举前缀，考虑每一个$$t$$的段（中间有连续的`a`就跳过）
开始的位置假设是$$j$$，当且仅当对每一个段的开始，$$Z(j) = |t|$$时，合法

> 技巧，怎么算从一个位置开始，有多少个连续的`a`，用`ext(i)`表示`i`能往前延伸的最大长度

从后往前`for`
```bash
for i = n downto 1
	ext[i] = (str[i] == 'a' ? ext[i+1] + 1 : 0)
```

### E
**[E. Shuffle](https://codeforces.com/contest/1984/problem/E)**
给定一个`n`个节点的树`T`，对整棵树进行恰好一次的洗牌操作，利用原来的树节点
构造一棵新的树$$T_2$$，有`3`个步骤
1.从原树中任意选择一个节点$$V$$，以$$V$$为根，创建一棵新树$$T_2$$
2.将$$V$$从`T`中移除，原树形成若干个子树
3.对每个子树都重复如上操作，并且洗牌后的子树的根节点，再连回$$V$$中，完成新树的构建
（注意，子树的这样操作是不断进行的，叶子结点是度数为 1 的点，如果根节点只有一个儿子，那么根节点也是叶子结点）

问能获得的最大叶子结点数是多少？

**算法分析**
将操作**分成若干层**，每一次操作，对应每一层取出一个根，然后在**下一层**递归处理剩下的子树

> 初步观察，能够发现

![](/media/content_img/global26-E1.png)

> 考虑几种特殊情况，以及递归求解

![](/media/content_img/global26-E2.png)

> 发现类似最大独立集问题

![](/media/content_img/global26-E3.png)
![](/media/content_img/global26-E4.png)

不难发现，符合条件的叶子树，是一个**强化版的最大独立集**，满足
1）最多只允许有一个点和它的父亲同时被选，作为第一层的`root`和`子树的叶子`
2）除此之外，任意一条边上的两个点，**不能同时被选为叶子**
在这种情况下的树的独立集大小

那这个怎么做呢？因为只会有一个点和它的父亲，即$$(u, pa_u)$$可能同时被选为叶子
那么我们可以枚举这个点，树上的枚举，考虑**换根 dp**

我们先正常跑一遍树的最大独立集，得到`dp 数组`
换根 dp 考虑三个东西，`u 往上 (不包括 u) 的补集的最大独立集 up(u)`，`u 及其子树的最大独立集 dp(u)`
以及枚举$$(u, v)$$时候，`rem = (u 及其子树扣除 v 这个分支之后，还剩下的部分)`
根据这三部分去转移

特别注意，对于$$x$$，`up(fa) + rem1 + dp(x, 0)`此时算的是`x`不被选为叶子（也就是说被选为子树的根）的最优解
如果`deg(x) == 1`，还要`+1`，因为题目中要求`deg = 1`的根节点也要计算进去
`res = ( up(fa) + rem1 + dp(x, 0) ) + [deg(x) == 1]`，`chmax(ans, res)`即可

#### 算法实现
```bash
up(x, 0/1)
表示 x 往根方向的补集（不包括 x），父亲 fa 会不会被选（注意是父亲，而不是自己）

dfs(x, fa)，考虑 fa 被选的状态，维护 x 子树的补集
1）要在 dp(fa) 对应的状态中，扣除 x 相关分支的信息
2）考虑根据 fa 是否被选，维护补集大小 rest0, rest1
auto rest0 = rem0 + max(up(fa, 0), up(fa, 1))
auto rest1 = rem1 + up(fa, 0)

chmax(ans,   dp(x, 0) + (g[x].size() == 1) + max(rest0, rest1)  )
chmax(ans,   dp(x, 1) + rest0)
```
具体实现换根的第二遍 dfs 如下
```bash
void solve {
    auto dfs2 = [&](auto &dfs2, int x, int fa) -> void {
		// 扣除 x 这个分支对应的状态
        auto rem0 = dp[fa][0] - max(dp[x][0], dp[x][1]);
        auto rem1 = dp[fa][1] - dp[x][0];

// fa status 0/1
        auto rest0 = rem0 + max(up[fa][0], up[fa][1]);
        auto rest1 = rem1 + up[fa][0];

chmax(ans, dp[x][0] + max(rest0, rest1) + (g[x].size() == 1));
        chmax(ans, dp[x][1] + rest0);

up[x][0] = max(up[fa][0], up[fa][1]) + rem0;
        up[x][1] = up[fa][0] + rem1;

for (auto y : g[x]) {
            if (y == fa) continue;
            dfs2(dfs2, y, x);
        }
    };

for (auto x : g[1]) {
        dfs2(dfs2, x, 1);
    }
}
```

## Codeforces Round 952
### H2
**[H2. Maximize the Largest Component (Hard Version)](https://codeforces.com/problemset/problem/1985/H2)**
给定一个$$n \times m$$的网格，每个网格中的数，是`.` or `#`，上下左右`4`个方向，相邻的格子是可达的
对于`#`单元格，如果能够移动到其他`#`单元格，称它们是连通的，所有可达的`#`就构成一个连通分量
现在一次操作，可以选择任意行或者任意列，然后将选取的行或者列，每个单元格都设置成`#`
问`#`所有连通分量中，最大的是多少

困难版，是要求同时选择$$(r, c)$$，将$$r$$行和$$c$$列同时都改成`#`

**算法分析**
> 简单版怎么做？

简单版并不难做，先对所有连通的`#`用并查集处理一下
然后枚举修改的列（行也是对称地，再做一次）
1）`add = 修改的列 . 的个数`
2）操作完成之后（假设操作的是`y`列）,`y-1 and y+1`所有的`#`连通快都会彼此连通（通过`y`）
只要用`set`记录一下`y-1 and y+1`列`#`所在的连通快的编号（即所在的并查集的根）
答案就是`sum(所有相邻列的连通块的 size) + add`，用这个值来更新`ans`即可

> 困难版呢？在于说我们`for`$$(r, c)$$，是$$O(nm)$$复杂度，再对每一个$$(r, c)$$进行统计`add`
又有一个$$O(n + m)$$的复杂度，总的复杂度时$$O(n^2m + m^2 n)$$，可能无法接受
但一开始枚举$$O(nm)$$是可行的，但需要在$$O(1)$$或者$$O(\log )$$内计算出答案

那能不能通过预处理，比如说，把$$r$$两侧的连通块先预处理到`set(r)`中
同样也预处理`set(c)`中，在计算的时候，直接取`set(r)`和`set(c)`的并
这样做在极端情况下，是要耗费$$O(n)$$的时间的，复杂度又变成了$$O(n^m)$$

如果先求和呢，`sumset(r), sumset(c)`，也是不行的，因为这样我们只知道他们两侧的连通快的大小之和
并不知道这些连通快的具体编号，可能某一个连通快，同时位于`r and c`的一侧
它的`size`被加了`2 次`，这样会重复计算，也不行

> 但这个好像启发我们，可以一个连通块一个连通块地考虑

一个极大的连通块，考虑最上方和最下方，最左端和最右端，构成了$$(xl, xr, yl, yr)$$的矩形区域
矩形的左上角是$$(xl, yl)$$，右下角是$$(xr, yr)$$，假设当前连通块是$$C$$

单独考虑行和列的话，如果你要对$$x \in [xl-1, xr+1]$$的行来操作，那么这样的行对应的答案
都要算上这个连通块$$C$$
换句话说，连通块对$$x \in [xl-1, xr+1]$$有贡献，这些行的答案都要$$+|C|$$

对于$$y \in [xl-1, xr+1]$$也是如此

但这样会有重复，因为这个问题要求同时对$$(x, y)$$操作，也就是说，对于连通块$$C$$
你选$$x \in [xl-1, xr+1]$$，但是你$$y \notin [yl-1, yr+1]$$，把$$y$$选在外面，那是不会重复的
而如果你选的$$(x, y)$$，刚好落在$$(xl-1, xr+1, yl-1, yr+1)$$围成的矩形区域内
那么这个$$C$$会被多算一次

> 最后要解决的问题是，对于每一个连通块$$|C|$$，可以很方便求出$$(xl-1, xr+1, yl-1, yr+1)$$
但是怎么让矩形区域中的点都$$+|C|$$呢？

首先，之前的操作让$$(xl-1, xr+1)$$和$$(yl-1, yr+1)$$都加上$$|C|$$，这个操作很简单
**差分数组**单点修改即可，最后求具体的某个$$x$$的时候，就是求差分数组在$$x$$的前缀和即可

现在呢？怎么让一个矩形区域都$$+|C|$$，可以用二维前缀和
![](/media/content_img/cf952H2.png)

## Codeforces Round 954 (Div. 3)
### G1
**[G1. Permutation Problem (Simple Version)](https://codeforces.com/contest/1986/problem/G1)**
给定一个排列$$p$$，长度是$$n$$，问有多少对下标$$(i, j), 1 \leqslant i < j \leqslant n$$
满足$$(i \cdot j) \mid (p_i \cdot p_j)$$

**算法分析**
不难发现，可以先$$/ gcd(p_i, i)$$，即$$\dfrac{a_i}{b_i} \dfrac{a_j}{b_j}$$
此时有$$(a_i, b_i) = 1, (a_j, b_j) = 1$$，那么所求的下标，满足限制
```math
\displaystyle
\begin{cases}
b_j \mid a_i \\
b_i \mid a_j \\
i < j
\end{cases}
```
不妨令$$(a_i, b_i)$$表示$$\dfrac{a_i}{b_i}$$
```bash
对于特定的 i，找 j > i，并且
(a[i], b[i]) <--> (a[j] 是 b[i] 的倍数，  b[j] 是 a[i] 的因子)
```

这样的统计可以**开一个桶**来解决，一般是**遍历一个限制的桶**，然后查询另一个限制
```bash
倒着 for i = (a[i], b[i])
	(1) 考虑先满足 > i 的 j，b[j] | a[i] 的限制
		for a[i] 的因子 bj，在 bj 的桶 buc[bj] 中，我们希望能够知道
		有多少个 aj 满足 aj 是 b[i] 的倍数
		
		这就需要维护 buc[bj][x] = 有多少个形如 {x, 2x, ..., kx} 的数？
		这样的话，就可以让 ans += buc[ bj ][ b[i] ]
		
	(2) 考虑维护，当前的 a[i] 对 (b[下标 < i 的数] | a[i]) 有贡献
		for a[i] 的所有因子 d,  buc[ b[i] ][d] += 1
```

上一篇：算法竞赛选题——概率与期望（四）已经是最后一篇啦

看完文章有啥想法