竞赛讨论区 > 【每日一题】3月8日题目精讲
头像
王清楚
编辑于 2021-03-08 16:39
+ 关注

【每日一题】3月8日题目精讲

题号 NC20177
名称 等差数列
来源 [JSOI2009]
每日一题三期汇总贴~

图片说明
如果你在题库做题时遇到了喜欢的题目,欢迎推荐给邓老师~ 点击查看详情
欢迎给每日一题投稿,投稿需要提供牛客题库里的题目+题解 投稿有牛币奖励,可发站内信给王清楚或联系QQ 234186389
每日一题QQ群:659028468

题解

3月2日的每日一题里出现了线段树维护区间加等差数列的问题,这个题则更进一步——还需要回答区间最少能分成几个等差数列的询问,也就是说关注的重点为:涉及到两个子区间合并起来的时候,怎么把等差数列的个数维护出来?
如果左区间的最右边有一段长度不为1的等差数列,右区间的最左边有一段长度不为1的等差数列,那么判断他们两个公差是不是相等且能不能接起来即可。如果有一边是孤零零的一个数呢(比如左区间最后一个数和前面的不是等差数列),那么和另外一边合并时也只需要看能不能接上,如果两边都是一个孤零零的数,那么他俩则肯定可以两个一组成为一个等差数列。
所以我们需要维护:
这个区间由多少个等差数列组成
这个区间的左右两端各自有没有零散的数字(有同学也表示为区间去掉左/右/左+右端点的时候的等差数列个数,其实都是为了把区间端点位置的数拿去和相邻区间拼合)
这个区间最左边的等差数列公差和第一项是什么
这个区间最右边的等差数列公差和最后一项是什么
维护的细节比较多,需要想清楚再写。
欢迎各位大佬来做题写题解,也欢迎大家踊跃在当日讨论贴中提问!

活动奖励:

在牛客博客中写出题解,并回复地址
审核通过可获得(依据题目难度和题解的内容而定)

本道题目3月15日中午12:00之前写的题解有获得牛币资格~

.牛币兑换中心

牛客博客开通方式

  1. 如何开通牛客博客:https://www.nowcoder.com/discuss/202952
  2. 如何使用博客搬家功能:进入博客--->设置--->底部博客搬家
  3. 如果你对牛客博客有任何意见或建议:牛客博客意见反馈专贴

全部评论

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

等你来战

查看全部

热门推荐