牛客练习赛 118 题解

A. Hard KMP Problem

记录两个串中每种字符的出现次数为 。计算 即可。

B. Sum Gcd

有很多种做法,其中一种是: 是积性函数,因此,上式在 时满足 。特别注意 的时候单独计算。

C. Future Machine

考虑三个数 ,考虑操作可以变成

那么考虑枚举 ,如果 ,那么操作 次以后一定还满足 。记 分别为 数组的最小值和最大值,不难发现 固定时进行 次操作后 。同理对 的情况也有类似结论。

因此 模拟一遍即可解决问题。

D. Binary String Game

可以证明当 时,有如下结论:

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

为奇数时,可以到达任何一个状态。

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

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

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

E. Slove Equations

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

F. The Closest Pair

枚举 以及 ,合法的 在值域上是一个区间。考虑 所在的下标 ,以及右侧的一个合法的 下标为 ,设 右侧的另一个合法的 所在的位置为 ,当 优秀则需要满足 ,同时又因为 需要比 优秀,因此可以加紧限制考虑 。左右分别只有 对。

这样我们扣出 对可能成为答案的点对之后扫描线即可。

全部评论
没看懂 F 那个加紧的限制
1 回复 分享
发布于 2023-11-11 17:16 重庆
请问e有哪些无解和多解的情况😥
点赞 回复 分享
发布于 2023-11-10 22:22 四川

相关推荐

不愿透露姓名的神秘牛友
今天 11:27
点赞 评论 收藏
分享
牛客83700679...:简历抄别人的,然后再投,有反馈就是简历不行,没反馈就是学历不行,多投多改只要技术不差机会总会有的
点赞 评论 收藏
分享
程序员小白条:找的太晚,别人都是大三实习,然后大四秋招春招的,你大四下了才去实习,晚1年
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
昨天 12:02
ssob上原来真有BOSS啊
硫蛋蛋:这种也是打工的,只不是是给写字楼房东打工
点赞 评论 收藏
分享
评论
6
1
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务