26.9.11 比赛记录

更新于 2026年9月26日约 3 分钟阅读

成外 & 梦熊 CSP-S 模拟赛 2。

T1 construct

输出 1,2,⋯ ,99,100,200,⋯ ,9900,10000,20000,⋯ ,990000,10000001,2,\cdots,99,100,200,\cdots,9900,10000,20000,\cdots,990000,1000000 即可。

T2 count

数数题。

可以发现无论怎么操作,字符串的连续的 0/10/1 段数一定不会改变。并且可以证明,一个字符串经过若干次操作,总能变成另一个具有相同 0/10/1 个数以及 0/10/1 段数的字符串。

设 0,10,1 的出现次数、段数分别是 s0/1,c0/1s_{0/1},c_{0/1}。

根据隔板法,可以计算出 s0s_0 个物品分成 c0c_0 组的方案数为 Cs0−1c0−1C_{s_0-1}^{c_0-1},s1s_1 个物品分成 c0c_0 组的方案数为 Cs1−1c1−1C_{s_1-1}^{c_1-1}。

因此最终答案为: Cs0−1c0−1×Cs1−1c1−1 C_{s_0-1}^{c_0-1}\times C_{s_1-1}^{c_1-1}

T3 query

这道题既有思维,又融合了线段树优化建图、Tarjan 缩点、DAG 上 DP、ST 表等算法和数据结构。

记 lil_i 为 A 处在 ii,B 处在 i+1i+1 时,A 最左能够走到的地方。rir_i 为 A 处在 ii,B 处在 i+1i+1 时,A 最右能够走到的地方。

题目中给定的起始位置 (a,b)(a,b),A 最左能够走到的地方为 min⁡i=ab−1li\min_{i=a}^{b-1} l_i,B 最右能够走到的地方为 1+max⁡i=ab−1ri1+\max_{i=a}^{b-1} r_i。如果 A 最左能够走到的地方在 cc 左边,B 最右能够走到的地方在 dd 右边,就是成立的。

接下来考虑如何求 l,rl,r。记 ii 至多使用一个跳板的情况下,最左走到的地方为 pip_i,最右走到的地方为 qiq_i。则可以让 ii 向 [pi,qi][p_i,q_i] 的点连边。区间批量连边,用线段树优化建图即可(在这场比赛赛后几天,教练一直让我们做线段树优化建图,都快做麻了)。之后 Tarjan 缩点缩成一个 DAG,按照拓扑序遍历,计算每个点的 l,rl,r 即可。

之后建一个 ST 表,维护 l,rl,r 的静态区间最值。

T4 point

数列中每一个数都可以看成一个点 (i,ai,j)(i,a_{i,j})。题目就是求曼哈顿距离不超过 kk 的点个数。

但是曼哈顿距离不超过 kk 覆盖的范围是一个菱形,不好求,因此我们用到一个 Trick,把曼哈顿距离转化成切比雪夫距离。

设 u=x+y,v=x−yu=x+y,v=x-y,那么 ∣x1−x2∣+∣y1−y2∣≤k|x_1-x_2|+|y_1-y_2|\le k 就变成了 max⁡(∣u1−u2∣,∣v1−v2∣)≤k\max(|u_1-u_2|,|v_1-v_2|)\le k。

已知点 (u1,v1)(u_1,v_1),求 max⁡(∣u1−u2∣,∣v1−v2∣)≤k\max(|u_1-u_2|,|v_1-v_2|)\le k 的点的个数就是求以它为中心边长为 2k2k 的正方形范围内点的个数。题目被转换成动态平面二维数点问题,用树套树或 CDQ 即可解决。

Vector Log · 算法竞赛学习笔记

Built with Nuxt UI & Nuxt MDC