Codeforces 杂题训练 - 洛谷保存站

# Codeforces 杂题训练

发现最近的 Codeforces 比七八年前的要难得多，所以从新往旧做题。

除了 CF 评级以外我还标了我的评级，表示这题对我来说的难度。

- $\text{Easy}$：能轻松解出的。
- $\text{Normal}$：长时间思考才能解出的。
- $\text{Hard}$：需要看题解才能解出的。
- $\text{Insane}$：看了题解，反复又看，苦苦思索，苦苦调试，最终解出的。

CF 题的特点：

- 一般对于 $\le 2100$ 的题中以数学题、序列题为主。

## 结论

**自然数的异或前缀和**：[A003815 - OEIS](https://oeis.org/A003815)

$$
\begin{gather}
f(x)=\bigoplus_{i=1}^xi\newline
f(x)=\begin{cases}
x&x\equiv 0\pmod 4\newline
1&x\equiv 1\pmod 4\newline
x+1&x\equiv 2\pmod 4\newline
0&x\equiv 3\pmod 4\newline
\end{cases}\newline
\text{G.f.:}~F(x)={x(1+3x-x^2+x^3)\over (1-x^4)(1-x^2)}
\end{gather}
$$

## 杂题

- [Timofey and Black-White Tree - CodeForces 1790F](https://vjudge.net/problem/CodeForces-1790F) $2100~\text{Hard}$

> 给定一个 $n~(n\le 2\times 10^5)$ 个点的树，初始全白，$n$ 次将某个白点染黑，每次输出两个黑点之间的最小距离。

对于每个点维护 $d_u$ 表示黑点离 $u$ 的最小距离，更新时则暴力 BFS，遇到**无法更新答案**时则返回。由于 $\sqrt{n}$ 次操作后 $d_u=O(\sqrt n)$，每次更新 $d_u$ 至少减 $1$，故总时间复杂度 $O(n\sqrt n)$。

更进一步地，我们只更新祖先节点，这样的时间复杂度为 $O\left(\sum_{i=1}^\infty {1\over i}\right)=O(n\log n)$。

- [The Harmonization of XOR - CodeForces 1787E](https://vjudge.net/problem/CodeForces-1787E) $2100~\text{Hard}$

> （构造题）判断一个 $n~(n\le 2\times 10^5)$ 的排列是否能分成 $k$ 组，使得异或和皆为 $x$。

判断很简单，构造时，先尽可能地将原序列拆分为 $\{i\}$ 与 $\{i,i\oplus x\}$，之后剩下的数的异或和必为不可拆分的 $0^\dagger$，之后合并即可。时间复杂度 $O(n)$。

$^\dagger$证明：对于 $n$ 为 $2$ 的次幂显然，对于非 $2$ 的次幂，分 $x$ 的最高位为 $0$ 和 $1$ 讨论。无论怎样，剩下的数的异或和都不可能为 $x$。根据必然存在拆分的前提，得证。

- [Another Wine Tasting Event - CodeForces 1776G](https://vjudge.net/problem/CodeForces-1776G) $2100~\text{Hard}-$

> （构造题）求一个长度为 $2n-1~(n\le 10^6)$ 的 $01$ 串 $S$ 中，能够选出 $n$ 个互异且长度不小于 $n$ 的区间使得 $1$ 的个数皆为 $x$ 的一个合法的 $x$。

$x=\max_{i=1}^n\sum_{j=i}^{i+n-1}S_j$ 必然合法。因为如果存在位置 $k$ 使得 $\sum_{i=k}^{k+n-1}S_i$ 正好等于 $x$，左右两边的区间都可以靠向中心扩展使得答案成为 $x$。时间复杂度 $O(n)$。

- [The Human Equation - CodeForces 1775E](https://vjudge.net/problem/CodeForces-1775E) $2100~\text{Hard}$

> 给定一个长度为 $n~(n\le 2\times 10^5)$ 的序列 $a$，每次可以选取其中一个子序列并将其元素交错加减 $1$，问使其全 $0$ 的最小步数。

**考虑前缀和**，求前缀和后这等价于选取一个子序列加 $1$ 或减 $1$，求出前缀和数组的极差即可，时间复杂度 $O(n)$。

- [Hossam and (sub-)palindromic tree - CodeForces 1771D](https://vjudge.net/problem/CodeForces-1771D) $2100~\text{Normal}+$

> 给定一棵 $n~(n\le 2\times 10^3)$ 个点的树，每个点有字符，求所有路径上最长回文子序列的最大值。

最长回文子序列是动态规划的经典问题，有方程式：

$$
f(u, v) = \max\left\{ f(u + 1, v), f(u, v - 1), f(u+1,v-1)+[s_u=s_v]\times 2\right\}
$$

但是在树上搜索顺序较为复杂， 使用记忆化搜索即可，时间复杂度 $O(n^2)$。

--------

Update on 2023/3/5：发现 $2100$ 的 CodeForces 题对于我太难了，所以降低难度刷题。从现在开始，我也不太喜欢通过 Vjudge 交 CF 题了，之后只有组题单再用它吧。

- [Maximum Subarray - 1796D - Codeforces](https://codeforces.com/problemset/problem/1796/D) $2000~\text{Hard}-$

> 给定一个长度为 $n~(n\le 2\times 10^5)$ 的序列 $a$，要求正好进行 $1$ 次操作，将其中 $k~(k\le 20\land k\le n)$ 个数加 $x$，剩余的数减 $x$，求最终最大子段和的最大值。

动态规划，设 $f(i,j,0/1/2)$ 表示考虑 $a[1\ldots n]$，已经加了 $k$ 个数，当前在子段前/在子段内/在子段后的最大子段和的最大值。这个动态规划也可以看作一个分层的 DAG。时间复杂度 $O(nk)$。

- [Teleporters - 1791G2 - Codeforces](https://codeforces.com/problemset/problem/1791/G2) $1900~\text{Normal}+$

> 一条直线上有 $0,1,\dots, n+1$ 这些点，$1,2,\dots,n~(n\le 2\times 10^5)$ 每个点上具有一个传送门，代价为 $a_i$，初始在 $0$ 号点，每次可以进行如下操作：
>
> - 向左或向右移动一个单位，代价为 $1$ 元；
> - 使用当前所在点的传送门，代价为 $a_i$ 元，可以传送到 $0$ 或 $n+1$，传送门使用后作废。
>
> 求从 $0$ 点出发能够使用的传送门数量的最大值。

对每个传送门分别计算代价，代价为 $\min\left\{ i+a_i,n+1-i+a_i \right\}$，然后枚举每一个传送门作为第一个传送门，使用前缀和和二分查找计算能够使用的最大值并更新答案即可，时间复杂度 $O(n\log n)$。

- [Moving Dots - 1788D - Codeforces](https://codeforces.com/problemset/problem/1788/D) $2000~\text{Normal}$

> 给定一条直线上 $n~(n\le 3\times 10^3)$，第 $i$ 个点的坐标为 $x_i$，开始时，每个点会向离它最近的点靠拢（如果相同就向左边），并最终变成若干个点，求对于这些点所有的大于 $2$ 的子集，最终变成点数之和。

观察到这等价于求相邻的两个点，一个向左移动，一个向右移动的情况数总和。枚举所有可能相邻的点，双指针维护左右两边最近能出现的点，再用二的次幂统计即可，时间复杂度 $O(n^2)$。

- [Game on Axis - 1787D - Codeforces](https://codeforces.com/problemset/problem/1787/D) $1900~\text{Hard}$

> 给定一条直线上 $n~(n\le 2\times 10^5)$ 个点，每个点有 $a_i~(-n\le a_i\le n)$，初始在点 $i$，每次进行如下操作：
>
> - 若 $1\le i\le n$，则到达 $i+a_i$；
> - 否则游戏结束。
>
> 游戏开始前选择一个 $(x,y)~(1\le x\le n,-n\le y\le n)$，并 $a_x\gets y$，求能使游戏在有限步内结束的方案数。

分初始能结束和不能结束两种情况讨论。当初始能结束时，对 $1\to \mathtt{end}$ 上的所有节点讨论连出环的情况。当初始不能结束时，对 $1$ 所在环上节点讨论能使游戏结束的情况。时间复杂度 $O(n)$。

- [Dasha and Nightmares - 1800F - Codeforces](https://codeforces.com/problemset/problem/1800/F) $1900~\text{Hard}$

> 给定 $n~(n\le 2\times 10^5)$ 个长度之和不大于 $5\times 10^6$ 的字符串，求有多少个有序二元组 $(i,j)$，使得 $s_is_j$ 中正好出现了 $25$ 个不同的字符，且每个字符的出现次数为奇数。

枚举没有出现的字符，之后有序二元组满足条件就等价于其出现奇数次元素集合的对称差大小正好为 $25$。时间复杂度为 $O(\sum s_i+2^\Sigma+\Sigma n)$。

## 精题

### Serval and Brain Power

- [Serval and Brain Power - 1789F - Codeforces](https://codeforces.com/contest/1789/problem/F) $2700~\text{Hard}$

> 给定长度为 $n$ 的字符串 $S~(n\le 80)$，定义 $T$ 为一个重复串当且仅当 $T$ 可表示为 $k~(k\ge 2)$ 个 $T^\prime$ 顺次拼接而成。求 $S$ 最长为重复串的子序列长度。

注意到 $80$ 的数据范围不大，绝对不是常规的字符串算法。考虑对 $k$ 的大小分类讨论。注意到只有当 $k$ 为质数时才有意义。

当 $k=2,3$ 时，答案可以通过枚举分界点，并对两边求最长公共子序列得到，时间复杂度 $O(n^{2k-1})$。注意这种高维的递推一般都具有较小的常数（指数阶乘的倒数），直接暴力计算即可。

当 $k\ge 5$ 时，将原先的序列分成 $5$ 段，根据鸽巢原理，必然有 $T^{\prime}$ 的某一次出现被完全包含在某一段中，将序列分成五份后枚举所有段的所有子序列检验出现次数。该部分的时间复杂度 $O(n2^{n/5})$。

综上，我们可以在 $O(n^5+n2^{n/5})$ 的时间复杂度内解决该问题。

### Laboratory on Pluto

- [Laboratory on Pluto - 1775F - Codeforces](https://codeforces.com/contest/1775/problem/F) $2500~\text{Hard}$

> 求网格图上由 $n~(n\le 4\times 10^5)$ 个小正方形形成的图案中周长的最小值，构造一组方案，并求出方案数。

观察到形成的图案一定可以表示为一个 $x\times y$ 的长方形中去除四个角中的某些方格。挖去一个角的方案数即分拆数之和 $g(i)=\sum_{j=0}^ip(i, j)$，在四个角挖 $i$ 个方格的方案数将其卷积三次即可。

若要构造一组方案，则取 $x=\left\lceil \sqrt n \right\rceil$，$y$ 取能取到的最小值必然符合要求。求方案数时枚举 $x,y$ 并统计。

### Labeling the Tree with Distances

- [Labeling the Tree with Distances - 1794E - Codeforces](https://codeforces.com/problemset/problem/1794/E) $2400~\text{Hard}$

> 给定一棵 $n$ 个点的数和一个大小为 $n-1$ 的多重集 $A$，求所有满足条件的结点 $x$，使得 $D_i=\left\{\operatorname{dis}(i, x)\mid i\in[1\dots n]\right\}$ 是 $A$ 的超集。

对于树上图上的判定问题，一个很常见的技巧是哈希，CSP-2022 的《星战》一题采用的就是这样的思想。对于这道题，符合要求的 $D_x$ 满足 $\exists i\in[0\dots n-1],D_x=A\cup \left\{i\right\}$。存储每个集合在空间上没有办法接受，考虑采用多项式哈希，即，用多项式每项的系数存储每个数的出现次数，以某个点值作为哈希值。在树上递推可以得到所有 $D_i$ 的哈希值，逐一验证即可。注意使用多模数以提高正确率。时间复杂度 $O(n)$。

正在渲染内容...