【每日一题】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. 如果你对牛客博客有任何意见或建议:牛客博客意见反馈专贴
全部评论
https://blog.nowcoder.net/n/79afdf81c2404bb1ab2892ff271f8adf
1 回复 分享
发布于 2021-03-08 15:23

相关推荐

01-28 16:12
中南大学 Java
几年前还没有chatgpt的时候,刷题真的是很痛苦。刷不出来只能看题解,题解有几个问题:第一个是每次看的写题解的人都不一样,很难有一个统一的思路;第二个也是最重要的是,题解只提供了作者自己的思路,但是没有办法告诉你你的思路哪里错了。其实很少有错误的思路,我只是需要被引导到正确的思路上面去。所以传统题解学习起来非常困难,每次做不出来难受,找题解更难受。但是现在chatgpt能做很多!它可以这样帮助你 -1. 可以直接按照你喜欢的语言生成各种解法的题解和分析复杂度。2. 把题和你写的代码都发给它,它可以告诉你 你的思路到底哪里有问题。有时候我发现我和题解非常接近,只是有一点点🤏想错了。只要改这一点点就是最优解。信心倍增。3. 如果遇到不懂的题解可以一行一行询问为什么要这样写,chatgpt不会嫌你烦。有时候我觉得自己的range写错了,其实那样写也没错,只是chat老师的题解有一点优化,这个它都会讲清楚。4. 它可以帮你找可以用同类型解法来做的题。然后它可以保持解法思路不变,用一个思路爽刷一个类型的题。如果题目之间思路又有变化,它会告诉你只有哪里变了,其他的地方还是老思路。5. 它也可以直接帮你总结模板,易错点。经过chat老师的指导,我最大的改变是敢刷题了。之前刷题需要先找某一个人写的算法题repo,然后跟着某一个人他的思路刷他给的几个题。如果想写别的题,套用思路失败了,没有他的题解,也不知道到底哪里错了;看别人的题解,思路又乱了。这个问题在二分查找和dp类型的题里面特别常见。但是现在有chat老师,他会针对我的代码告诉我我哪里想错了,应该怎么做;还按照我写代码的习惯帮我总结了一套属于我的刷题模板。每天写题全是正反馈!
明天不下雨了:那我建议可以用 chatgpt atlas 或者 dia 去刷,也可以用 chrome 加个 ai 插件去刷 左边刷题右边 chat 效果很好
AI时代的工作 VS 传...
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务