成外 & 梦熊 CSP-S 模拟赛 2。
输出 1,2,⋯,99,100,200,⋯,9900,10000,20000,⋯,990000,1000000 即可。
数数题。
可以发现无论怎么操作,字符串的连续的 0/1 段数一定不会改变。并且可以证明,一个字符串经过若干次操作,总能变成另一个具有相同 0/1 个数以及 0/1 段数的字符串。
设 0,1 的出现次数、段数分别是 s0/1,c0/1。
根据隔板法,可以计算出 s0 个物品分成 c0 组的方案数为 Cs0−1c0−1,s1 个物品分成 c0 组的方案数为 Cs1−1c1−1。
因此最终答案为:
Cs0−1c0−1×Cs1−1c1−1
这道题既有思维,又融合了线段树优化建图、Tarjan 缩点、DAG 上 DP、ST 表等算法和数据结构。
记 li 为 A 处在 i,B 处在 i+1 时,A 最左能够走到的地方。ri 为 A 处在 i,B 处在 i+1 时,A 最右能够走到的地方。
题目中给定的起始位置 (a,b),A 最左能够走到的地方为 mini=ab−1li,B 最右能够走到的地方为 1+maxi=ab−1ri。如果 A 最左能够走到的地方在 c 左边,B 最右能够走到的地方在 d 右边,就是成立的。
接下来考虑如何求 l,r。记 i 至多使用一个跳板的情况下,最左走到的地方为 pi,最右走到的地方为 qi。则可以让 i 向 [pi,qi] 的点连边。区间批量连边,用线段树优化建图即可(在这场比赛赛后几天,教练一直让我们做线段树优化建图,都快做麻了)。之后 Tarjan 缩点缩成一个 DAG,按照拓扑序遍历,计算每个点的 l,r 即可。
之后建一个 ST 表,维护 l,r 的静态区间最值。
数列中每一个数都可以看成一个点 (i,ai,j)。题目就是求曼哈顿距离不超过 k 的点个数。
但是曼哈顿距离不超过 k 覆盖的范围是一个菱形,不好求,因此我们用到一个 Trick,把曼哈顿距离转化成切比雪夫距离。
设 u=x+y,v=x−y,那么 ∣x1−x2∣+∣y1−y2∣≤k 就变成了 max(∣u1−u2∣,∣v1−v2∣)≤k。
已知点 (u1,v1),求 max(∣u1−u2∣,∣v1−v2∣)≤k 的点的个数就是求以它为中心边长为 2k 的正方形范围内点的个数。题目被转换成动态平面二维数点问题,用树套树或 CDQ 即可解决。