科学计算【免费下载链接】codeforces-go算法竞赛模板库 by 灵茶山艾府 项目地址https://gitcode.com/GitHub_Trending/co/codeforces-go点击查看免费下载本篇技术指南以 codeforces-go 仓库中 1878.md 题解文档为核心深入剖析 LeetCode 1878「网格中最大的三个菱形和」的完整解法如何用两个变量唯一刻画菱形、如何用 ↘ / ↙ 两类斜向前缀和在 O(1) 内求任意斜线段和、如何枚举所有中心与半径并维护前三大的不同菱形和。读者学完后将掌握一套可复用的「斜向前缀和」模板思路并能将其迁移到幻方、菱形区域和等一类网格斜线求和问题中。问题背景菱形和是什么LeetCode 1878Biweekly Contest 53 C 题要求给定m × n网格grid菱形由四个顶点连线构成其边平行于网格的两条对角线方向。定义「菱形和」为菱形四条边所覆盖格子上的元素之和。题目要求返回网格中前三个不同且最大的菱形和若不足三个则按实际数量返回结果按降序排列。本题的菱形定义有一个细节容易忽略单个格子也视作菱形即半径为 0 的退化菱形因此单元素和也应参与前三大的竞争。仓库中的 Go 实现 c.go 与题解文档一致在枚举每个格子作为中心时先执行update(v)一个数也算菱形再枚举更大的半径。核心建模描述一个菱形需要几个变量原文档核心提问如何枚举菱形描述一个菱形需要几个变量菱形完全由两个参数决定正中心坐标(i, j)顶点到正中心的距离k即曼哈顿距离菱形的四个顶点分别位于中心的上下左右 k 格处。例如题解文档中给出的示意图蓝色菱形正中心在(1, 1)顶点到中心的距离为 1四个顶点分别在(1, 0)、(0, 1)、(1, 2)、(2, 1)。于是枚举所有菱形等价于枚举所有格子作为正中心(i, j)枚举半径k且保证四个顶点不越界i-k 0、ik m-1、j-k 0、jk n-1即k min(i, m-1-i, j, n-1-j)。mx : min(i, m-1-i, j, n-1-j) for k : 1; k mx; k { // 用斜向前缀和快速求出四条边的和 }每个中心的可行半径上限由它到矩阵四条边的最短距离决定这个上界正是上述min表达式见 c.go。加速工具两条对角方向上的斜向前缀和四条边都是沿对角线方向的斜线段直接累加会使总复杂度上升到 O(mn·min(m,n)²)。解决办法是斜向前缀和diagSum[i1][j1]从矩阵最上边或最左边出发向右下 ↘ 到(i, j)的线段元素和antiSum[i1][j]从矩阵最上边或最右边出发向左下 ↙ 到(i, j)的线段元素和。两类前缀和的递推式仅有一条之差非常对称diagSum[i1][j1] diagSum[i][j] v // 继承左上角 antiSum[i1][j] antiSum[i][j1] v // 继承右上角关于 1 下标的说明数组多开一圈(m1) × (n1)让下标从 1 开始边界上留出全 0 的哨兵行/列查询时就可以像一维前缀和那样用两个前缀和之差直接得到任意斜线段和而无需特判起点是否在矩阵边上。这正是「前缀和及其扩展」系列中强调的核心技巧即使所求线段就是前缀本身也可统一用pre[r] - pre[l]计算。任意斜线段的 O(1) 查询设queryDiagonal(x, y, k)表示从(x, y)出发向右下 ↘ 连续k个数的和queryAntiDiagonal(x, y, k)表示从(x, y)出发向左下 ↙ 连续k个数的和queryDiagonal : func(x, y, k int) int { return diagSum[xk][yk] - diagSum[x][y] } queryAntiDiagonal : func(x, y, k int) int { return antiSum[xk][y1-k] - antiSum[x][y1] }queryAntiDiagonal中y1与y1-k的偏移值得仔细体会↙ 方向的线段起点在上方偏右落点在下方偏左坐标变换正好是y方向按k递减因此以y1为右哨兵、y1-k为左边界做前缀差。四条边如何拼成一个菱形以中心(i, j)、半径k的菱形为例四条边分别是a queryDiagonal(i-k, j, k)右上边从顶点(i-k, j)向右下走 k 格b queryDiagonal(i, j-k, k)左下边从左顶点(i, j-k)向右下走 k 格c queryAntiDiagonal(i-k1, j-1, k-1)左上边长度是 k-1右上顶点下方一格起向左下走d queryAntiDiagonal(i, jk, k1)右下边从右顶点(i, jk)向左下走 k1 格。为什么c的长度是k-1、d的长度是k1因为菱形四个顶点分别被 a、b 两条 ↘ 边各覆盖一次若 c、d 都取长度 k 会重复统计顶点。交错取k-1与k1恰好让四条边首尾衔接、每个格子恰好被统计一次。完整拼接a : queryDiagonal(i-k, j, k) // 菱形右上的边 b : queryDiagonal(i, j-k, k) // 菱形左下的边 c : queryAntiDiagonal(i-k1, j-1, k-1) // 菱形左上的边 d : queryAntiDiagonal(i, jk, k1) // 菱形右下的边 update(a b c d)对应代码见 c.go。维护前三大的菱形和滚动更新题目要求的是不同的前三大和且存在菱形和不足三个的情形。实现上用三个变量x, y, z分别保存最大、次大、第三大用update在严格大于/严格小于的判断下滚动更新update : func(v int) { if v x { x, y, z v, x, y } else if v x v y { y, z v, y } else if v y v z { z v } }这里刻意使用v x而非v x从而保证三个值互不相同等值不更新输出前再从尾部弹出值为 0 的占位项得到实际个数ans : []int{x, y, z} for ans[len(ans)-1] 0 { // 不同的和少于三个 ans ans[:len(ans)-1] } return ansJava 与 C 版本的区别仅在于update的分支写法C 用min({...})计算半径上界核心逻辑完全一致见 1878.md。复杂度分析时间复杂度O(mn·min(m, n))。枚举每个中心是 O(mn)每个中心枚举的半径数至多为min(m, n)/2每次查询四条边均为 O(1)空间复杂度O(mn)即两张(m1) × (n1)的斜向前缀和表。仓库配套测试与通用模板仓库内的测试用例仓库为本题配套了 c_test.go由copypasta/template/leetcode/generator_test.go自动生成包含三组数据输入网格期望输出覆盖点5×5 网格[[3,4,5,1,3],...][228,216,211]常规情况三个菱形和齐全3×3 网格[[1,2,3],[4,5,6],[7,8,9]][20,9,8]最大菱形和为 20次大为单元素 9、81×3 网格[[7,7,7]][7]不同菱形和不足三个时的收尾逻辑第三组用例尤其值得注意单元素同样计入菱形而7出现多次但值相同最终只保留一个。测试通过testutil.RunLeetCodeFuncWithExamples实现在 leetcode/testutil/leetcode.go驱动先用反射将字符串用例解析为[][]int参数再逐例调用getBiggestThree比对输出targetCaseNum为 0 时还会做超时检测。菱形区域和的另一条路径45° 坐标旋转仓库 copypasta/common.go 中还收录了一个「菱形曼哈顿距离区域和」的通用模板rhombusSum思路是把整个矩阵顺时针旋转 45°坐标映射(x, y) → (xy, y-xn-1)使原菱形区域变成旋转后坐标系下的正方形区域再套用标准二维前缀和模板见 copypasta/common.go查询。它的注释中还标注了本题的扩展思考CF 1301E 2500 分题目「如果是菱形该怎么做」适合学完本题后继续深挖。这两种思路互为印证1878 的解法面向菱形边框和只算四条边而rhombusSum面向菱形填充和整个内部区域。若题目改为求菱形内部区域和可直接复用rhombusSum模板。相似题目与延伸练习1895. 最大的幻方同样在网格中枚举带方向的子结构并校验行列、对角线之和可加深对对角线/前缀和枚举的理解CF 1301E2500菱形区域和的扩展题对应仓库 copypasta/common.go 中标注的思考更多前缀和与网格图综合题目可参考仓库在 copypasta/common.go 中整理的题单LC304、洛谷 P2004、CF 611C、835C、1731D、1107D、2044H 等。小结回顾整条解题链两个变量(中心, 半径)唯一刻画菱形 → 两张斜向前缀表把斜线段求和降到 O(1) → 四条边按k-1 / k1交错拼接避免重复统计 → 滚动三变量维护不同前三大。整套方法的时间复杂度为 O(mn·min(m,n))在m, n ≤ 50的题目约束下绰绰有余。仓库中的 Go 实现 c.go 与题解文档 1878.md 完全对应配合 c_test.go 可以直接本地运行验证。赞分享科学计算【免费下载链接】codeforces-go算法竞赛模板库 by 灵茶山艾府 项目地址https://gitcode.com/GitHub_Trending/co/codeforces-go点击查看免费下载相关推荐codeforces-go 题解精讲枚举中间 前后缀分解求解放置三车最大价值LeetCode 双周赛 137 Dcodeforces go 题解精讲枚举中间 前后缀分解求解放置三车最大价值LeetCode 双周赛 137 D 本篇技术指南以 leetcode/b科学计算从枚举选哪个到前缀和优化codeforces-go 详解 LeetCode 双周赛 133 逆序对计数问题LC 3193从枚举选哪个到前缀和优化codeforces go 详解 LeetCode 双周赛 133 逆序对计数问题LC 3193 本文以 LeetCode 第 1科学计算codeforces-go 题解精讲LeetCode 第 118 场双周赛 B 题「最大化网格正方形洞的面积」—— 贪心与最长连续序列codeforces go 题解精讲LeetCode 第 118 场双周赛 B 题「最大化网格正方形洞的面积」—— 贪心与最长连续序列 本篇技术指南以 cod科学计算上一篇AMD Ryzen处理器深度调试指南免费开源工具SMUDebugTool完全教程下一篇如何快速批量下载抖音视频终极自动化工具指南创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考