求助训练营D.石子游戏差分写法

我们每次操作区间

对差分数组而言,相当于是

又因为,所以

操作简化为以下两种

,因为可以操作区间

,因为可以操作区间

那么是不是倒序扫描差分数组一遍就好了....但是一直

全部评论
这样考虑,每次区间+1,对应差分数组a[i++],a[i+k]--。 那么当a[i]<0时连一条i->i+k的边,当a[i]>0连一条i-k->i的边。 整个数组被拆分成若干条有向链或者环(两点配对了),把数组变成全0(1和n+1位置除外)需要从每条链的起点开始处理,链中的点会受到前面点的影响。 可参考赛中代码(有点丑):https://ac.nowcoder.com/acm/contest/view-submission?submissionId=46825912
点赞 回复 分享
发布于 2021-02-23 11:24
不是啊,看看代码。
点赞 回复 分享
发布于 2021-02-23 11:15
issue yyds
点赞 回复 分享
发布于 2021-02-23 10:49

相关推荐

04-08 23:14
已编辑
南阳理工学院 算法工程师
本人情况:26届双非本科,两段实习经历,目前拿到的都是实习的offer,一个校招的都没有,他们都说先实习,然后等拿到毕业证了直接转正,我又害怕干三个月给我叉出去面试题也发一下吧###&nbsp;杭州问尔信息技术后端登录你是怎么做的?JWT令牌你了解过吗?他虽然是一段字符串,他表达了什么东西?怎么解析出来信息和过期时间?JWT令牌怎么续期?如果我拉黑一个账号,要怎么做?两种方案(有无redis)mongodb和mysql的区别?mongodb和mysql分别实用于什么项目?选型你会怎么选?数据库的事务,那些地方需要使用,那些地方不需要使用?他会影响什么性能?mysql和pgsql有什么差异你知道吗?消息队列&nbsp;redis也有,为什么要用mq?前后端会部署吗?docker会用吗?内部通信前端&nbsp;async和&nbsp;await你知道吗?异步编程的原理是什么?vue3&nbsp;为什么你改变一个字符串&nbsp;前端会跟着改动AI工具会用什么?你会怎么用?###&nbsp;仲财通常用的锁有哪些synchronize和ReentrantLock的区别分布式锁了解吗?分布式事务mysql表字段sql优化什么时候用索引索引什么时候会失效mysql事务ioc一些项目应用问题###&nbsp;观妙科技项目问题...zset的架构是什么样子的线程池突然队列被打满了怎么办?如果上游和下游都无法控制,该怎么维护select&nbsp;*&nbsp;from&nbsp;user&nbsp;where&nbsp;age&gt;20&nbsp;order&nbsp;by&nbsp;update_time&nbsp;索引设计检索过程是什么样的冒泡排序和快排,有什么区别怎么判断链表有没有环###&nbsp;观妙科技-二面项目部分...线程池的核心参数有哪些你是怎么用线程池的JMMG1模型跳表介绍一下平衡二叉树TCP为什么要三次握手?说一下hashmap红黑树的特征你有什么学习的方法
牛马人的牛马人生:对学院本而言很强了
点赞 评论 收藏
分享
一只代码牛:应该不是你的问题,我感觉应该是最近不缺人
我的求职进度条
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

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