竞赛讨论区 > 【题解】wannafly挑战赛16
头像
牛客网小运营
编辑于 2018-12-27 14:48
+ 关注

【题解】wannafly挑战赛16

(题解由比赛出题人提供,点击右侧“本文相关内容”的题目即可开始做题)

T1 取石子

考 虑 取 出 的 石 子 序 列 , 序 列 长 度 为 a+b+c+d , 属 于 第 1,2,3,4 堆 的 石 子 分 别 有 a,b,c,d 因 此 答 案 为 C(a+b+c+d,a) C(b+c+d,b) C(c+d,c)=(a+b+c+d)!/(a!b!c!d!)

T2 AB序列

图片说明

显然这是个关于x的凹函数,最小值在-Ai,Bi,0组成的集合的中位数取到,如中位数有两个则最小值在两个中位数之间取到时间复杂度
图片说明 (线性时间求中位 数),
或者图片说明 (排序)
当然也可以用二分/三分等方法求最值,时间复杂度图片说明

T3 小球碰撞
对i=1到10000000线性预处理2i-1模998244353的乘法逆元 设弹球第一次落地位置为x(L<=x<=R),则当且仅当k<= (R+x)/2x<k+1 时 , 落 在 区 间 内 的 次 数 为 k 即 R/(2k+1)<x<=R/(2k-1) 时 , 落 在 区 间 内 的 次 数 为 k 答 案 为图片说明
图片说明
可见答案只和L/R有关,而且每个询问的分子部分都 是(1/(2k-1)-1/(2k+1))k的前缀和加上一项边界情况 预处理前缀和,每次回答询问时处理一下边界即可

T4 打怪
设状态为f[i][j][k],表示处理完第i只怪,武器是j,属性是k的最短时间 武器/属性的切换只需在打每只怪之前考虑 转 移的时候,分别考虑武器,属性的转换即可 由于武器/属性的转换是一个有向图,间接切换可能比直接切换更优, 所以一开始要跑Floyd求最短路。

T5 弹球弹弹弹
n个位置构成环套树森林,可以拆分为一些有根树和有向环,且有根树的根的后继为有向环上的点 对有根树进行轻 重链剖分,对于一个球,经过 条轻边后可以到达环上 对于一条重链或一个环,维护一个序列表示每个位置 球的个数 当一个球经过一条轻边时,修改离开的重链和进入的重链或环 每次操作后,环对应的序列会循环移动一 位,重链对应的序列会向深度较浅的方向移动一位(由于球离开重链导致移位出界的情况已被处理,重链上也可视 为循环移位) 这些移位不需要直接处理,只需在需要修改/查询序列的某个位置时,将操作位置加上对应的偏移量 即可
另一个做法是对环用数组维护,考虑去掉环剩下的每棵树,每次加入球就在对应位置记录这个球的 加入时间+离根 的距离 ,查询时查一个点子树内 加入时间+离根的距离 等于相应值的球的个数 对每个值x,用 支持维护有序集合、 查询区间元素个数 的数据结构维护 加入时间+离根的距离=x 的球的dfs序编号,查询为对某个x,问dfs序在区间内 的球的个数。

T6 修改序列值
如果一个位置x是极大值(即a[x-1] < a[x] >= a[x+1]),那么x-1和x+1不会有机会成为最大值,且x会成为最大值a[x] 次,此时可以把a[x-1]和a[x+1]直接设为0而不影响答案 将a[x-1]和a[x+1]设为0后可能会出现新的极大值,最终整个 序列所有非0位置都为极大值,非0位置的值之和即为所求答案 分析以上找极大值的过程可知,实际上是从每个初始 极大值开始向两侧隔一个位置取一个位置,直到遇到极小值(a[x-1]>=a[x]<a[x+1])或边界(x=1或x=n)为止,一 个极小值当且仅当在和两侧极大值距离均为偶数时会成为极大值 于是可以用数据结构维护极大值、极小值以及它们 之间的区间 可以用平衡树/线段树维护极大值和极小值位置构成的序列,支持插入删除查询前驱后继,用树状数组/ 线段树分别维护原序列奇偶位置的前缀和,支持单点修改 也可以直接用线段树维护原序列,分类讨论两个区间信息合并的每种情况。

其他疑问可加以下交流群(加入一个即可啦~)
牛客多校算法训练营1:453799454
牛客全国算法训练营2:330766563
牛客多校算法训练营3:934889305

全部评论

(0) 回帖
加载中...
话题 回帖

等你来战

查看全部

热门推荐