小白月赛108题解

A

  • 的情况,答案是
  • 的情况,我们把每两次按钮先捆绑在一起,算出
    • 然后判断是否可以在前 次就完成任务,即判断
    • 如果上式成立,答案是 ,否则是

B

提供一个比较暴力的做法。对于至少有两位的数字,它是 的倍数,等价于最后两位组成的数是 的倍数。

记录出现的所有数位(以及次数),然后枚举

  • 如果 ,那么可以输出 YES 的条件是 的倍数,且数位 都有在原数出现。
  • 如果 ,那么可以输出 YES 的条件是 的倍数,且数位 在原数出现至少两次。

注意特判一位数的情况。

C

由第一个式子:异或和不是 ,那么它一定大于

将这个不等式代入第二个式子,那么必有:

而最小公倍数一定是序列每个数(包括最小数)的倍数,因此

所以,要求 每个数相等。

然后别忘了异或和不是 ,结合上一行的结论可知我们只能选奇数个相等的数。

所以如果某个数在序列出现奇数次可以一次删空;如果出现偶数次就需要删除两次(偶数 = 1+奇数)。

D

为了让 尽量大,我们应该让所有不为 值都不一样。

同时我们想要所有数的和尽量小,根据贪心策略,对于越大的 ,对应的 应该越小。

例如,我们想要让 等于 ,构造的总和最小的序列是 ,这样

因此,当 等于 时, 的下限应该是

化简后是

对于每个询问,可以二分出最大的一个不超过 ,输出 即可。注意二分过程不要溢出了。

P.S. 由于这个数这是 级别的,也可以暴力求出所有在 以内的

E

对于一个节点 ,它的颜色会波及到 的链上所有点的贡献。

假设 初始的子树内红点有 个,蓝点有 个。假设节点 节点的子树内。

  • 由红变蓝,且 ,那么 会减少
  • 由红变蓝,且 ,那么 会增加
  • 由蓝变红,不等式左边改成 即可判断。

因此我们 DFS 两次。

  • 第一次统计每个节点所在子树的红蓝点个数。
  • 第二次对于每个 ,树上前缀和求出 的链上每个点 中,满足 的点数。根据节点 颜色的变化情况得到 的变化量,再根据变化量的正负统计答案数。

F

利用若干个 vector 分别记录每个值的出现位置集合。我们先把原序列每个数取出,然后按照数值从大到小的顺序把数字放回。

放回的过程中,假设当前考虑等于 的数(先不放回),那么所有满足 的区间 ,里面放回的数都大于

所以每个区间的贡献,等于放回区间内的数的个数。求完贡献后把所有等于 的数放回。

以上操作可以用树状数组快速维护、查询。

区间数太多了怎么办? 怎么乘上去?我们可以只先关注极小有效区间,即满足 但中间不存在等于 的数的区间

区间长度为奇数,等价于左右端点的奇偶性相同;区间长度为偶数,等价于端点的奇偶性相反。

所以对于极小区间 ,假设四个量,这都可以用线性复杂度求出:

  • 中等于 且下标是奇数的元素个数
  • 中等于 且下标是奇数的元素个数
  • 中等于 且下标是偶数的元素个数
  • 中等于 且下标是偶数的元素个数

那么区间 对整个序列的贡献是

这个贡献可以代表所有包含 且端点等于 的区间,在 这一段产生的贡献和。

容易证明极小有效区间数是 的,所以总时间复杂度是

全部评论
我还是太菜了,题解都看不懂
1 回复 分享
发布于 2024-12-27 21:55 江西
mark,学习了
点赞 回复 分享
发布于 2024-12-27 23:35 广东
点赞 回复 分享
发布于 2024-12-28 10:37 江西
点赞 回复 分享
发布于 2024-12-30 17:28 北京
mark,学习了
点赞 回复 分享
发布于 03-09 22:15 吉林

相关推荐

点赞 评论 收藏
分享
02-05 08:49
已编辑
武汉大学 Java
野猪不是猪🐗:36k和36k之间亦有差距,ms的36k和pdd的36k不是一个概念
点赞 评论 收藏
分享
02-23 00:10
湖南大学 C++
点赞 评论 收藏
分享
评论
20
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务