A 扫雷
设 f[i] 表示扫第 i 个雷的期望用时(只考虑第 i 个雷)。
成功排除当前雷:f[i]=a[i]/b[i]
未成功排除当前雷,需要从新开始排除:
然后就可以递推了,递推的同时更新前缀和就行了。
B 情书
给定一个长度为 n 的序列,若干次询问带修改,每次给定一个区间 [l,r],求所有子区间的 hash 值的和 定义一个序列的 hash 值为,将其看作 b 进制意义下的整数在十进制下的值
由于是线性相加,因此可以考虑统计贡献,即 ai 对答案产生多少贡献
显然对于一个跨过 i 的区间会在 i 处产生贡献,而且产生的贡献多少只跟右端点与 i 的距离有关,即 所以对于一个确定的右端点,左端点在哪是无关的,因此可以得到单次询问 [L,R] 时的答案 T的表达式
然后对于多组询问,只需要用树状数组维护 ai ,ai*i,ai/bi ,ai*i/bi
这些前缀和即可。
C 学习
一句话题意:树上二维限制最长不上升子序列
dp,每个点可以看做从子树转移,不过有两维限制。
于是可以看做三维偏序问题,树套树或者cdq分治即可解决。
代码
A: https://ac.nowcoder.com/acm/contest/view-submission?submissionId=40618097
B: https://ac.nowcoder.com/acm/contest/view-submission?submissionId=40618100
C: https://ac.nowcoder.com/acm/contest/view-submission?submissionId=40618089
全部评论
(2) 回帖