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) 回帖