牛客练习赛 118 题解

A. Hard KMP Problem

记录两个串中每种字符的出现次数为 $s_i,t_i$ 。计算 $\min{\lfloor\frac{s_i}{t_i}\rfloor}$ 即可。

B. Sum Gcd

有很多种做法，其中一种是： $f(x)=\gcd(x,k)$ 是积性函数，因此，上式在 $i\not =j$ 时满足 $\frac{\gcd({a_i}\times{a_j},k)}{\gcd({a_i},k)}=\gcd(a_j,k)$ 。特别注意 $i=j$ 的时候单独计算。

C. Future Machine

考虑三个数 $X,a,b$ ，考虑操作可以变成 $X=\max(X,\min(a,b)),X=\min(X,\max(a,b))$ 。

那么考虑枚举 $i$ ，如果 $X\leq x_i$ ，那么操作 $m$ 次以后一定还满足 $X\leq x_i$ 。记 $mn,mx$ 分别为 $y$ 数组的最小值和最大值，不难发现 $i$ 固定时进行 $m$ 次操作后 $X\rightarrow \max(X,\min(x_i,mx))$ 。同理对 $X>x_i$ 的情况也有类似结论。

因此 $O(n+m)$ 模拟一遍即可解决问题。

D. Binary String Game

可以证明当 $m\not =n$ 时，有如下结论：

当 $m$ 为偶数时，可以到达任何一个 1 个数奇偶性不变的状态。

当 $m$ 为奇数时，可以到达任何一个状态。

确定一个方案之后可以使用类似 bfs 或者 dfs 的手段求出某个包含 $x$ 个 1 的状态。

当然其实最简单的方法还是我们手动构造。

发现不管什么情况下我们都可以用两次操作恰好翻转 $2$ 格。那么当我们需要选的 $1$ 的个数是偶数的时候就做完了，如果是奇数，先翻翻翻到只剩一个，最后这一个跟另外任意 $m-1$ 个组成一组再翻一次，那么接下来就要把 $m-1$ 个翻回去，而 $m-1$ 是偶数所以做完了。

E. Slove Equations

$ax+b=y,x=\frac{y-b}{a}$ 。

然后这个东西其实也是可逆的，所以可以直接维护前缀信息，注意维护无解和多解的情况。

F. The Closest Pair

$\max(a_i,a_j)=x,\min(a_i,a_j)=y$ 。

$x \bmod y=x-\lfloor\frac{x}{y}\rfloor y$ 。

枚举 $y$ 以及 $\lfloor\frac{x}{y}\rfloor$ ，合法的 $x$ 在值域上是一个区间。考虑 $y$ 所在的下标 $i$ ，以及右侧的一个合法的 $x$ 下标为 $j$ ，设 $y$ 右侧的另一个合法的 $x$ 所在的位置为 $k$ ，当 $(i,k)$ 比 $(i,j)$ 优秀则需要满足 $a_{j}\bmod a_i>a_{k}\bmod a_i$ ，同时又因为 $(i,k)$ 需要比 $(j,k)$ 优秀，因此可以加紧限制考虑 $a_{j}\bmod a_i> 2\times (a_{k}\bmod a_i)$ 。左右分别只有 $\log$ 对。