首页 > 其他 > 详细

#0021. 「Codeforces」1366E Two Arrays

时间:2020-06-20 16:34:24      阅读:60      评论:0      收藏:0      [点我收藏+]

题目大意:

  给定数组a和一个上升的数组b,求将a数组划分为m段且对于任意1<=i<=m,第i段最小值为b[i]的方案数。对998244353取模。

题目解法:

  一开始一直在死磕dp后来发现大可不必

  我们要注意b是严格递增的这个限制。这意味着如果第i段的左端点在l,那么l右边的所有数一定都大于等于b[i]。因此其实每个subarray的左端点都会有一个范围。在这个范围里,所有数字都不小于b[i],且一定存在一个位置的值等于b[i]。显然这些范围都是不重叠的,根据乘法原理乘起来即可(注意第一段的左端点一定为1,不需要乘范围)。

  根据定义范围的计算方法是这样的:

  把i,j作为两个指针。任意一个时刻i,j表示a数组的第i个数在第j段里。同时我们还需要用一个r记录最靠后的与b[j]相等的位置。

  若a[i]==b[j],则更新r,i--

  若a[i]<b[j],则当前i必须放到新的一段,第j段的左端点范围在(i,r),j--。此时若r为-1则无解,直接输出0。

  若a[i]>b[j],继续更新,i--

  几个循环完成但无解的情况:

  1. j不为1(第一段的左端点一定位1)

  2. r=-1(没有等于b[1]的位置)

#0021. 「Codeforces」1366E Two Arrays

原文:https://www.cnblogs.com/myrcella/p/13169147.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!