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$

全部评论

推荐最新楼层

Kur1su

北京师范大学 C++

issue yyds

点赞回复分享

发布于 2021-02-23 10:49

我不会玩锐雯

吉首大学 Java

不是啊，看看代码。

点赞回复分享

发布于 2021-02-23 11:15

我不会玩锐雯

吉首大学 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

昨天 19:04

福建师范大学天线工程师

我自己结束了秋招

深圳的校招暂时告一段落，没想到会这么快结束，心里有些遗憾。尽管我一直在努力尝试，考上编制并不是我的终极目标，但我真的希望能给自己一个好的起点，给这几年的努力一个交代。

牛客创作赏金赛

点赞评论收藏

11-27 11:29

小红书_社区技术部_前端开发(实习员工)

10.30字节一面

【再再再再再再再战字节，摆烂了，这次一面都没过（手撕做出来了前面还有几轮字节面试忘记录音了，就不记录了。1.自我介绍2.主要技术栈是3.是否了解react4.做题【建议下次做这种题目拿个草稿纸！！】 console.log('start'); setTimeout(() => { console.log('children2'); setTimeout(function() { console.log('children8'); }, 0) ; Promise.resolve().then(() => { console.log('chil...

查看16道真题和解析面经烤面筋

点赞评论收藏

11-21 04:35

电子科技大学 Java

还没约面问最低薪资😅

逆天公司，这种正常吗😅

努力学习的小绵羊：我反倒觉得这种挺好的，给不到我想要的就别浪费大家时间了

点赞评论收藏

11-29 14:47

字节跳动_后端开发(准入职员工)

逆天华为

逆天 hr。。先是在面试之前给我换了两次面试时间，面试完就不回消息了。面试时候我已经明确说了我不接受上海和深圳，没有 hc 你给我挂了就是了现在说这个😅化身华黑子，纯逆天

沉淀一会：1.同学你面试评价不错，概率很大，请耐心等待； 2.你的排名比较靠前，不要担心，耐心等待； 3.问题不大，正在审批，不要着急签其他公司，等等我们！ 4.预计9月中下旬，安心过节； 5.下周会有结果，请耐心等待下； 6.可能国庆节前后，一有结果我马上通知你； 7.预计10月中旬，再坚持一下； 8.正在走流程，就这两天了； 9.同学，结果我也不知道，你如果查到了也告诉我一声； 10.同学你出线不明朗，建议签其他公司保底！ 11.同学你找了哪些公司，我也在找工作。

点赞评论收藏