issue是云哥的小迷×呀

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$

全部评论

推荐最新楼层

北京师范大学数学类

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

在看机会的大学生很勤劳

昨天 11:33

已编辑

门头沟学院计算机类

暑期实习推荐

面试两个月，鼠鼠挂了一堆，只收到武汉小米和美团优选的offer（都是后端java）网上看风评都不太好，可是没有别的选了，想问问大伙选哪个

投递小米集团等公司10个岗位 > 晒一晒我的offer 我的实习求职记录

点赞评论收藏

转发

昨天 20:40

Momenta_HD Map_研发(实习员工)

4月份暑期实习大厂面经基本颗粒无收

腾讯云智 4.1短视频项目http通信加密body短信验证码，攻击ip变化，图形验证码算法 三种 两个栈三次握手MySQL索引B+树最左匹配索引排序算法 冒泡排序 快速排序 平均时间复杂度linux top命令进程和线程 切换成本死锁腾讯音乐一面 4.10第K大数（快速排序思想）最长上升子序列阿里国际 4.11JAVA特性和面向对象特性 接口和抽象类有什么异同点 深拷贝和浅拷贝区别 == 和 equals 区别 Java泛型 Java反射 Spring AOP 实现和场景Java集合底层数据结构多线程了解吗如何解决线程死锁了解分布式锁乐观锁和悲观锁怎么实现一个乐观锁线程池的参数怎么设置参数主要...

投递美团等公司10个岗位 >

点赞评论收藏

转发

No_Game_No_Life

03-31 00:57

已编辑

湖南大学计算机类

阿里云暑期实习简历投递

室友的简历颠勺他其实一面过了，面试官现场说的没问题会安排二面，但是隔两天还是被挂了。看其他贴子的说法，可能是HR给挂了。然后就开始被捞、挂简历的循环了。😂 #阿里云# #简历挂# #阿里云暑期实习#

投递阿里云等公司10个岗位

点赞评论收藏

转发

牛客893799462号

03-08 16:03

玉溪师范学院计算机类

投了几百份基本没人理，感觉简历有问题😭

点赞评论收藏

转发

04-25 21:22

浙江大学计算机类

四月的一些面经

面试官：看了你的简历，了解到你有两年半的送外卖经验，可以简单说下平时是怎么送外卖的吗？我：我首先在平台上接单，然后到店里取餐，取到餐后骑电动车到顾客留下的地址，再通知顾客取餐。面试官：你们也用电动车来配送啊，那能说一下电动车的运行原理吗？我：电动车的工作原理是通过锂电池释放存储的电能，经过电控系统将电能转化为电动机的机械能，然后电动机驱动电动车的机械结构，从而推动电动车行驶。面试官：锂电池是怎么把化学能转化为电能的呢？锂电池化学成分以及反应方程式有了解过吗？我：这个不太了解。面试官：没关系，平时有空应该多研究电动车的底层实现，这样才能提升送外卖水平。对了，你们平时开什么品牌的电动车？我：我们平...

点赞评论收藏

转发

1 收藏评论

全站热榜

正在热议

# 牛友的五一计划 #

26487次浏览 469人参与

# 市场营销面经 #

1725次浏览 79人参与

# 牛客帮帮团来啦！有问必答 #

418176次浏览 8011人参与

# 晒一晒我的offer #

2862125次浏览 50217人参与

# 互联网公司评价 #

63870次浏览 909人参与

# 提前批真的不会影响正式批吗 #

18284次浏览 230人参与

# 市场营销人求职交流聚集地 #

25527次浏览 577人参与

67191次浏览 1488人参与

# 我的上岸简历长这样 #

142881次浏览 2869人参与

# 如何看待offer收割机的行为 #

198176次浏览 3036人参与

# 国企和大厂硬件兄弟怎么选？ #

28731次浏览 553人参与

# 硬件人的春招flag #

14741次浏览 202人参与

# 简历中的项目经历要怎么写 #

384157次浏览 6439人参与

# 非技术岗薪资爆料 #

10703次浏览 208人参与

# 找工作，你会甘心进小厂还是猛冲大厂 #

25287次浏览 253人参与

# 实习想申请秋招offer，能不能argue薪资 #

4602次浏览 70人参与

# 产品实习，你更倾向大公司or小公司 #

31623次浏览 498人参与

# 在国企工作的人，躺平了吗？ #

74434次浏览 910人参与

# 浅聊一下我实习的辛苦费 #

71643次浏览 653人参与

# 没有实习经历，还有机会进大厂吗 #

261392次浏览 4927人参与

牛客网
牛客企业服务