2026 北京市赛 / 河南省赛

VP under 新赛制

两场比赛多数题目相同。第一列是北京市赛的 ID，第二列是河南省赛的。

ID		Tag	Diff	Description	Solution	Code	Review
A			Easy	任意操作：将 $1$ 替换为 $23$，将 $2$ 替换为 $31$，将 $3$ 替换为 $12$，或删除相邻的两个相同字符。求能由 $S$ 操作得到的 $T[l, r]$ 数量。	不变量 $x=\bigoplus s_{i}$，主机派，$\mathcal{O}(N)$。	109
B	E		Medium	平面点 $A$ 和 $B$。$B$ 先手，轮流操作：将点移动至 $(x-1, y)$ 或 $(x, y-1)$。$A$ 不能移动到 $B$ 经过的所有位置，包括起点，除原点。若 $A$ 到达 $(0,0)$ 则 $A$ 获胜；否则 $B$ 获胜。	分类讨论。若 $A$ 已在原点胜。若 $B$ 已在原点胜。若 $A$ 比 $B$ 靠近原点至少两步则胜。若 $B$ 在纵轴上，当 $A$ 不在纵轴上时胜，横轴同理。若 $B$ 在第一象限内，判断 $A$ 走到 $B$ 的右上方的时间，与 $B$ 到 $(1, 1)$ 的时间。$\mathcal{O}(1)$。	187+2
C	H			构造 0 到 $N-1$ 的排列，最小化 $\prod_{i=1}^{N-1} (a_i \oplus a_{i+1})$，再最小化字典序。	最小值时，$a_i \oplus a_{i+1} = \text{lowbit}(i)$。枚举 $a_{1}$，须满足 $a_{1} \oplus \bigoplus_{i=1}^{k-1} \text{lowbit}(i) < N$。
D				对于长度为 $2 N$ 的序列 $b$，两人轮流删一个数，最终剩下两个，先手希望它们的差尽可能小，后手希望尽可能大。	排序后 $F(b)=\min(b_{i+N}-b_i)$。先手保证 $\le F(b)$：取走 $[i^*, i^*+N]$ 以外的全部 $N-1$ 个数。后手保证 $\ge F$：对称取 $(b_{i}, b_{i+N})$，将剩下某个 $\lbrace i, i+N \rbrace$。
				长度为 $2 N$ 的序列 $A$。依次处理操作：(a) 设 $A$ 排序后为 $b$，输出 $\min_{i}(b_{i+N}-b_i)$；(b) $A_X \gets A_X + 1$；© 对所有 $i$，$A_i \gets \max(A_i - T, T)$。	设全局偏移量 $d$，全局下界 $h$，辅助数组 $v$，满足 $a_i=A_i+d=\max(v_i, h)$，设 $a$ 排序后为 $b$，设 $l_i=b_i, r_i=b_{i+N}$。线段树维护节点的 $\min r$, $\max r$, $\min l$, $\max r$, $\text{Ans}=\min(r-l)$。 (a) 输出 $\text{Ans}$； (b) 设 $x = \max(v_i, h)$，线段树二分找到 $l$ 中 $x$ 的最后一次出现位置 $p$，更新 $l_p \gets l_p+1$，$r$ 同理，随后 $v_i \gets x+1$； © 设 $x = d+2T$，更新 $l_i \gets \max(l_i, x)$，即线段树二分找到 $l_i<x$ 的范围后做区间赋值，对完整的 $l$ 节点更新 $\min l=\max l=x$，并更新 $\text{Ans}=\min r-x$，$r$ 同理，随后 $d \gets d+T$，$h\gets \max(h, x)$。
E	C		Easy	有 $M$ 个任务，每个任务需要被处理 $K$ 次。每一单位时间，可以选择至多 $N$ 个不同的任务，并分别处理一次。最小化总时间。	$\max(K,\lceil \frac{MK}{N}\rceil)$。	38+1
F	B		Medium	长度为 $N$ 的排列 $A$，操作：选择区间 $[l, r]$，若满足对 $i \in [l, r]$，$A_i > \max(A_{l-1}, A_{r+1})$，则翻转 $A[l, r]$。分别最大化、最小化 $\sum_{i=1}^N i \times A_i$。	操作等价于在 Cartesian 树上交换左右子树。$\mathcal{O}(N)$。	146
G	J			$f(s)$ 表示满足 $\operatorname{prefix}(s,i)=(\operatorname{suffix}(s,i))^R$ 的最大 $i$。求所有 $f(S[l,r])$ 之和。
H			Hard	$3$ 个初始为空的能量球槽位。有 $N$ 个回合。第 $i$ 回合，有 $A_i$ 张卡牌 A 和 $B_i$ 张卡牌 B，任意顺序打牌。打出卡牌 A 时，若存在空槽位，则占用一个空槽位并生成一个球；否则造成 $D$ 点伤害。打出卡牌 B 时，若场上有球，则消耗一个球并造成 $2D$ 点伤害，同时释放对应槽位；否则无效果。每回合结束时，若场上有 $x$ 个球，则造成 $x$ 点伤害，且球会保留到下一回合，卡牌不保留。求 $N$ 个回合内能造成的最大总伤害。	DP。考虑某回合从 $x$ 个球变成 $y$ 个球，需要消耗 $p + A - q$ 个球。$\mathcal{O}(N)$。	AC
I	I		Expert	有 $N$ 支队伍和 $M$ 场比赛，每支队伍最多参加 $2$ 场比赛。将每支队伍分配给 $2$ 位教练之一。对于每场比赛，若有一支分配给教练的队伍参赛，则该教练获得 $1$ 个礼品。求两位教练获得的礼品总数最大值。	(1) 比赛为点，队伍为边。特别地，若一支队伍只参加一场比赛 $u$：新建虚拟叶子 $x$，连边 $(u,x)$。得到的图有重边无自环。 (2) 对边二染色，目标是使尽可能多的点满足其关联边中有两种颜色。 (3) 只有纯奇环分量不能让每个点有两种颜色，答案减去 1。 (4) 构造：若是欧拉图，即所有点的度数都是偶数，纯环显然，否则存在度数至少为 $4$ 的点 $s$，以它为起点求欧拉回路，则除 $s$ 外的每个点都有两种颜色，而欧拉回路至少出入两次 $s$，可以对其中一个环反转达到两种颜色。若存在奇度点，新建超级虚点 $s$，从 $s$ 向每个奇度点连边，得到欧拉图，以 $s$ 为起点求欧拉回路，则除 $s$ 外的每个点都有两种颜色。$\mathcal{O}(N + M)$。	AC
J	A			对排列 $a$，令 $l$ 为满足 $\max_{j=1}^i a_j = a_i$ 的 $i$ 的数量，$r$ 为满足 $\min_{j=1}^i a_j = a_i$ 的 $i$ 的数量。对 $1 \sim N$ 的随机排列，求满足 $l \ge r + K$ 的概率。
K			Expert	从长度为 $N$ 的排列中随机选择 $b$，重复随机选择 $\lfloor \lvert b \rvert /2 \rfloor$ 个的元素删除，直至递增。求最终剩余的元素个数的期望。	设第 $i$ 轮的长度为 $x_i$。定义假想过程：即使已经递增，也继续随机删除，直到只剩一个元素。一个序列一旦递增，此后的序列都递增。因此实际执行第 $i$ 轮删除的概率（在所有随机过程中，而非在前一轮保留的排列中），在假想过程就是排列不递增的概率，为 $1-\dfrac1{x_i!}$。 (1) 最终剩余数量 = 初始数量 − 实际删除的总数量，故总贡献 $\displaystyle N-\sum_{i=0}^{k-1}\bigg\lfloor\frac{x_i}{2}\bigg\rfloor\bigg(1-\frac1{x_i!}\bigg)$。 (2) 按假想过程，期望贡献为 1。但如果第 $i$ 轮的假序列已经递增，实际就不需要这轮删除，撤回 $\bigg\lfloor\dfrac{x_i}{2}\bigg\rfloor$ 个删除。总贡献 $\displaystyle 1+\sum_{i=0}^{k-1} \bigg\lfloor\dfrac{x_i}{2}\bigg\rfloor \frac{1}{x_i!}$。$\mathcal{O}(N)$。	AC
	G		Expert	对特定排列 $P$，求最终剩余的元素个数的期望。	仍求假想过程就是排列递增的概率，即求有多少个长度为 $x_i$ 的递增子序列。$f_{l, i}$：以 $i$ 结尾，长度为 $l$ 的递增数列数量，$f_{l+1,i} = \sum_{j<i, P_j<P_i} f_{l, j}$，每层用树状数组辅助转移，$\mathcal{O}(N^{2} \log N)$。	AC
L	D		Hard	有 $N$ 张卡牌和初始能量 $M$。任意顺序打牌，牌有三类：能量 $\ge 1$，消耗 $1$ 点能量并造成 $D$ 点伤害；能量 $\ge 2$，消耗 $2$ 点能量并造成 $D$ 点伤害；消耗所有剩余能量 $k$ 并造成 $k \times D$ 点伤害。求能造成的最大总伤害。	把二费牌拆成两个单位，每个单位收益为 $D/2$。设 $X$ 费牌最大伤害为 $c$，将普通牌的单位收益统一减去 $c$，问题化为：总费用不超过 $M$，最大化修改后的收益之和，最后加上 $Mc$。贪心选出收益最大的 $M$ 个单位。若没有选出半张牌，得到的方案已经最优。否则，设被拆开的二费牌为 $x$，答案形态可能为：扔掉 $x$；扔掉 $x$，加入一张未选中的一费牌；不扔 $x$，删去一张已选中的一费牌。$\mathcal{O}(N)$。	71+5
	K		Easy	01 矩阵，判断是否满足 1 格边连通，在该 1 的连通块内部，恰好存在两个 0 连通块。	补全边界后，有 1 个 1 的连通块，3 个 0 的连通块。$\mathcal{O}(M N)$。	AC
	L		Medium	求不定方程 $Ax_{1}+Bx_{2}+Cx_{3}+Dx_{4}=E$ 在 $x_{i}\in[L, R]$ 的整数解数量。	变形为 $Ax_{1}+Bx_{2}=E-Cx_{3}-Dx_{4}$，折半枚举，$\mathcal{O}(V^{2}\log V)$，其中 $V=R-L$。	AC