做题记录 25.8.29

· · 个人记录

QOJ #7645. Shoes

将所有位置排序，设 0 左侧的位置为 l_{1\sim lp}，0 右侧的位置为 r_{1\sim rp}，两者按绝对值从小到大排序

定义某一天为合法的当且仅当这一天中同时访问了 l 中的位置和 r 中的位置

可证最优解中合法的每一天访问的区间互相嵌套，不合法的每一天每次访问连续的一段

因此任意一天结束时，都恰好访问了 l 和 r 的一个前缀

设目前访问了 [l_x,r_y]，则可以转移到 [l_u,r_v]\;(u\ge x,v\ge y)

倒序，从 (lp,rp) 转移至 (0,0)，每天可以缩小一次区间，满足对应距离不超过限制

令 dp_{x,y} 保存若干二元组，表示 [l_x,r_y] 的答案，其中每个二元组 (u,v) 表示缩小的第 u 天还剩下 v 个可以访问（倒序转移可以直接得到今天的总移动距离，时间上限减去总移动距离除以 k 下取整即为剩余可以访问的数量），显然每个 u 记录最大的 v 即可，可证只需要保留最小的 u

转移是容易的

时空复杂度 O(n^2)

代码

参考：1 \quad 2

QOJ #7606. Digital Nim

令 s(i) 表示 i 的数位和

令 f_n 表示 n 对应的 \text{SG} 函数值，显然

f_0=0,f_n=\text{mex}_{j=i-s(i)}^{i-1} \{f_j\}

令 ls_n 表示 [0,n] 中最后一个满足 f_i=0 的 i，显然

ls_0=0,ls_i=\begin{cases}ls_{i-1}&ls_{i-1}\ge i-s(i)\\i&\text{otherwise}\end{cases}

令 pl_i=i-ls_i，则

pl_0=0,pl_i=\begin{cases}pl_{i-1}+1&pl_{i-1}+1\le s(i)\\0&\text{otherwise} \end{cases}

显然 pl_n>0 时先手必胜

令 f_{i,s,l} 表示对于一个 10^i\mid v,s(v)=s,pl_v=l 的 v，pl_{v+10^i-1} 的值

转移和求解都是简单的

时间复杂度 O(\log_b^3 V \cdot b^3+\sum \log_b V\cdot b)，其中 b=10

代码