A

简要题意

有多少种从 $\{1, 2, \dots, n\}$ 当中选取数字的方法，使得对于选出的任意两个奇偶性相同的元素 $a, b$，$\frac{a + b}{2}$ 也被选出。

有多测。

$1 \lt T \le 10^5, 1 \le n \le 10^6$。

做法

假设选出来的是 $a_1 \lt a_2 \lt \dots \lt a_k$。对于相邻两项 $a_i, a_{i + 1}$，如果他们奇偶性相同，则 $\frac{a_i + a_{i + 1}}{2}$ 也应被选出。所以 $a_i$ 和 $a_{i + 1}$ 的差为奇数。考虑相隔一项的 $a_i, a_{i + 2}$，他们的差必定为偶数，所以 $\frac{a_i + a_{i + 2}}{2}$ 需被选出，必须为 $a_{i + 1}$。因此，选出来的必定为公差为奇数的等差数列。

考虑公差为 $d$ 的方案数。

$$\sum_{l = 1}^{\lfloor\frac{n - 1}{d}\rfloor}n - d(l - 1) = n(\lfloor\frac{n - 1}{d}\rfloor) - d \times \frac{1}{2}(\lfloor\frac{n - 1}{d}\rfloor - 1)\lfloor\frac{n - 1}{d}\rfloor $$

那么，最终的答案就是

$$\begin{align*} &\sum_{d = 1, 2 \not| d}^n n(\lfloor\frac{n - 1}{d}\rfloor) - d \times \frac{1}{2}(\lfloor\frac{n - 1}{d}\rfloor - 1)\lfloor\frac{n - 1}{d}\rfloor\\ =&\sum_{d = 1}^n n(\lfloor\frac{n - 1}{d}\rfloor) - d \times \frac{1}{2}(\lfloor\frac{n - 1}{d}\rfloor - 1)\lfloor\frac{n - 1}{d}\rfloor\\ &-\sum_{d = 1}^{\lfloor\frac{n}{2}\rfloor}n(\lfloor\frac{\lfloor\frac{n - 1}{2}\rfloor}{d}\rfloor) - d (\lfloor\frac{\lfloor\frac{n - 1}{2}\rfloor}{d}\rfloor - 1)\lfloor\frac{\lfloor\frac{n - 1}{2}\rfloor}{d}\rfloor\\ =&\sum_{d = 1}^{n - 1} n(\lfloor\frac{n - 1}{d}\rfloor) - d \times \frac{1}{2}(\lfloor\frac{n - 1}{d}\rfloor - 1)\lfloor\frac{n - 1}{d}\rfloor\\ &-\sum_{d = 1}^{\lfloor\frac{n - 1}{2}\rfloor}n(\lfloor\frac{\lfloor\frac{n - 1}{2}\rfloor}{d}\rfloor) - d (\lfloor\frac{\lfloor\frac{n - 1}{2}\rfloor}{d}\rfloor - 1)\lfloor\frac{\lfloor\frac{n - 1}{2}\rfloor}{d}\rfloor \end{align*} $$

可观察得到，$\sum_{d=1}^n\lfloor\frac{n}{d}\rfloor$ 可以根据 $\lfloor\frac{n}{d}\rfloor$ 的值预处理。时间复杂度 $O(n + T)$。

我们令 $f_n = \sum_{d = 1}^n\lfloor\frac{n}{d}\rfloor$，则有以下递推式：$f_n = f_{n - 1} + r(n)$，其中 $r$ 表示因子个数。线性筛即可。

B

简要题意

给定一个字符串 $T$，问 $T$ 有多少个子串可以写为 $AABA$ 的形式。

$|T| \le 10^5$。

做法（官解）

考虑 $A$ 作为 $T$ 的所有后缀，则所有以 $AA$ 为前缀的后缀按字典序排序之后是连续的。

二维数点。

C

简要题意

给你 $n$ 个分数 $\frac{a_i}{b_i}$，问：最少多少进制下，这些分数写成小数形式均为有限小数？

$1 \le n \le 10, 1 \le a_i, b_i \le 100$。

做法

令答案为 $p$。在 $p$ 进制下有限等价于该分数可描述为 $\frac{x}{p^k}$。因此，$\frac{b_i}{(a_i, b_i)} | p^k$。约分后取所有质因子乘积即可。

答案很大，要 __int128。

D

简要题意

给你一个有向图，问至少删多少条边让它变成 DAG。

$1 \le n \le 22, 1 \le m \le \sout{500}462$。

做法

本质求最大生成 DAG。

考虑状压。令 $dp_S$ 表示只保留 $S$ 点的最大边数。因为 DAG 中至少有一个点没入边，所以可以转移：$dp_S = \max_{i \in S}\{dp_{S \setminus \{i\}} + |v_i \cap (S \setminus \{i\})|\}$。$v_i$ 表示 $i$ 的出边集。

E

签到题，跳过。

F

签到题，跳过。

G

暴力题，跳过。

H

简要题意

给你一个序列 $a_1, a_2, \dots, a_n$，每次你可以选一个子区间 $[l, r]$，把 $a_{l \dots r}$ 替换为他们的中位数。问你能否把所有数变成 $k$。

对于长度为 $n$ 的序列 $a$，它的中位数为其中第 $\lfloor\frac{n + 1}{2}\rfloor$ 小的数。

有多测。

$1 \le \sum n \le 10^5$。

做法

如果 $k$ 不在 $a$ 中出现，显然不行。

否则，只要我们能让 $a$ 中出现连续两个 $\ge k$ 的数就行了。

我们把 $\lt k$ 的换成 $0$，$\ge k$ 的换成 $1$。如果不存在，则两个 $1$ 之间至少有一个 $0$。如果之间只有一个零，选取这三个数进行操作即可。

如果所有相邻的 $1$ 之间都有多个 $0$，则不行。

I

原题，ABC315F，去年集训的，徐老师讲过。

J

简要题意

问 $n \times m$ 的棋盘上最多放多少个互不攻击的马。

$1 \le n, m \le 10^9$。

做法

令 $n \le m$。

当 $n = 1$ 时，全放，答案为 $m$。

当 $n \ge 3$ 时，棋盘黑白染色后有大小为 $\lfloor\frac{nm}{2}\rfloor$ 的完美匹配，所以答案为 $\lceil \frac{nm}{2}\rceil$。

当 $n = 2$ 时，考虑一下布局：

$$\begin{array}{c|c|c|c|c|c|c | c} \hline & K & K & & & K & K & \dots \\ \hline & K & K & & & K & K & \dots \\ \hline \end{array} $$

$m \bmod 4$ 分类讨论即可。