前言

距离 2026 CSP 第二轮还有 71 天。

---

简单

T1-生产线

题意：按照 $a$ 个 $0$ 和 $b$ 个 $1$ 排列，问前 $n$ 个数中有多少个 $0$。

可以发现 $a+b$ 是个循环节，循环节内有 $a$ 个 $0$。可以通过 $\lfloor \frac{n}{a+b} \rfloor$ 计算有多少个循环节。去掉循环节后剩下 $n$ 除以 $(a+b)$ 个数，计算这些数中有多少个 $0$ （与 $a$ 取 $\min$）即可。答案：$\lfloor \frac{n}{a+b} \rfloor \times a + \min(n - \lfloor \frac{n}{a+b} \rfloor, a)$

T2-三数之和

题意：找出三个小于等于 $k$ 的数使其和为 $S$ 的方案数。

注意到 $2 \le K \le 2500,0 \le S \le 3K$，数据非常小。可以枚举前两个数，做差求出第三个数。统计数量即可。

T3-数学老师的难题

题意：求 $t_1$ ~ $t_2$ 的因数个数和。

可以通过前缀和转化为 $1$ ~ $t_2$ 的因数个数和减去 $1$ ~ $t_1-1$ 的因数个数和。定义 $f(x)$ 表示 $1$ 到 $x$ 的因数个数和，那么答案就是 $f(t_2)-f(t_1-1)$。

$f(x)$：直接分别求 $1$ ~ $x$ 的因数个数不好求。可以反过来想：枚举因数 $i$，计算有多少个数是 $i$ 的倍数。倍数自然就是 $\lfloor \frac{x}{i} \rfloor$。$i$ 从 $1$ 到 $x$。$t_1,t_2<10^7$，不会超时。

T4-小蛮腰

题意：用 $n$ 星号能组成的最大的小蛮腰。

1. 找规律 + 二分：通过观察可以知道边长和需要的个数的关系。再二分查找剩余最少的。
2. 枚举：可以发现图形是对称的，第 $i$ 次增加 $2(i-1)+1$ 个星号。直到总和超过 $n$，输出上一个就好了。

T5-批量更新

题意：有一个数组，每次操作将值为 $B$ 的都改成 $C$ 并输出总和。

可以使用桶排，存储库存为 $c_i$ 的有多少个。修改时（库存 $x \to y$）：$c_y=c_y+c_x,c_x=0$。总和就加上 $c_y-c_x$。

普及 +

注意到这个比赛是 “普及+”，对于洛谷难度 “普及+/提高”。

T1-试吃（eat）

目标：通过反复操作，让所有 $N$ 个人的口味都变成同一种。

操作规则：每次选一个连续区间 $[i, j]$，如果这个区间里超过半数的人喜欢同一种口味 $x$，那么区间里所有人都会变成口味 $x$。

问题：哪些口味有可能最终成为所有人的统一口味？

假设我们每次都只选连续 $3$ 个人试吃。此时问题就非常简单：$3$ 个人中，只要有 $2$ 个人口味一致，就能将这三个人统一。

如果三个人口味统一了，那就能拓展到 $5$ 个人。$5$ 个人就能拓展到 $9$ 个人。反正，只需要考虑连续 $3$ 人。所有数字塞进 set 里，最后输出就好了。

T2-工作任务（work）

题意：两个列表 $A$ 和 $B$，从头往后取数。使总和不超过 $K$ 最多能取多少个数。

首先可以考虑暴力。枚举 $A$ 中选前 $p$ 个，内层枚举 $B$ 中选前 $q$ 个。然后计算 $\sum_{i=1}^{p} A_i + \sum_{i=1}^{q} B_i$，如果没有超过 $K$ 就更新答案。

容易想到上面那一坨东西可以用前缀和优化，这样就优化到 $O(mn)$。不过还是会超时。$A$ 和 $B$ 都是正整数，容易发现做够前缀和后是单调的。此时可以用二分查找 $B$ 能选到第几个数。时间复杂度就是 $O(n \log m)$。

既然是单调的，那 $q$ 的位置就会一直往前而不会后退。那就可以用双指针。开始时 $i,j$ 都指向 $0$（什么都不选）。在 $i$ 后移的过程中，如果 $a_i+b_j\le k$ 就将 $j$ 后移，并更新答案。这样时间复杂度就优化到 $O(n+m)$。

提醒

下面 ↓ 几题我的代码都又臭又长，只能提供大概的思路了。

T3-学习计划（study）

题意：每个学生有初始分数和每天增长的分数。问多少天能达到校长给定的排名。

可以先按照排名 $t$ 升序排序。然后对于每个人，计算 $i$ 需要多少天能超过 $i+1$，答案就是所有天数中的最大值。如果有一个人不能超过，那就是不行。同时还需要计算 $i$ 能比 $i+1$ 高的最后一天。因为如果 $i$ 本来就比 $i+1$ 高并且 $i$ 相对于 $i+1$ 是下滑的，那就有可能有最后一天。

然后有两个全局的 $L$ 和 $R$ 计算所有情况都满足的第一天和最后一天。遍历完后如果 $[L,R]$ 是个合法的范围，就输出 $L$，否则就输出 $-1$。

T4-魔法井字棋（magic）

这题的 $N$ 非常小，只有 $25$。可以直接用 DFS 遍历每一种情况。注意打标记的时候要把棋盘状态和节点位置一起标记了，最后对棋盘状态进行去重。

还可以优化（我的做法）：用 DFS 遍历棋盘可能会遍历到很多无用的空格子。所以可以在 DFS 前对每个 B/M/O 做 BFS，找到可以直接相连的 B/M/O，用邻接链表存图。之后对这个图进行 DFS 就会快很多。

T5-邮票收集（stamp）

可以使用动态规划。

• 定义状态变量：定义 dp[i][j] 表示使用前 $i$ 个字母，拼出长度恰好为 $j$ 的邮票序列的方案数。
• 状态转移方程：首先要枚举 $i,j$，分别从 $1$ 到 $26$ 和 $K$。然后枚举选 $k$ 个字母 $i$。$dp_{i,j}$ 就可以加上 选择前 $i$ 个字母恰好拼出 $j-k$ 的方案数乘以在 $j$ 个位置中选出 $k$ 个放 $i$。即 $dp_{i,j}=dp_{i,j}+dp{i-1,j-k}\times C_j^k$。计算组合数 $C$ 可以直接用公式 $C_n^m=\frac{n!}{m!(n-m)!}$。
• 初始化和边界：$dp_{0,0}=1$，用 $0$ 个字母拼出长度微为 $0$ 只有一种方案，就是什么都不做。
• 答案：所有长度都是可以的，所以答案：$\sum_{i=1}^{K}dp_{26,i}$。

需要注意的地方：需要取模，所以组合数中的除法要改成乘以逆元。而且 $998244353$ 是个质数，$a 的逆元=a^{MOD-2}$。不过也可以用递推直接求出组合数。但我不会。

T6-音符序列（seq）

（提示：我的这个做法有些点竟然要 900ms 以上，非常不推荐）

题意：对字符串 $S$ 进行一些操作，修改某个字符或判断 $[l, r]$ 是否是 $S$ 排序后的子串。

可以用线段树维护区间内每种字母的出现次数（这要是二维的，要不就开 $26$ 个线段树），再用树状数组维护区间是否顺序（如果 $S_{i-1} > S_i$ 则为 $1$，否则为 $0$）

操作一：

1. 将 $S_x$ 字母对应的线段树 $x$ 上的数减一。对应的将 $c$ 线段树上第 $x$ 加一。
2. 要将 $S_x$ 替换为 $c$。如果 $S_{x-1}>c$，则将树状数组的第 $x$ 项设为 $1$。如果 $c>S_{x+1}$，则将树状数组的第 $x+1$ 项设为 $1$。
3. 将 $S_x$ 修改为 $c$。

操作二：这有两条性质：

1. 如果是 $T$ 的子串，那么 $[l, r]$ 这一段必须升序。
2. 而且 $[l+1,r-1]$ 内所有字符数量都必须和整体的数量一致。