备战蓝桥杯国赛【Day 4】

前置知识速查如果你还不熟悉差分数组记住这两个公式一维区间[l,r]加x→diff[l]x,diff[r1]-x二维子矩阵(x1,y1)到(x2,y2)加x→ 四角容斥左上, 右上-, 左下-, 右下例题 1区间更新蓝桥云课 P3291项目内容链接https://www.lanqiao.cn/problems/3291/learning/时间限制1s空间限制256MB数据范围n,m 10^5多组数据题目描述给定长度为n的数组a[1..n]执行m次操作。每次操作给定x,y,z将下标x到y包含的所有元素加上z。最后输出整个数组。输入格式n m a[1] a[2] ... a[n] x1 y1 z1 x2 y2 z2 ... xm ym zm输出格式一行n个整数表示最终数组。样例输入5 2 1 3 5 6 7 2 4 5 1 3 2输出3 10 12 13 9解题思路暴力做法每次操作遍历[x,y]区间时间复杂度O(m×n)会TLE。差分优化构建差分数组diff[i] a[i] - a[i-1]每次区间修改转化为两个单点修改O(1)最后前缀和还原O(n)总复杂度O(n m)完整代码whileTrue:try:n,mmap(int,input().split())alist(map(int,input().split()))# 差分数组 前端、后端1 操作diff[0]*(n1)diff[0]a[0]foriinrange(1,n):diff[i]a[i]-a[i-1]# 进行m次操作for_inrange(m):x,y,zmap(int,input().split())x-1diff[x]z diff[y]-z# 先对起始点更新a[0]diff[0]foriinrange(1,n):a[i]a[i-1]diff[i]print( .join(map(str,a)))except:break关键细节注意点说明0-based转换题目是1-based代码中用0-based更方便diff多开一位diff[n]作为哨兵防止y1越界快读sys.stdin.read()处理多组大数据避免TLE例题 2航班预订统计LeetCode 1109项目内容链接https://leetcode.cn/problems/corporate-flight-bookings/难度 简单标签数组、差分、前缀和题目描述有n个航班编号1到n。给定bookings[i] [first_i, last_i, seats_i]表示预订从first_i到last_i包含的每个航班seats_i个座位。返回长度为n的数组第i个元素表示航班i预订的座位总数。样例输入bookings [[1,2,10],[2,3,20],[2,5,25]], n 5输出[10, 55, 45, 25, 25]解题思路航班编号从1开始数组下标从0开始需要-1转换。diff长度设为n1diff[n]作为哨兵处理last n的情况。完整代码fromtypingimportListclassSolution:defcorpFlightBookings(self,bookings:List[List[int]],n:int)-List[int]:# diff[i] 表示第 i 个航班相比前一个航班的座位增量diff[0]*(n1)# 多开一位diff[n]是哨兵forfirst,last,seatsinbookings:# 航班编号从1开始转0-baseddiff[first-1]seats# 区间起点从此处开始增加diff[last]-seats# 区间终点后一位从此处抵消# 前缀和还原求每个航班的实际座位数res[0]*n res[0]diff[0]foriinrange(1,n):res[i]res[i-1]diff[i]returnres复杂度分析指标复杂度说明时间O(n m)m为 bookings 数量一次遍历修改 一次前缀和空间O(n)diff 数组 结果数组推演验证bookings [[1,2,10], [2,3,20], [2,5,25]], n5 初始: diff [0, 0, 0, 0, 0, 0] 操作 [1,2,10]: diff[0] 10 → [10, 0, 0, 0, 0, 0] diff[2] - 10 → [10, 0, -10, 0, 0, 0] 操作 [2,3,20]: diff[1] 20 → [10, 20, -10, 0, 0, 0] diff[3] - 20 → [10, 20, -10, -20, 0, 0] 操作 [2,5,25]: diff[1] 25 → [10, 45, -10, -20, 0, 0] diff[5] - 25 → [10, 45, -10, -20, 0, -25] 前缀和还原: res[0] 10 res[1] 10 45 55 res[2] 55 (-10) 45 res[3] 45 (-20) 25 res[4] 25 0 25 结果: [10, 55, 45, 25, 25] ✓同类对比题目与本题区别例题1区间更新需要处理多组输入初始数组非零拼车LC1094区间是左闭右开需要边还原边判断例题 3拼车LeetCode 1094项目内容链接https://leetcode.cn/problems/car-pooling/难度 中等标签数组、差分、排序题目描述车上有capacity个空座位只能单向行驶。trips[i] [numPassengers_i, from_i, to_i]表示在from_i接上numPassengers_i人在to_i放下。判断能否在不超载的情况下完成所有行程。样例输入trips [[2,1,5],[3,3,7]], capacity 4输出false解释在位置3时车上有 235 人超过容量4。解题思路关键细节区间是左闭右开[from, to)乘客在to位置已经下车所以diff[to] - num。优化数据范围0 from_i to_i 1000可以直接开大小为1001的数组。边还原边判断不需要存储完整结果。完整代码fromtypingimportListclassSolution:defcarPooling(self,trips:List[List[int]],capacity:int)-bool:# 根据数据范围最大位置是1000diff[0]*1001fornum,from_i,to_iintrips:diff[from_i]num# 上车diff[to_i]-num# 下车开区间to位置已下车# 求前缀和模拟每个位置车上的人数current0foriinrange(1001):currentdiff[i]# current 表示位置 i 时车上的人数ifcurrentcapacity:returnFalsereturnTrue复杂度分析指标复杂度说明时间O(max_location len(trips))max_location 1000空间O(max_location)固定1001大小推演验证trips [[2,1,5], [3,3,7]], capacity 4 diff 数组变化只显示非零位置: 位置: 0 1 2 3 4 5 6 7 diff: 0 2 0 3 0 -2 0 -3 模拟过程: i0: current 0 0 0, 0 4 ✓ i1: current 0 2 2, 2 4 ✓ i2: current 2 0 2, 2 4 ✓ i3: current 2 3 5, 5 4 ✗ → 返回 False关键易错点错误写法正确写法原因diff[to_i 1] - numdiff[to_i] - num区间是左闭右开to_i位置已经下车先还原整个数组再判断边还原边判断可以提前返回且节省空间例题 4差分矩阵AcWing 798项目内容链接https://www.acwing.com/problem/content/800/难度 中等标签二维差分、前缀和题目描述输入一个n行m列的整数矩阵再输入q个操作每个操作包含五个整数x1, y1, x2, y2, c表示将子矩阵(x1,y1)到(x2,y2)内的所有元素加上c。输出最终矩阵。输入格式n m q a[1][1] a[1][2] ... a[1][m] ... a[n][1] a[n][2] ... a[n][m] x1 y1 x2 y2 c ...输出格式n行每行m个整数。样例输入3 4 3 1 2 2 1 3 2 2 1 1 1 1 1 1 1 2 2 1 1 3 2 3 2 3 1 3 4 1输出2 3 4 1 4 3 4 1 2 2 2 2解题思路二维差分模板题。核心公式构建二维差分diff[i][j] a[i][j] - a[i-1][j] - a[i][j-1] a[i-1][j-1]子矩阵修改(x1,y1)到(x2,y2)加cdiff[x1][y1] c diff[x1][y21] - c diff[x21][y1] - c diff[x21][y21] c二维前缀和还原a[i][j] a[i-1][j] a[i][j-1] - a[i-1][j-1] diff[i][j]完整代码defsolve():n,m,qmap(int,input().split())# 下标从1开始多开一圈防止越界a[[0]*(m2)for_inrange(n2)]diff[[0]*(m2)for_inrange(n2)]# 读入矩阵foriinrange(1,n1):rowlist(map(int,input().split()))forjinrange(1,m1):a[i][j]row[j-1]# 构建二维差分数组foriinrange(1,n1):forjinrange(1,m1):diff[i][j]a[i][j]-a[i-1][j]-a[i][j-1]a[i-1][j-1]# q次操作for_inrange(q):x1,y1,x2,y2,cmap(int,input().split())diff[x1][y1]c diff[x1][y21]-c diff[x21][y1]-c diff[x21][y21]c# 二维前缀和还原同时输出foriinrange(1,n1):forjinrange(1,m1):diff[i][j]diff[i-1][j]diff[i][j-1]-diff[i-1][j-1]print(diff[i][j],end )print()solve()复杂度分析指标复杂度说明时间O(n×m q)构建差分O(nm) q次操作O(q) 还原O(nm)空间O(n×m)两个(n2)×(m2)的二维数组推演验证初始矩阵a1 2 2 1 3 2 2 1 1 1 1 1操作1(1,1)到(2,2)加 1操作2(1,3)到(2,3)加 2操作3(3,1)到(3,4)加 1diff 构建过程初始 diff构建后: i1: [0, 1, 1, 0, -1] (1-0-001, 2-0-101, 2-0-101, 1-0-20-1) i2: [0, 2, 0, 0, -1] (3-1-002, 2-1-111? 需要重新算...) 详细计算 diff[i][j] a[i][j] - a[i-1][j] - a[i][j-1] a[i-1][j-1]: diff[1][1] 1-0-00 1 diff[1][2] 2-0-10 1 diff[1][3] 2-0-20 0 diff[1][4] 1-0-20 -1 diff[2][1] 3-1-00 2 diff[2][2] 2-2-31 -2? 不对a[2][2]2, a[1][2]2, a[2][1]3, a[1][1]1 2 - 2 - 3 1 -2 diff[2][3] 2-2-22 0 diff[2][4] 1-1-22 0 diff[3][1] 1-3-00 -2 diff[3][2] 1-2-13 1 diff[3][3] 1-2-12 0 diff[3][4] 1-1-12 1操作后的 diff操作1 (1,1)-(2,2)1: diff[1][1]1, diff[1][3]-1, diff[3][1]-1, diff[3][3]1 操作2 (1,3)-(2,3)2: diff[1][3]2, diff[1][4]-2, diff[3][3]-2, diff[3][4]2 操作3 (3,1)-(3,4)1: diff[3][1]1, diff[3][5]-1(越界忽略), diff[4][1]-1, diff[4][5]1由于手算较复杂直接信任代码输出与样例一致[2,3,4,1], [4,3,4,1], [2,2,2,2]关键易错点错误正确后果下标从0开始下标从1开始边界判断复杂容易越界数组大小n×m数组大小(n2)×(m2)x21或y21越界还原时修改原数组a还原时修改diff自身如果还需要原数组会丢失数据例题 5字母移位 IILeetCode 2381项目内容链接https://leetcode.cn/problems/shifting-letters-ii/难度 中等标签差分、字符串、前缀和题目描述给定字符串s下标从0开始和shifts[i] [start, end, direction]direction 1字母向后移1位a→b,z→adirection 0字母向前移1位b→a,a→z返回所有操作后的字符串。样例输入s abc, shifts [[0,1,0],[1,2,1],[0,2,1]]输出ace解题思路差分记录偏移量不是直接改字符最后统一计算。注意后移 1前移 -1最终偏移可能很大对26取模负数取模((num % 26) 26) % 26或直接num % 26Python支持负数取模完整代码fromtypingimportListclassSolution:defshiftingLetters(self,s:str,shifts:List[List[int]])-str:nlen(s)diff[0]*(n1)# 差分数组记录偏移量forstart,end,directioninshifts:delta1ifdirection1else-1diff[start]delta diff[end1]-delta# 前缀和得到每个位置的实际偏移再计算字符res[]offset0foriinrange(n):offsetdiff[i]# 计算新字符# ord(s[i]) - ord(a) 得到 0-25 的数字# 加上偏移对26取模再转回字符num(ord(s[i])-ord(a)offset)%26res.append(chr(numord(a)))return.join(res)复杂度分析指标复杂度说明时间O(n m)m为 shifts 数量空间O(n)diff 数组 结果字符串推演验证s abc, shifts [[0,1,0],[1,2,1],[0,2,1]] 初始: diff [0, 0, 0, 0] 操作1 [0,1,0] (前移, delta-1): diff[0] -1 → -1 diff[2] - -1 → 1 diff: [-1, 0, 1, 0] 操作2 [1,2,1] (后移, delta1): diff[1] 1 → 1 diff[3] - 1 → -1 diff: [-1, 1, 1, -1] 操作3 [0,2,1] (后移, delta1): diff[0] 1 → 0 diff[3] - 1 → -2 diff: [0, 1, 1, -2] 前缀和求偏移: i0: offset 0, a 0 a i1: offset 0 1 1, b 1 c i2: offset 1 1 2, c 2 e (c→d→e) 结果: ace ✓关键易错点错误正确后果直接修改字符先存偏移量再统一计算多次操作叠加时逻辑混乱diff[end] - deltadiff[end 1] - delta区间闭合错误忽略负数取模(x % 26 26) % 26Python中%26对负数也有效但其他语言需注意 今日心得差分的本质是记录变化量不存绝对值存增量最后统一求和二维差分记住四角公式左上、右上-、左下-、右下本质是容斥下标从1开始能救命二维问题中下标从1开始可以避免大量边界判断多开一圈数组一维多开1位二维多开1圈防止r1越界