2021-02-23 09:34 江西师范大学 golang

关注

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

我们每次操作区间 $[i-k+1,i]$

对差分数组而言,相当于是 $a[i+1]--$ 而 $a[i-k+1]++$

又因为 $i\in[k,n]$ ,所以 $i+1\in[k+1,n+1]$

操作简化为以下两种

当 $i==n-k+1$

$a[i]++$ ,因为可以操作区间 $[n-k+1,n]$

当 $i\in[k+1,n]$

$a[i]--$ 而 $a[i-k]++$ ,因为可以操作区间 $[i-k,i-1]$

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

全部评论

推荐最新楼层

我不会玩锐雯

吉首大学 Java

这样考虑，每次区间+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

我不会玩锐雯

吉首大学 Java

不是啊，看看代码。

点赞回复分享

发布于 2021-02-23 11:15

Kur1su

北京师范大学 C++

issue yyds

点赞回复分享

发布于 2021-02-23 10:49

06-24 18:52

门头沟学院 Java

腾讯CSIG真的很缺人吗？

今天接到了hr约面电话，没想到6月底了腾讯还在捞人，因为之前面试都挂了，约面试的时候有点没信心面了

点赞评论收藏

06-25 18:26

辽宁大学实施工程师

快入职了，hr突然跑过来说，要综合考虑

马上七月了，都快入职了😅大家感觉都准备入职了吧，只有我主动收到了hr的“你测评差点挂我们要综合考虑”

在抱佛脚的小松鼠很想回老家：这不是坑人吗😅

点赞评论收藏

05-07 17:58

门头沟学院 Java

27届找日常实习，简历求锐评

处女简历，项目是点评加外卖，打算五月中旬八股背得差不多就投，求各位大佬提建议   

wuwuwuoow：1.简历字体有些怪怪的，用啥写的？ 2.Redis 一主二从为什么能解决双写一致性？ 3.乐观锁指的是 SQL 层面的库存判断？比如 stock > 0。个人认为这种不算乐观锁，更像是乐观锁的思想，写 SQL 避免不了悲观锁的 4.奖项证书如果不是 ACM，说实话没什么必要写 5.逻辑过期时间为什么能解决缓存击穿问题？逻辑过期指的是什么其实也没什么多大要改的。海投吧

简历中的项目经历要怎么写简历被挂麻了，求建议

点赞评论收藏