用户工具

站点工具


2022-2023:teams:kunkunkun:2022-nowcoder-8

这是本文档旧的修订版!


2022 牛客暑期多校训练营8

A-Puzzle: X-Sums Sudoku

给出一个数独,求在其字典序最小时的 $X-num$。
设坐标从 $(0,0)$ 开始,将数独分为 $2^m\times 2^n$ 个区域,且每个区域大小为 $2^n\times 2^m$,给每个区域编号 $A_{a,b}$,显然区域 $A_{0,0}$ 的编号已知,找规律发现 $(i,j)$ 对应的数应该为区域 $A_{0,0}$ 中坐标为 $(i\%(2^n) \oplus b,j\%(2^m)\oplus a)$ 所对应的数,其中 $(a,b)$ 为 $(i,j)$ 所在区域编号,即 $a=\left\lfloor\dfrac i{2^n}\right\rfloor,\ b=\left\lfloor\dfrac j{2^m}\right\rfloor$。于是可以 $O(1)$ 计算 $X$,根据题意需要求长度为 $X$ 的前缀和。对于每行,发现每 $2^p$ 个数中前 $2^{p-1}$ 个数与后 $2^{p-1}$ 个数都小于等于或者大于一个数 $k$,即可以根据变化关系倍增求出前缀和。 对于每列,相当于将 $1\sim 2^{n+m}$ 映射为第一列进行求和操作。
每次统计答案复杂度为 $O(n+m)$

2022-2023/teams/kunkunkun/2022-nowcoder-8.1660394843.txt.gz · 最后更改: 2022/08/13 20:47 由 sd_ltt