牛客练习赛 146
主包这次超常发挥 rk8, 可喜可贺, 离橙名又进一步!
A
将所有机器大于 1 的硬币取出, 即
如果
就有解.
B
可以通过二分确定每一天能够收集哪个区间的学分, 对于这个区间, 可以用前缀和维护最大值和次大值.
C
某些时刻小灰灰的位置是确定的, 列举出所有已经确定的位置, 考虑这些位置的距离奇偶性以及是否在同一侧, 可以发现两者之间为止部分的跳跃次数是
或者
即一段奇数或者一段偶数.
值得注意的是, 最后一个区间的贡献是连续整数.
考虑到贡献为奇数的区间至少有 1 的贡献, 且只会改变一次总贡献的奇偶性, 我们可以通过奇偶性判断有没有解. 此外, 还需判断最大可能跳跃次数是否大于等于目标次数.
D
比较经典的两个关键字的最短路问题.
题目要求我们最小化操作三的次数, 不妨以操作三的次数为第一关键字, 那么, 如果指令集 中没有某个方向, 我们就把其代价定义为 1, 否则为 0.
以时间为第二关键字, 显然第一关键字相同的情况下, 时间越小越优. 而且, 如果知道当前时间, 我们就可以计算出下一个需要的字符再次出现的时间, 这东西显然可以线性预处理.
E
很有意思的题.
显然我们可以二分找出某次操作之后区间中的最小值, 这样复杂度是带 的, 无法通过, 但这启示我们寻找线性的做法.
考虑二分的过程, 如果某次二分后, 指针向大的方向移动, 那么下次 check 时我们不需要再重新计算左侧区间的贡献, 因为可以直接用这次 check 计算出的结果. 指针向小的方向移动是同理, 更大的数字不需要再考虑了. 于是, 我们可以每次都取当前保留的区间的中位数, 然后将区间大小不断折半, 最终, 时间复杂度是线性的.
可以用 nth_element 实现, 注意慎用 vector, 尽量手写栈, 本题卡常.
F
本题有原.
目前是站内最优解.
京公网安备 11010502036488号