算法周赛round31

T1¶

设共有 $n$ 名同学，记每个身高 $i$ 的出现次数为 cnt[i]；最大身高为：

\[ mx = \max(a_1, a_2, \dots, a_n) \]

根据题意，某一身高若出现次数 $\geq 2$，则能贡献一种“双人同高”的情况，否则无贡献。

因此答案可表示为：

\[ \left( \sum_{i=1}^{mx-1} [\text{cnt}[i] > 1] \cdot 2 \right) + 1 \]

其中：

$[P]$ 为艾佛森括号：若命题 $P$ 为真，则 $[P]=1$；否则 $[P]=0$；
对于每个非最大身高 $i$，若出现次数大于 $1$，则贡献 $2$；
最后额外加 $1$，对应最高身高的必定出现一次。

T2¶

给定一个三角矩阵 $a$（需在读入时补全为完整 $n \times n$ 的手势胜负矩阵），以及聪聪老师出的双手手势对 $(s_1, s_2)$。翁老师可任意选择左右手的手势 $(l, r)$，问其是否能够确保至少一只手取胜。

暴力做法

枚举所有可能手势对 $(l, r)$：

$l \in [1,n]$（代表左手手势）
$r \in [1,n]$（代表右手手势）

翁老师可以确保获胜当且仅当满足以下条件之一：

a[l][s1] == 'W' && a[l][s2] == 'W' → 左手能打赢聪聪老师双手
a[r][s1] == 'W' && a[r][s2] == 'W' → 右手能打赢聪聪老师双手

满足其中任意一个条件时，对答案贡献 $1$。

时间复杂度：$O(mn^2)$

满分解法

只需枚举手势 $i \in [1,n]$，判断它是否为对 $(s_1, s_2)$ 的 必胜手势：

若满足：

a[i][s1] == 'W' && a[i][s2] == 'W'

则称 $i$ 为必胜手势，并计入数量 $k$：$k \gets k + 1$

含义：翁老师只要任意一只手选择手势 $i$，即可确保获胜，另一只手则可以随意选择。

计算答案

若必胜手势数量为 $k$，则：

左手可以取 $k$ 种必胜手势之一
右手可取任意 $n$ 个手势

贡献：$k \times n$

同理，右手取必胜手势也可以确保胜利：

再次贡献：$k \times n$

因此：$2kn$

去重处理

上述计算 双手均取必胜手势 时出现双重统计：

例：必胜手势为 ${x_1, x_2, \dots, x_k}$

左取 $x_1$，右任取 ${x_1\sim x_k}$ 计入一次
右任取 ${x_1\sim x_k}$，左取 ${x_1}$ 又计一次

因此必须减去重复的 $k^2$：

\[ \text{Answer} = 2kn - k^2 \]

时间复杂度复杂度：$O(mn)$

T3¶

思路分析

已知任意两个数 $a_i + b_j < 2 \times 10^9$，因此它们的和最多为 10 位数。

若 $a_i + b_j$ 为一个 $k \in [1,10]$ 位整数，则必有：

\[ 10^{k-1} \le a_i + b_j < 10^k \]

移项可得对 $b_j$ 的约束区间：

\[ 10^{k-1} - a_i \le b_j < 10^k - a_i \]

因此，只需枚举每个 $a_i$，并统计与其相加得到 $k$ 位数的 $b_j$ 的数量。

设该数量为 $\texttt{cnt}$，则贡献为：

\[ \texttt{cnt} \times k \]

换句话说：对当前 $a_i$ 而言，有多少个 $b_j$ 使得 $a_i + b_j$ 为 $k$ 位数，就向答案累加 $k$ 多少次。

实现策略

由于需要快速统计区间内满足条件的元素个数，可对数组排序，并使用二分求解。

步骤：

预处理幂数组 pow10[i] = pow10[i - 1] * 10（避免使用 pow() 产生精度误差），只需预处理到 pow10[10]。
排序数组 $b$。
枚举每个 $a_i$：
- 枚举位数区间 $k = 1 \ldots 10$
- 通过二分搜索，找到满足 $$ 10^{k-1} - a_i \le b_j < 10^k - a_i $$ 的元素个数（区间左右边界分别用 lower_bound / upper_bound）
- 贡献累加：ans += cnt * k

时间复杂度分析

枚举每个 $a_i$ 需要 $n$ 次，枚举位长 $k$ 需要常数 $10$ 次，每次二分操作为 $O(\log n)$：

\[ T = O(n \cdot k \log n) = O(10n\log n) = O(n\log n) \]

T4¶

题意

给定整数 $n$ 与固定起始值 $k$，求有多少个序列 $a$ 满足如下条件：

序列长度为 $m$（未固定）；
相邻元素不相等：$a_i \neq a_{i+1}$；
序列必须严格交替：若 $a_i < a_{i+1}$，则必有 $a_{i+1} > a_{i+2}$；反之若 $a_i > a_{i+1}$，则必须 $a_{i+1} < a_{i+2}$；
序列所有元素之和为 $n$：$\sum a_i = n$；
给定初始条件 $a_1 = k$。

该问题具有明显「背包式 DP」结构：总和类似背包容量，但由于序列交替性，需要额外记录上一项的取值与单调趋势，因此构造二维状态并按趋势区分。

状态设计

考虑当前总和与当前元素的取值，定义：

\[\begin{aligned} f[i][j] = \texttt{以总和 } i \texttt{ 结束，且当前值为 } j \texttt{，并且当前为下降点的方案数}\\ g[i][j] = \texttt{以总和 } i \texttt{ 结束，且当前值为 } j \texttt{，并且当前为上升点的方案数} \end{aligned}\]

解释：

“下降点”表示上一项大于当前项；
“上升点”表示上一项小于当前项；
因为交替结构，下一次趋势将与当前趋势相反，因此两类状态需分别处理。

状态转移

枚举上一项的取值，即：

若当前为下降点，则上一项必大于当前取值 $j$：

\[ f[i][j] = \sum_{k = j + 1}^{i} g[i - j][k], \qquad j \le i \]

若当前为上升点，则上一项必小于当前取值 $j$：

\[ g[i][j] = \sum_{k = 1}^{j - 1} f[i - j][k], \qquad j \le i \]

初始化

由于题目规定 $a_1 = k$，且序列从第 1 个元素开始时趋势未确定 —— 默认可以视为两种趋势的开始点均合法：

\[ f[k][k] = g[k][k] = 1 \]

最终答案

累加所有以总和为 $n$ 结束的方案：

\[ \text{Ans} = \sum_{i=1}^n (f[n][i] + g[n][i]) \]

前缀和优化转移

直接 DP 复杂度为 $O(n^3)$，由于转移中存在区间求和，可通过前缀和加速。

定义：

\[\begin{aligned} & sf[i][j] = f[i][1] + f[i][2] + \dots + f[i][j]\\ & sg[i][j] = g[i][1] + g[i][2] + \dots + g[i][j] \end{aligned}\]

转移可化简为：

\[\begin{aligned} & f[i][j] = sg[i - j][i] - sg[i - j][j]\\ & g[i][j] = sf[i - j][j - 1] \end{aligned}\]

时间复杂度优化至 $O(n^2)$。