做题记录 25.9.9

szt100309 · 2025-09-09 16:15:42 · 个人记录

\purple\odot P9361 [ICPC 2022 Xi'an R] Contests

显然除了最后一次跳跃，前面每次都会选择一场比赛，跳到能一步到达的位置中当前比赛排名最考前的

因此预处理 f_{l,i,c} 表示从 i 出发跳 2^l 次，在第 c 场比赛中能到达的最小排名

计算 f_{0,\ast} 时预处理一个辅助数组 g_{i,k,c} 表示选手 a_{k,i\sim n} 中第 c 场比赛排名的最小值

f_{l-1,\ast,\ast}$ 合并至 $f_{l,\ast,\ast}$ 时枚举中间一步选择的比赛即可做到 $O(m^2n\log n)

每次询问，特判一步能到达的情况，枚举 l=(\lfloor\log_2(n)\rfloor+1)\sim 0，若 x 跳 2^l 步后无法跳到 y 则将 2^l 计入答案，最终答案加上 2，若超过 n 则无解

时间复杂度 O((m+q)m^2\log n)

代码

参考

令 f_{i,j} 表示第 i 次操作结束后剩余 j 个白球的方案数，转移是显然的

直接由 \sum f_{m,\ast} 得到答案，显然会算重，一种方式是记录操作过程中 j 是否到过 0，只统计这部分的方案数，另一种方式为用 n 算出的答案减去 n-1 算出的答案即为正确答案

时间复杂度 O(nm)

代码

参考