关于菱形前缀和，悬关

学术版

Breath_of_the_Wild @ 2024-11-29 21:25:29

rt，脑子转不动了，求助大佬们。

给定二维数组 n 行 m 列。给定 x,y ，求到 a_{x,y} 的曼哈顿距离不超过 k 的元素之和。（这些元素形成了一个菱形）

求给个方法或者给个式子（不用管菱形越界的情况）。

by yukimianyan @ 2024-11-29 21:26:44

转切比雪夫距离，做普通二维前缀和

by Breath_of_the_Wild @ 2024-11-29 21:27:13

@yukimianyan 有别的方法咩

by Breath_of_the_Wild @ 2024-11-29 21:34:04

已关 thx

by Vector_Li @ 2024-11-29 21:40:24

@Breath_of_the_Wild 转切比雪夫是最优解

by Breath_of_the_Wild @ 2024-11-29 21:40:24

@lct201714 这么典的题全洛谷就没个一样的么... thx

by _XHY20180718_ @ 2024-11-29 21:41:57

@Breath_of_the_Wild

我寻思你不是把原数组转90度一下就行了嘛（

by wfc284 @ 2024-11-29 21:42:11

@Breath_of_the_Wild 尝试转 45 ^{\circ}？

by Breath_of_the_Wild @ 2024-11-29 21:43:00

@XHY20180718@wfc284 噢噢噢完了我脑子宕机了，有道理

by wfc284 @ 2024-11-29 21:45:01

@Breath_of_the_Wild 哦，打扰了，原来这就是切比雪夫距离，才疏学浅了

by FBW2010 @ 2024-11-29 21:54:54

@Breath_of_the_Wild 其实就用曼哈顿也能做，可以先横着做一遍一维前缀和，求答案时每一行要加两个值，然后发现要加的值呈四条斜线，再分别斜着做前缀和即可

| 下一页