2026.1月算法竞赛选题（一）

[[ slider_text ]]

[[ item.c ]]

2026.1月算法竞赛选题（一）

发布时间 2026-01-14 作者：秋千月 来源：算法小站

mex 树上差分 二维数点 逆序对

## Educational Codeforces Round 186
### C
**[C. Production of Snowmen](https://codeforces.com/contest/2182/problem/C)**
堆雪人，雪人有`3`个部位，必须满足`a < b < c`，现在有`3`条产线，环形的，长度为`n`
其中第一条产线生产`a`，第二条产线生产`b`，第三条产线生产`c`
现在生产`n`个雪人，需要确定$$(i, j, k)$$，第一个雪人`(a[i] < b[j] < c[k])`
第二个雪人`(a[i+1] < b[j+1] < c[k+1])`，依此类推
问合法的$$(i, j, k)$$方案数

**算法分析**
看成是长度为`n`的圆，`a[1...n]`和`b[1...n]`能否**匹配上**，取决于**相对偏移量**
**两个长度为`n`的圆相互匹配，看成映射**，比如说$$a_i \to b_j$$

那么之后任意位置$$a\_{i+d}$$能够映射到的位置是**确定的**，就是$$b\_{j+d}$$

> 这种问题的处理方法

可以看成`a, b`**两个单位圆**一开始是**对齐的**，即`a[0] = b[0]`
然后考虑`b`转相应的角度$$\theta$$，枚举每个角度，枚举每个位置$$i$$
检查$$a\_i, b\_{i + \theta}$$能否匹配上即可

### D
**[D. Christmas Tree Decoration](https://codeforces.com/contest/2182/problem/D)**
装饰圣诞树，有`n+1`个饰品，编号`[0...n]`，第$$i$$个盒子的饰品数量是$$a_i$$
现在问合法排列的数量，合法排列定义如下
```bash
编号 p1 的人只能从编号 p1 的盒子，或者从 0 号盒子中取出一个饰品
编号 p2 的人只能从编号 p2 的盒子，或者从 0 号盒子中取出一个饰品
依此类推
在 pn 之后，周期性地再从 p1 开始做，直到取完所有的饰品
```
问合法排列的方案数

**算法分析**
首先游戏会进行若干轮，假设若干轮之后取完所有的饰品$$S$$
那么$$S = qn + r$$，游戏一定至少进行$$q$$轮，剩下有$$[1\cdots r]$$个位置
再额外执行一轮，额外轮位置最多有$$r$$个

**贪心地**，每个人应该先把它自己盒子里的拿完，然后再拿公共的$$a_0$$盒子

那么如果$$a_i > q+1$$一定无解
如果$$a_i = q+1$$，那么这样的人一定要放在**额外轮**的位置上，并且它不会消耗$$a_0$$
如果$$a_i < q$$，那么它要消耗公共资源即`a[0]`，消耗掉$$cost_i = q - a_i$$个

我们先算一下$$\sum cost_i$$，如果$$\sum cost_i > a_0$$，那么一定无解
然后考虑需要放在**额外轮**的人数$$K$$，如果$$K > r$$，那么也无解
（这$$K$$个人称为**必须的人**）

否则，还需要$$r - K$$个人补上**额外轮**位置，每个人都会另外消耗`1`个单位的公共资源
`waste = r - K`，如果$$waste + \sum cost_i \neq a_0$$，同样无解

否则就可以正常消耗了，在$$r$$个额外轮的位置，选$$K$$个**必须的人**
方案数是$$\displaystyle \binom{r}{K} \cdot K!$$
剩下的$$n - K$$个人是自由人，没有限制，可以随便排

方案数就是$$\displaystyle \binom{r}{K} \cdot K! (n - K)!$$

## Educational Codeforces Round 168
### D
**[D. Maximize the Root](https://codeforces.com/contest/1997/problem/D)**
给定`n`个点的树，执行以下操作任意次，将非叶子结点的点`u`权值`a[u] += 1`
同时，令所有**`u`的子树(不包括`u`)**中的点`v`权值`a[v] -= 1`
但是要保证任何时刻，树上所有点的权值都必须$$\geqslant 0$$，问根节点最大的权值？

**算法分析**
假设$$u$$有$$k$$个儿子$$v_1, v_2, \cdots, v_k$$
最终我们要统计$$\forall i, v_i \to u$$**贡献的流量**，然后取一个`min`，就是`u`能增加的权值

但庆幸的是，对于每个$$u$$及其子树，它往`root`贡献的流量是确定的
这取决于它的子树中$$\min(a[v]) = mn$$
如果$$a_u \geqslant mn$$，`u 往上贡献的流量`就是$$mn$$
否则$$a_u < mn$$，但是$$a_u$$是有可能通过操作变大的，假设变成$$now$$
满足$$d = now - a_u, \quad mn - d \geqslant now, \quad now \leqslant \lfloor (mn+a_u) / 2 \rfloor$$
此时贡献的流量就是`now`
这些都可以`dfs`求出来

## 牛客周赛 Round 122
### D 一个 mex 问题
**[Digital Deletion](https://ac.nowcoder.com/acm/contest/125083/D)**
给定序列`a`，现在把`a`的所有子序列的和（包括空的）都加入到`S`中
求出`S`的`mex`，现在发现，从`a`中删掉一些数并不影响`mex`，问最多可以删掉多少数

**算法分析**
> 如果求出一段区间`mex`，那么$$\geqslant mex$$的数**都可以扔掉**

可以考虑对`a`排序，那么考虑$$x = a_i$$是否有用
维护前缀可能出现的数$$[0, R]$$，假设这些数都出现，尝试加入$$x$$
如果能加入$$x$$，也就意味着会新出现$$[x\cdots R+x]$$这些数
那么如果$$x > R+1$$，说明不管怎么样都缺了一个$$R+1$$，不可能填上了
之后的数都应该舍弃，否则$$x$$肯定是有贡献的，会贡献$$[\cdots R+x]$$这一段
让$$R = R + x$$继续讨论

## Good Bye 2023
### D
**[D. Mathematical Problem](https://codeforces.com/problemset/problem/1916/D)**
构造一个$$n \times n$$的矩阵，每个位置的值都是`1`位数
这样每一行构成一个长度为`n`的`n`位数，需要保证它是完全平方数
另外它不能有前导`0`
此外，还必须矩阵中每个数出现次数都相同
这`n`行构成的`n`个数还必须互不相同

**算法分析**
打表不解释，对于$$n = 13$$的情况，枚举$$x = [10^6, 10^7)$$之间的$$x^2$$，同时要使得$$x^2$$的长度为$$13$$
怎么解决所有数出现的次数都相同呢？

**随机一个下标`j`**，根据下标令$$v = tot_j$$，计算`v`中`[0-9]`出现了多少次`tar`
然后枚举每一个`tot`，计算当前的数，`[0, 9]`出现的次数`cnt`
当`cnt = tar`，就把它放到`cand`中，`cand`数量$$\geqslant 99$$就退出
发现很容易就可以找到这样的表了

这样能保证前面长度为`13`的高位，都是满足限制的，后面就补`0`补到`n`即可

非要观察规律，那就是说$$(10^x + 3)^2 = 10^{2x} + 6 \cdot 10^x + 9$$，`1, 6, 9`加上若干个`0`去构造
类似地，$$(3 \cdot 10^x + 1)^2 = 9 \cdot 10^{2x} + 6 \cdot 10^x + 1$$，同样也只涉及`1, 6, 9`

### E
**[E. Happy Life in University](https://codeforces.com/contest/1916/problem/E)**
有`n`个节点的树，每个节点有一个颜色$$1 \leqslant a_i \leqslant n$$
现在要找到一对$$(u, v)$$，使得$$f(u, lca(u, v)) \cdot f(v, lca(u, v))$$最大
其中`f(x, y)`定义成$$x, y$$简单路径上有多少个不同的颜色
求这个最大值

**算法分析**
> 初步想法，求路径上有多少个不同的数，转成`dfs 序`后，可以剖链，对应成一段区间
区间内有多少不同的数，可以主席树求解

现在问题是，如果枚举`nowlca`，我们**去子树中**找两个`[x, nowlca], [y, nowlca]`尽量大
会导致什么情况呢？`x, y 的 lca`**可能并不是我们枚举的`nowlca`**
而是`nowlca`子树中的其他点，这样`lca --> nowlca`这部分路径的贡献，可能会被多计算

那这个问题怎么解决呢？还是枚举`u`作为`lca`
这个时候考虑$$u$$的**不同的子树分支**`v1, v2, ..., vm`，对每一个分支$$v_i$$，**很标准的**
**求子树中任意两个分支`f(v1) * f(v2)`最大的问题**
```bash
维护 mx = 已经遍历过的分支的最大值
for v in g[u]:
	当前分支是 v，最大值 now = query(L, R), 其中 L, R 对应 v 及其子树的 dfs 序
	ans = max(ans, mx * now)
	chmax(mx, now)
	
这样算的话，mx 和 now 对应取到最大值的点，他们的 lca 就一定是 u 了
```

> 但这样做有一个问题，`dfs(v1)`的时候，即使剖链
能求出来` subtree(v1)`中的任意一个节点`x`到`v1`这条路径上有多少个不同的颜色
即`cnt(x --> v1)`，但是怎么求**这些`cnt`的最大值**呢？
难道要`for`所有`subtree`中的点吗？

**这里有一个贪心**
假设说`u`作为`lca`的话，那么$$f(x, u), f(y, u)$$，**把`x, y`都向下延伸到叶子结点是不劣的**

> 那么我们就只需要考虑在叶子结点结算，叶子$$x \to lca$$有多少个不同的数？记为`cnt`
另外还需要对叶子结点的`cnt`取一个最大值

那么，当枚举$$u = lca$$的时候，只有`u`**所在的子树对应的叶子结点`x`**，`x --> u 路径`可能会对答案有贡献
这样如果我们只在叶子结点执行修改操作的话，就可以`query(l[u], r[u])`（$$l_u, r_u$$分别对应$$u$$及子树所在的`dfs序`）
在$$\log n$$的复杂度内求出最大值了

**枚举$$u$$作为`LCA`**
1) 如果`a[u]`没有在$$u$$的子树中出现过，那么所有叶子结点$$\forall x \to u$$（`u = LCA`）路径的贡献都会`+1`
执行区间`[ l(u), r(u) ] += 1`

2) 如果`a[u]`已经出现过了怎么办？假设说$$a_v = a_u$$，$$v$$及其子树中的叶子节点，**不会受`u`的影响**
因为$$[l_v, r_v] \subseteq [l_u, r_u]$$，所以如果单纯的对`[l(u), r(u)] += 1`，会导致`[l(v), r(v)]`也被`+1`
而这是不应该的，此时需要将`[l(v), r(v)] -= 1`即可

> 这样算法就比较容易了

用`vec[color] := set dfs 序编号 {k1, k2, ..., km}`表示`color`在哪些点出现
然后`dfs(u)`并且枚举`u`作为`LCA`

1）先在`vec[ a[u] ]`中找到$$k_v \in [l_u, r_u]$$，对应到原来树中的点是$$v$$，`set 中`删除$$k_v$$
同时令线段树$$[l_v, r_v] -= 1$$

2）在`vec[a[u]]`中插入`u 的 dfs 序编号`，同时对$$[l_u, r_u] += 1$$

3）按最开始的方法，找到两个分支的$$\max[l_v, r_v]$$乘起来最大

## Codeforces Round 917 (Div. 2)
### D
**[D. Yet Another Inversions Problem](https://codeforces.com/problemset/problem/1917/D)**
给定长度为$$n$$的排列`p`，`p`由$$1\sim 2n-1$$所有奇数构成
同时给定长度为$$k$$的排列`q`，`q`由$$0 \sim k-1$$的**所有数**构成，下标都是从`0`开始
现在构造一个`a[0, 1, ..., nk-1]`，长度为$$nk$$的数组，满足$$a(ik+j) = p_i \cdot 2^{q_j}$$
![](/media/content_img/cf917D.png)

下面求`a`的逆序对的个数，对`998244353`取模

**算法分析**
首先不难发现，同一组的逆序对，就取决于`q`的逆序对的数量

现在来看跨组的逆序对，不妨设$$i < j$$，第`i`组的基础值都是$$p_i$$，第`j`组的基础值都是$$p_j$$
现在$$(i, j)$$要构成逆序对，假设存在两个位置$$(j_1, j_2)$$，对应的值是$$q_1, q_2$$
```math
p_i \cdot 2^{q_1} > p_j \cdot 2^{q_2} \\
\quad \\
\dfrac{p_i}{p_j} > \dfrac{2^{q_2}}{2^{q_1}} \\
\quad \\
\dfrac{p_i}{p_j} > 2^{q_2 - q_1}
```
因为$$n \leqslant O(2\times 10^5)$$，所以$$|q_2 - q_1| \leqslant 20$$

1）一旦$$|q_2 - q_1| > 20$$，不可能找到合法的$$(p_i, p_j)$$，方案数不存在
2）对于$$-20 \leqslant (q_2 - q_1) \leqslant 20$$，暴力，枚举$$d = q_2 - q_1$$有多少对
记为$$cnt(d)$$，这样的话，又变成了一个二维偏序，$$i < j, \quad p_i > p_j \cdot (2^d)$$
这可以用树状数组求出，记得$$\times cnt(d)$$
3）对于$$q_2 - q_1 < -20$$，此时任意$$\binom{n}{2}$$的$$(p_i, p_j)$$组合都可以

## Codeforces Round 919 (Div. 2)
### D
**[D. Array Repetition](https://codeforces.com/contest/1920/problem/D)**
给定一个空数组`a`，按顺序执行`n`次操作，两种类型
`1 x`，将$$x, x \in [1, n]$$添加到`a`的末尾
`2 x`，复制$$x$$份当前序列`a`的拷贝，添加到末尾，保证之前至少进行过一次`1`操作

`q`个询问，每次询问`a[kth]`是多少

**算法分析**
> 先复习一个问题

**[leetcode 458 场周赛，序列复制处理问题](https://www.ringalgo.com/article/72/)**
这种问题的一种思路是，预处理每一次操作，假设操作编号是$$k$$，可以处理$$sz(k)$$
即执行完操作`k`之后，现有序列的长度

> 会做上面的题之后，这个问题也独立写出来了，核心在于$$\bmod len$$

不难发现只有$$\log$$次的操作`2`，每次操作用$$ops_i = (tp, l, r, x)$$来封装
如果$$tp = 2, ops_i = (tp, l, r, len)$$，`len`表示单位长度，比如添加`t 个 copy`
那么`len = |copy|`

其中$$[l, r]$$表示第`i`次操作，在尾部添加的序列下标是$$[l, r]$$
如果`tp = 1`，`x = 添加的数`，否则，`x = len = 添加的单位长度|copy|`

那么我们可以`dfs(kth)`，每次`dfs`二分`kth`落在哪个操作区间内
比如操作$$p$$，增加了$$[l, r]$$，我们二分出第一个满足$$r \geqslant kth$$的操作序列编号$$p$$

如果操作`p`对应类型`1`，直接输出`x`
否则呢？令$$nkth = kth \bmod len$$，然后继续`dfs(nkth)`

> 坑点，可能会越界，$$\lim = 10^18$$，进行操作`2`的时候，考虑增加的量$$\Delta$$
以及能够增加的量`canadd = lim - 当前len`，然后$$\Delta = \min(\Delta, canadd)$$

### E
**[E. Counting Binary Strings](https://codeforces.com/contest/1920/problem/E)**
一个二进制串是好的，当且仅当它恰好包含`1 个 1`
现在要计算有多少个二进制字符串`s`满足以下条件
1）`s`恰好包含`n`个好的子串，$$n \leqslant 2500$$
2）`s`没有长度严格$$> k$$的好的子串，其中$$k \leqslant n$$
注，子串必须连续

**算法分析**
> 可能的突破口，`s[1...n] = 11...1`一定是好的，下面考虑将若干个`1`改成`0`
或者是需要在后面补`0`？

如果是`s[1, n] = 11...1`，后面补`0`是不可能的，这只会让好子串的个数`> n`
**观察一**
对于`s[1, n] = 11...1`，前缀可以改出`[0, k-1]`个`0`，后缀也可以改出`[0, k-1]`个`0`
**枚举前缀能改出`pre`个`0`，后缀能够改出`suf`个**，要求`n - (pre + suf) >= 1`
此时都可以满足恰好有`n`个好串
另外，还必须满足好串的长度$$\leqslant k$$，这意味着改太多前缀/后缀的话
`0..010..0`将不再是好串（除非$$k = n$$）

不难发现，两个好串之间，需要用`...0[11]0...`，用`[11]`来隔离，防止两个好串拼接在一起
导致长度$$> k$$
进一步地，长度恰好为$$K$$的好串，`1 [...长度恰好为 k 的好串...] 1`，**两端必须用`1`来隔离**

**观察二**
好像对于长度为`n`的串来说，不能出现形如`11..1011..`的结构？
好像要求中间不能有`0`？（除非`k = 1`特判？）

转移的时候，好像还必须考虑前缀，否则处理不了`00...010....0`的情况？
（此时存在$$> K$$的很长的好串，不合法）
```bash
好串的结构大致是
1 [... 仅有1个1...] 1 [00..1..0] 1 [0...1...00] 1 ... 
```
**观察三**
> 计数的同时，还必须满足，`s`中好串的个数**恰好为`n`**，能不能把好串的个数**设计到状态中去**？
类似背包，假设当前已经有$$dp(i, ?)$$个好串，然后枚举在每个位置放入`1`，贡献`cost`个好串
那么还需要$$dp(i-cost, ?)$$个好串

这样就可以做了
1）发现需要满足恰好为`n`的限制，所以把能贡献的合法子串个数设计到状态中，$$dp(i, ?)$$
2）另外，发现最后的计数和**前缀 and 后缀**能允许多少个`0`有关，设计状态转移

枚举每一个能放`1`的位置，然后枚举`1`之前有多少个前缀`0`呢？假设是$$pre$$个
（实际上就是当前`1`到上一个`1`之间有多少个`0`）
那么`1`后面呢？最多可以允许$$pre + suf + 1 \leqslant K$$个
同时，这个`1`能贡献的合法子串数量，是$$(pre+1) \cdot (suf+1)$$个
```math
\displaystyle
\forall pre \leqslant K - 1: \quad 
dp(i, pre) = \sum_{sf \leqslant K-1-pre} dp(i - (pre+1)(sf+1), \quad sf) \\
(pre+1)(sf+1) \leqslant i
```
这个是一个调和级数
```bash
for i = 1 to n:		枚举已经有的合法子串的个数
	for pre, for suf, 限制是 (pre+1)*(suf+1) <= i and pre+suf+1 <= K
		dp(i, suf) += dp(i - (pre+1) * (suf+1),  pre)
```
其中枚举`pre, suf`的复杂度是$$O(n^2)$$，但是合法的$$(pre, suf)$$对应的，合法的$$i$$的状态
是调和级数的，即$$\log(n^2)$$

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

看完文章有啥想法