【每日一题】4月21日题目精讲 枚举

题号 NC14583
名称 糖糖别胡说,我真的不是签到题目
来源 北京理工大学珠海学院第七届C语言程序设计竞赛
戳我进入往期每日一题汇总贴~
往期每日一题题单

图片说明

如果你在题库做题时遇到了喜欢的题目,欢迎推荐给邓老师~ 点击查看详情

任何问题都有一个从简单到复杂的过程——先考虑没有娇姐发功怎么做:
我们可以考虑每只糖糖最后能不能存活:第i只糖糖能存活的条件是他后面没有比他大的另外一组的糖糖,所以我们只需要从后往前扫描维护当前位置往后每一组糖糖的最大值是多少然后和当前糖糖的能力值比较就行。
现在再来考虑娇姐发功的问题:
娇姐会在第ci秒使得前ci个人的能力值+1,其实不影响第ci个糖糖在第ci秒消灭他前面的糖糖——大家都加一,大小关系不变;但是会影响后面的糖糖打他。换句话说,第x个糖糖开始能打前面的糖糖的时候看到的前面的糖糖数字是第x秒的数字,而随着之后大家一起增大,大小关系就不变了,所以用每个人最后他的能力值判断能不能存活就行了。
于是我们只需要把先得出每个糖糖最后的能力值,再从后往前判断他是否还存活。维护每个糖糖最后的能力值可以用差分来维护,也可也累加一下当前位置x即x往后贡献了多少个加一就可以了。

看完邓老师的题解,记得自己去做题提高呀~
欢迎各位大佬来做题写题解,也欢迎大家踊跃在当日讨论贴中提问!

活动奖励:

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

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

.牛币兑换中心

牛客博客开通方式

  1. 如何开通牛客博客:https://www.nowcoder.com/discuss/202952
  2. 如何使用博客搬家功能:进入博客--->设置--->底部博客搬家
  3. 如果你对牛客博客有任何意见或建议:牛客博客意见反馈专贴
全部评论
https://blog.nowcoder.net/n/3b121ea344394b2f8d319dfc2690ddd3 简单的前缀和,我看了两小时
1 回复 分享
发布于 2020-04-20 22:19
https://blog.nowcoder.net/n/26d3efd377b74a34921f1c03a452b0f9
1 回复 分享
发布于 2020-04-20 11:02
https://blog.nowcoder.net/n/6cf00f4ddd7b4b05b5cd8a3a0387da79 清楚姐姐之前写的题解忘记发了,现在还来得及吗
点赞 回复 分享
发布于 2020-05-08 23:04
https://blog.nowcoder.net/n/db22f7aefddf4ebd91e5057c15bc4e90  
点赞 回复 分享
发布于 2020-05-04 18:43
https://blog.nowcoder.net/n/296e0189022c440fa5a373929a797736
点赞 回复 分享
发布于 2020-05-03 09:42
https://blog.nowcoder.net/n/4956ed2eab744187801e7c7c5e83db02 差点超时了
点赞 回复 分享
发布于 2020-04-28 10:39
https://blog.nowcoder.net/n/6923810888684164852ecf8d76f718c5
点赞 回复 分享
发布于 2020-04-27 11:10
https://blog.nowcoder.net/n/6a0ce4c5a3c541bdaa1dbec84654f07d
点赞 回复 分享
发布于 2020-04-26 00:20
https://blog.nowcoder.net/n/5762ebef11464dd1b9aad72c3f67193a
点赞 回复 分享
发布于 2020-04-24 16:06
https://blog.nowcoder.net/n/b9b9b11b0bdf4f99ae52b929d487a932
点赞 回复 分享
发布于 2020-04-23 21:26
https://blog.nowcoder.net/n/37fcdc9aee4d4369a7edc8cc9f31674d
点赞 回复 分享
发布于 2020-04-23 11:26
https://blog.nowcoder.net/n/fefa3ef87e144ebf9b163b1d13d4ec1a
点赞 回复 分享
发布于 2020-04-23 10:39
这题有毒,线段树死活A不了,我都造了几百组数据对怕了
点赞 回复 分享
发布于 2020-04-22 17:42
https://blog.nowcoder.net/n/2006d630b4654c789476d8988dca30b2
点赞 回复 分享
发布于 2020-04-22 17:13
https://blog.nowcoder.net/n/afb77c878ebc4c2fa546f0427eec8811
点赞 回复 分享
发布于 2020-04-21 16:07
https://blog.nowcoder.net/n/956ebe6efe4349019e9c94f3ba3a8944
点赞 回复 分享
发布于 2020-04-21 15:23
https://blog.nowcoder.net/n/91b919b727264c8394ee587148833a8b
点赞 回复 分享
发布于 2020-04-21 09:59
https://blog.nowcoder.net/n/1c2d27e3953545a3a32fca04c5a8ef60
点赞 回复 分享
发布于 2020-04-21 08:48
https://blog.nowcoder.net/n/956ad3c5643949d0a08f99f015bd7364
点赞 回复 分享
发布于 2020-04-20 23:12
https://blog.nowcoder.net/n/c8942e56150145f5b6baa1f0993d1389
点赞 回复 分享
发布于 2020-04-20 21:55

相关推荐

自从我室友在计算机导论课上听说了“刷 LeetCode 是进入大厂的敲门砖”,整个人就跟走火入魔了一样。他在宿舍门口贴了一张A4纸,上面写着:“正在 DP,请勿打扰,否则 Time Limit Exceeded。”日记本的扉页被他用黑色水笔加粗描了三遍:“Talk is cheap. Show me the code。”连宿舍聚餐,他都要给我们讲解:“今天的座位安排可以用回溯算法解决,但为了避免栈溢出,我建议用动态规划。来,这是状态转移方程:dp[i][j] 代表第 i 个人坐在第 j 个位置的最优解。”我让他去楼下取个快递,他不直接去,非要在门口踱步,嘴里念念有词:“这是一个图的遍历问题。从宿舍楼(root)到驿站(target node),我应该用 BFS 还是 DFS?嗯,求最短路径,还是广度优先好。”和同学约好出去开黑,他会提前发消息:“集合点 (x, y),我们俩的路径有 k 个交点,为了最小化时间复杂度,应该在 (x/2, y/2) 处汇合。”有一次另一个室友低血糖犯了,让他帮忙找颗糖,他居然冷静地分析道:“别急,这是一个查找问题。零食箱是无序数组,暴力查找是 O(n)。如果按甜度排序,我就可以用二分查找,时间复杂度降到 O(log n)。”他做卫生也要讲究算法效率:“拖地是典型的岛屿问题,要先把连通的污渍区块都清理掉。倒垃圾可以用双指针法,一个指针从左往右,一个从右往左,能最快匹配垃圾分类。”现在我们宿舍的画风已经完全变了,大家不聊游戏和妹子,对话都是这样的:“你 Two Sum 刷了几遍了?”“别提了,昨天遇到一道 Hard 题,我连暴力解都想不出来,最后只能看题解。你呢?”“我动态规划还不行,总是找不到最优子结构。今天那道接雨水给我整麻了。”……LeetCode 真的害了我室友!!!
老六f:编程嘉豪来了
AI时代还有必要刷lee...
点赞 评论 收藏
分享
评论
点赞
1
分享

创作者周榜

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