写在前面今天的4道题全部来自第十四届蓝桥杯省赛真题难度覆盖 ⭐⭐ 到 ⭐⭐⭐⭐⭐是检验省赛备战成果的绝佳素材。核心考点包括前缀和优化枚举、单调队列维护区间最值、二维差分处理矩阵变换、按位独立统计。每道题我都会从暴力为何超时讲起一步步推导到最优解确保你不仅懂代码更懂思维路径。 今日刷题清单题号题目来源类型难度核心考点1子串简写蓝桥杯3514前缀和⭐⭐⭐贡献法思想、前缀和优化2最大子矩阵蓝桥杯2147单调队列枚举⭐⭐⭐⭐二维转一维、滑动窗口最值3闪耀的灯光蓝桥杯3811二维前缀和⭐⭐⭐⭐矩阵变换、差分思想4异或和之和蓝桥杯3507位运算组合数学⭐⭐⭐⭐⭐按位独立、贡献法、O(n)优化一、子串简写 ⭐⭐⭐1.1 题目描述程序猿圈子里流行一种简写只保留首尾字符中间用长度代替如internationalization→i18n。给定字符串S、整数K、字符c1和c2。求有多少个以 c1 开头、c2 结尾、长度 ≥ K的子串可以采用这种简写。输入KS c1 c2空格分隔输出满足条件的子串个数1.2 关键思路贡献法 前缀和暴力思路O(n²)枚举所有子串检查首尾字符和长度。超时原因|S| ≤ 5×10⁵子串数量是 O(n²) 级别。优化思路——贡献法对于每个位置i上的c2它能和前面多少个c1组成合法子串条件i - j 1 ≥ K→j ≤ i - K 1即位置i的c2的贡献 区间[0, i-K1]内c1的出现次数前缀和维护用pre[i]表示前i个字符中c1的出现次数O(1) 查询区间和。1.3 推演验证输入: K4, Sabababdb, c1a, c2b 索引: 0 1 2 3 4 5 6 7 字符: a b a b a b d b pre数组c1a的个数: pre[0]1 (a) pre[1]1 (b不是a) pre[2]2 (a) pre[3]2 (b) pre[4]3 (a) pre[5]3 (b) pre[6]3 (d) pre[7]3 (b) 遍历每个c2的位置 i1 (b): i-K1 1-41 -2 → max(0,-2)0, 贡献pre[0]1 ✓ 子串[0,1]ab 长度24? 等等这里要注意长度≥K即i-j1≥K → j≤i-K1 重新计算 i1: j≤1-41-2没有合法j贡献0 i3: j≤3-410pre[0]1贡献1 → abab [0,3] i5: j≤5-412pre[2]2贡献2 → ababab[0,5], babab[1,5]? 不对c1必须在开头 应该是j0(ababab), j2(babab? 开头是b不是a) 等等pre[2]2表示位置0和2都是a所以 j0: [0,5]ababab 长度6≥4 ✓ j2: [2,5]abab 长度4≥4 ✓ 贡献确实是2 i7: j≤7-414pre[4]3贡献3 j0: [0,7]abababdb 长度8 ✓ j2: [2,7]ababdb 长度6 ✓ j4: [4,7]abdb 长度4 ✓ 总贡献 0123 6 ✓1.4 题解importsysinputsys.stdin.readline kint(input())s,a,binput().split()nlen(s)# pre[i] 前i个字符中字符a出现的次数前缀和pre[0]*n ans0foriinrange(n):# 继承前一个值pre[i]pre[i-1]ifi0else0# 当前是c1计数1ifs[i]a:pre[i]1# 当前是c2计算贡献# 需要找开头c1的位置j满足 i-j1 k → j i-k1elifs[i]bandi-k10:# pre[i-k1] 就是区间[0, i-k1]内c1的个数anspre[i-k1]print(ans)复杂度时间O(n)空间O(n)可优化至O(1)1.5 关键细节坑点说明下标越界i-k1可能为负数必须判断i-k1 0pre[i-1] 越界i0时不能访问pre[-1]Python中-1是最后一个元素字符读取input().split()读取注意字符串中可能有空格不题目说只含小写字母答案类型答案可能很大要用long longPython自动处理二、最大子矩阵 ⭐⭐⭐⭐2.1 题目描述给定n×m矩阵定义子矩阵的稳定度 子矩阵中最大值 - 最小值。求稳定度≤ limit的所有子矩阵中面积最大是多少。2.2 关键思路二维转一维 滑动窗口暴力思路O(n²m²)枚举上下左右四个边界再遍历求最值。超时原因n,m可能到几百四重循环无法接受。优化思路枚举上下边界固定子矩阵的上边top和下边bottom将问题压缩成一维列最值数组对于每一列j计算col_min[j] min(a[top..bottom][j])col_max[j] max(a[top..bottom][j])一维问题转化现在问题变成——在数组col_min和col_max上找最长的连续子数组使得max(col_max) - min(col_min) ≤ limit滑动窗口单调队列用双指针维护窗口窗口内需要快速知道最大值和最小值 →单调队列单调队列作用maxx队列维护窗口内最大值队首是最大值minn队列维护窗口内最小值队首是最小值窗口右移时加入新元素左移时弹出过期元素均摊 O(1)2.3 推演验证输入: n2, m3, limit1 矩阵: 1 2 3 2 3 4 枚举 top0, bottom0第一行: col_min [1, 2, 3], col_max [1, 2, 3] 滑动窗口 right0: [1], max1,min1,diff0≤1, 面积1×11 right1: [1,2], max2,min1,diff1≤1, 面积1×22 right2: [1,2,3], max3,min1,diff21, 收缩left left0弹出1: [2,3], diff1≤1, 面积1×22 left1弹出2: [3], diff0≤1, 面积1×11 枚举 top0, bottom1两行合并: col_min [1, 2, 3], col_max [2, 3, 4] right0: [1], max2,min1,diff1≤1, 面积2×12 right1: [1,2], max3,min1,diff21, 收缩 left0: [2], max3,min2,diff1≤1, 面积2×12 再收缩? diff已经≤1了 等等窗口是[0,1]left0时弹出1窗口变[1]即只有2 max3,min2,diff1, 面积2×12 right2: [2,3], max4,min2,diff21, 收缩 left1弹出2: [3], max4,min3,diff1, 面积2×12 最大面积 22.4 题解fromcollectionsimportdeque n,mmap(int,input().split())a[]for_inrange(n):rowlist(map(int,input().split()))a.append(row)limitint(input())ans0# 枚举上下边界fortopinrange(n):# 初始化每列的最小值和最大值col_min[float(inf)]*m col_max[float(-inf)]*mforbottominrange(top,n):# 更新每列的最值随着bottom下移forjinrange(m):col_min[j]min(col_min[j],a[bottom][j])col_max[j]max(col_max[j],a[bottom][j])# 现在问题变成在col_min和col_max上找最长子数组# 使得 max(col_max[l..r]) - min(col_min[l..r]) limit# 滑动窗口 单调队列left0min_qdeque()# 维护最小值存 (值, 索引)max_qdeque()# 维护最大值存 (值, 索引)forrightinrange(m):# 维护最小值队列单调递增whilemin_qandmin_q[-1][0]col_min[right]:min_q.pop()min_q.append((col_min[right],right))# 维护最大值队列单调递减whilemax_qandmax_q[-1][0]col_max[right]:max_q.pop()max_q.append((col_max[right],right))# 收缩左边界直到满足条件whileleftright:# 清理过期的队首元素whilemin_qandmin_q[0][1]left:min_q.popleft()whilemax_qandmax_q[0][1]left:max_q.popleft()current_diffmax_q[0][0]-min_q[0][0]ifcurrent_difflimit:break# 满足条件停止收缩# 不满足收缩左边界left1# 计算当前合法窗口的面积# 高度 bottom - top 1, 宽度 right - left 1area(bottom-top1)*(right-left1)ansmax(ans,area)print(ans)复杂度时间O(n² × m)空间O(m)2.5 关键细节坑点说明单调队列实现Python用deque队首弹出过期元素队尾维护单调性过期元素清理左边界右移时要弹出索引 left的元素窗口收缩逻辑先加入right再收缩left直到满足条件面积计算时机每次right扩展后都要计算因为窗口可能已经合法初始值设置col_min初始infcol_max初始-inf感谢提供完整题目现在我来更新闪耀的灯光的题解。这道题的核心是每次操作独立基于初始状态计算而不是累积修改。让我重新分析三、闪耀的灯光 ⭐⭐⭐⭐3.1 题目描述蓝桥公园有n×m盏灯初始亮度为a[i][j]。每盏灯有一个开关按一次亮度-1亮度最低降到a[i][j] - c如果当前亮度已经是a[i][j] - c再按一次会恢复为a[i][j]即每盏灯的亮度在a[i][j], a[i][j]-1, ..., a[i][j]-c这c1个值之间循环。进行t次操作每次选择一个子矩阵将该区域内每盏灯按k次开关。每次操作前所有灯恢复初始值。求每次操作后该子矩阵内所有灯的总亮度。数据范围n,m ≤ 300t ≤ 10⁵k ≤ 10⁹3.2 关键思路周期取模 二维前缀和核心观察每盏灯的亮度变化周期为c1按c1次回到原值按k次等价于按k % (c1)次设k k % (c1)则每盏灯亮度变化为-k但如果初始亮度不够减会循环等等重新理解循环灯的状态序列a[i][j] → a[i][j]-1 → ... → a[i][j]-c → a[i][j] → ...按k次后亮度 a[i][j] - (k % (c1))但如果结果为负数则加c1不对题目说数据保证每盏灯的亮度不会减少至负数且a[i][j] ≥ 10c ≤ 10所以a[i][j]-c ≥ 0更准确地按k次后亮度 a[i][j] - k其中k k % (c1)且a[i][j] - k ≥ a[i][j] - c因为k ≤ c。所以每盏灯按 k 次后亮度 a[i][j] - k % (c1)子矩阵总亮度设k k % (c1)num (x2-x11) × (y2-y11)为子矩阵格子数总亮度 Σ(a[i][j] - k)Σa[i][j] - num × kΣa[i][j]用二维前缀和 O(1) 求3.3 推演验证输入: n3, m3, c3 矩阵: 14 14 17 13 15 18 13 16 19 t3 操作1: x11,y11,x22,y22, k3 k 3 % 4 3 num 2×2 4 子矩阵和 14141315 56 总亮度 56 - 4×3 56 - 12 44 ✓ 操作2: x12,y12,x23,y23, k5 k 5 % 4 1 num 2×2 4 子矩阵和 15181619 68 总亮度 68 - 4×1 68 - 4 64 ✓ 操作3: x12,y13,x23,y23, k4 k 4 % 4 0 num 2×1 2 子矩阵和 1819 37 总亮度 37 - 2×0 37 ✓3.4 题解importsysinputsys.stdin.readline n,m,cmap(int,input().split())# 构建矩阵下标从1开始方便前缀和a[[0]*(m1)]for_inrange(n):row[0]list(map(int,input().split()))a.append(row)# 二维前缀和: pre_sum[i][j] 矩形(1,1)到(i,j)的元素和pre_sum[[0]*(m1)for_inrange(n1)]foriinrange(1,n1):forjinrange(1,m1):pre_sum[i][j](pre_sum[i-1][j]pre_sum[i][j-1]-pre_sum[i-1][j-1]a[i][j])tint(input())for_inrange(t):x1,y1,x2,y2,kmap(int,input().split())# k对周期(c1)取模因为按c1次等于没按kk%(c1)# 子矩阵格子数num(y2-y11)*(x2-x11)# 用二维前缀和求子矩阵原始亮度之和# 公式: sum(x1,y1到x2,y2) pre[x2][y2] - pre[x1-1][y2] - pre[x2][y1-1] pre[x1-1][y1-1]sub_sum(pre_sum[x2][y2]-pre_sum[x1-1][y2]-pre_sum[x2][y1-1]pre_sum[x1-1][y1-1])# 每盏灯减少k总共减少 num*kanssub_sum-num*kprint(ans)复杂度预处理O(n × m)每次查询O(1)总复杂度O(n × m t)3.5 关键细节坑点说明k % (c1)周期是c1不是c按c1次回到原值下标从1开始输入坐标就是1-indexed直接用不用转换二维前缀和公式pre[x2][y2] - pre[x1-1][y2] - pre[x2][y1-1] pre[x1-1][y1-1]符号别搞错“恢复初始值”每次操作独立不用维护修改状态直接用初始矩阵的前缀和t很大t ≤ 10⁵必须 O(1) 查询预处理前缀和是关键四、异或和之和 ⭐⭐⭐⭐⭐ 按位独立贡献法4.1 题目描述给定数组a求所有子数组的异或和的总和。即对每对1 ≤ L ≤ R ≤ n求a[L] ^ a[L1] ^ ... ^ a[R]把所有结果加起来。4.2 关键思路按位独立贡献法暴力思路O(n²)枚举所有子数组计算异或和累加。超时原因n ≤ 10⁵子数组数量O(n²)需要10¹⁰次操作。优化思路——按位独立异或运算按位独立第k位的结果只和第k位有关对于第k位如果子数组异或结果的第k位是1则贡献2^k到答案问题转化有多少个子数组其异或结果的第 k 位是 1前缀异或pre_xor[i] a[0] ^ a[1] ^ ... ^ a[i]子数组[L,R]的异或 pre_xor[R] ^ pre_xor[L-1]第 k 位为 1 的条件pre_xor[R]和pre_xor[L-1]的第k位不同因为0^11,1^01,0^00,1^10统计方法遍历所有pre_xor值统计第k位为0的个数cnt0为1的个数cnt1子数组数量 cnt0 × cnt1选一个0和一个1配对注意pre_xor数组有n1个元素包含pre_xor[-1]04.3 推演验证输入: n3, a[1, 2, 3] 前缀异或 pre[0] 0 (空前缀) pre[1] 1 01 pre[2] 1^2 3 11 pre[3] 3^3 0 00 所有子数组异或 [1]: 1 01 [2]: 2 10 [3]: 3 11 [1,2]: 1^2 3 11 [2,3]: 2^3 1 01 [1,2,3]: 1^2^3 0 00 总和 123310 10 按位计算 第0位1 pre中第0位: 0(0), 1(1), 3(1), 0(0) → cnt02, cnt12 贡献 2×2×1 4 第1位2 pre中第1位: 0(0), 1(0), 3(1), 0(0) → cnt03, cnt11 贡献 3×1×2 6 总和 46 10 ✓ 验证子数组第0位为1的个数 [1]:1 ✓, [2]:0, [3]:1 ✓, [1,2]:1 ✓, [2,3]:1 ✓, [1,2,3]:0 共4个cnt0×cnt14 ✓ 第1位为1的个数 [1]:0, [2]:1 ✓, [3]:1 ✓, [1,2]:1 ✓, [2,3]:0, [1,2,3]:0 共3个cnt0×cnt13? 但算出来是3×13贡献3×26而实际第1位为1的子数组和是 2338? 等等重新算 第1位为1的子数组[2]2, [3]2, [1,2]2第1位是1值是2 贡献 222 6? 不对[2]2(10), [3]3(11), [1,2]3(11) 第1位为1的值2, 2, 2 → 总和6但2338 哦我搞混了。按位独立的意思是 第1位为1则该子数组对总和的贡献包含 2^12。 有多少个子数组第1位为13个。所以贡献 3×26。 实际子数组值2,3,3它们的第1位都是1所以每个都贡献2到总和作为第1位的部分。 总和的第1位部分 222 6 ✓ 加上第0位部分4个子数组第0位为1每个贡献1共4。 总和 64 10 ✓4.4 题解nint(input())alist(map(int,input().split()))# 前缀异或数组pre_xor[i] a[0]^a[1]^...^a[i-1]# pre_xor[0] 0 表示空前缀pre_xor[0]*(n1)foriinrange(n):pre_xor[i1]pre_xor[i]^a[i]# 最多21位因为 a[i] ≤ 2^20MAX_BIT21ans0forkinrange(MAX_BIT):cnt00# 第k位为0的前缀异或个数cnt10# 第k位为1的前缀异或个数fornuminpre_xor:if(numk)1:cnt11else:cnt01# 第k位的总贡献 配对数 × 该位的权值# 0和1配对异或结果为1anscnt0*cnt1*(1k)print(ans)复杂度时间O(21 × n)空间O(n)可优化至O(1)4.5 关键细节坑点说明前缀异或数组大小n1个元素pre_xor[0]0对应空前缀容易漏掉位运算优先级(num k) 1的括号不能省略21位足够根据数据范围a[i] ≤ 2^2021位覆盖所有可能cnt0 cnt1 n1可以用这个验证计数是否正确long long答案可能很大Python自动处理C要开long long4.6 进一步优化空间优化不需要存pre_xor数组可以边读边处理nint(input())alist(map(int,input().split()))MAX_BIT21ans0forkinrange(MAX_BIT):cnt0,cnt11,0# pre_xor[0]0第0位是0所以cnt0初始为1xor_sum0fornumina:xor_sum^numif(xor_sumk)1:cnt11else:cnt01anscnt0*cnt1*(1k)print(ans)这样空间复杂度降到O(1)除了输入数组。 今日复盘总结题目核心技巧思维路径易错点国赛价值子串简写贡献法前缀和枚举右端点统计左端点合法个数下标越界、pre[-1]⭐⭐⭐最大子矩阵二维转一维单调队列枚举上下边界→滑动窗口→维护最值单调队列实现、过期元素⭐⭐⭐⭐闪耀的灯光二维前缀和子矩阵和→容斥公式下标从1开始、公式符号⭐⭐⭐⭐异或和之和按位独立贡献法异或按位独立→0/1配对统计空前缀pre[0]、位运算优先级⭐⭐⭐⭐⭐ 记得点赞收藏算法路上不迷路有问题评论区见
备战蓝桥杯国赛【Day 15】
发布时间：2026/5/18 15:57:40
写在前面今天的4道题全部来自第十四届蓝桥杯省赛真题难度覆盖 ⭐⭐ 到 ⭐⭐⭐⭐⭐是检验省赛备战成果的绝佳素材。核心考点包括前缀和优化枚举、单调队列维护区间最值、二维差分处理矩阵变换、按位独立统计。每道题我都会从暴力为何超时讲起一步步推导到最优解确保你不仅懂代码更懂思维路径。 今日刷题清单题号题目来源类型难度核心考点1子串简写蓝桥杯3514前缀和⭐⭐⭐贡献法思想、前缀和优化2最大子矩阵蓝桥杯2147单调队列枚举⭐⭐⭐⭐二维转一维、滑动窗口最值3闪耀的灯光蓝桥杯3811二维前缀和⭐⭐⭐⭐矩阵变换、差分思想4异或和之和蓝桥杯3507位运算组合数学⭐⭐⭐⭐⭐按位独立、贡献法、O(n)优化一、子串简写 ⭐⭐⭐1.1 题目描述程序猿圈子里流行一种简写只保留首尾字符中间用长度代替如internationalization→i18n。给定字符串S、整数K、字符c1和c2。求有多少个以 c1 开头、c2 结尾、长度 ≥ K的子串可以采用这种简写。输入KS c1 c2空格分隔输出满足条件的子串个数1.2 关键思路贡献法 前缀和暴力思路O(n²)枚举所有子串检查首尾字符和长度。超时原因|S| ≤ 5×10⁵子串数量是 O(n²) 级别。优化思路——贡献法对于每个位置i上的c2它能和前面多少个c1组成合法子串条件i - j 1 ≥ K→j ≤ i - K 1即位置i的c2的贡献 区间[0, i-K1]内c1的出现次数前缀和维护用pre[i]表示前i个字符中c1的出现次数O(1) 查询区间和。1.3 推演验证输入: K4, Sabababdb, c1a, c2b 索引: 0 1 2 3 4 5 6 7 字符: a b a b a b d b pre数组c1a的个数: pre[0]1 (a) pre[1]1 (b不是a) pre[2]2 (a) pre[3]2 (b) pre[4]3 (a) pre[5]3 (b) pre[6]3 (d) pre[7]3 (b) 遍历每个c2的位置 i1 (b): i-K1 1-41 -2 → max(0,-2)0, 贡献pre[0]1 ✓ 子串[0,1]ab 长度24? 等等这里要注意长度≥K即i-j1≥K → j≤i-K1 重新计算 i1: j≤1-41-2没有合法j贡献0 i3: j≤3-410pre[0]1贡献1 → abab [0,3] i5: j≤5-412pre[2]2贡献2 → ababab[0,5], babab[1,5]? 不对c1必须在开头 应该是j0(ababab), j2(babab? 开头是b不是a) 等等pre[2]2表示位置0和2都是a所以 j0: [0,5]ababab 长度6≥4 ✓ j2: [2,5]abab 长度4≥4 ✓ 贡献确实是2 i7: j≤7-414pre[4]3贡献3 j0: [0,7]abababdb 长度8 ✓ j2: [2,7]ababdb 长度6 ✓ j4: [4,7]abdb 长度4 ✓ 总贡献 0123 6 ✓1.4 题解importsysinputsys.stdin.readline kint(input())s,a,binput().split()nlen(s)# pre[i] 前i个字符中字符a出现的次数前缀和pre[0]*n ans0foriinrange(n):# 继承前一个值pre[i]pre[i-1]ifi0else0# 当前是c1计数1ifs[i]a:pre[i]1# 当前是c2计算贡献# 需要找开头c1的位置j满足 i-j1 k → j i-k1elifs[i]bandi-k10:# pre[i-k1] 就是区间[0, i-k1]内c1的个数anspre[i-k1]print(ans)复杂度时间O(n)空间O(n)可优化至O(1)1.5 关键细节坑点说明下标越界i-k1可能为负数必须判断i-k1 0pre[i-1] 越界i0时不能访问pre[-1]Python中-1是最后一个元素字符读取input().split()读取注意字符串中可能有空格不题目说只含小写字母答案类型答案可能很大要用long longPython自动处理二、最大子矩阵 ⭐⭐⭐⭐2.1 题目描述给定n×m矩阵定义子矩阵的稳定度 子矩阵中最大值 - 最小值。求稳定度≤ limit的所有子矩阵中面积最大是多少。2.2 关键思路二维转一维 滑动窗口暴力思路O(n²m²)枚举上下左右四个边界再遍历求最值。超时原因n,m可能到几百四重循环无法接受。优化思路枚举上下边界固定子矩阵的上边top和下边bottom将问题压缩成一维列最值数组对于每一列j计算col_min[j] min(a[top..bottom][j])col_max[j] max(a[top..bottom][j])一维问题转化现在问题变成——在数组col_min和col_max上找最长的连续子数组使得max(col_max) - min(col_min) ≤ limit滑动窗口单调队列用双指针维护窗口窗口内需要快速知道最大值和最小值 →单调队列单调队列作用maxx队列维护窗口内最大值队首是最大值minn队列维护窗口内最小值队首是最小值窗口右移时加入新元素左移时弹出过期元素均摊 O(1)2.3 推演验证输入: n2, m3, limit1 矩阵: 1 2 3 2 3 4 枚举 top0, bottom0第一行: col_min [1, 2, 3], col_max [1, 2, 3] 滑动窗口 right0: [1], max1,min1,diff0≤1, 面积1×11 right1: [1,2], max2,min1,diff1≤1, 面积1×22 right2: [1,2,3], max3,min1,diff21, 收缩left left0弹出1: [2,3], diff1≤1, 面积1×22 left1弹出2: [3], diff0≤1, 面积1×11 枚举 top0, bottom1两行合并: col_min [1, 2, 3], col_max [2, 3, 4] right0: [1], max2,min1,diff1≤1, 面积2×12 right1: [1,2], max3,min1,diff21, 收缩 left0: [2], max3,min2,diff1≤1, 面积2×12 再收缩? diff已经≤1了 等等窗口是[0,1]left0时弹出1窗口变[1]即只有2 max3,min2,diff1, 面积2×12 right2: [2,3], max4,min2,diff21, 收缩 left1弹出2: [3], max4,min3,diff1, 面积2×12 最大面积 22.4 题解fromcollectionsimportdeque n,mmap(int,input().split())a[]for_inrange(n):rowlist(map(int,input().split()))a.append(row)limitint(input())ans0# 枚举上下边界fortopinrange(n):# 初始化每列的最小值和最大值col_min[float(inf)]*m col_max[float(-inf)]*mforbottominrange(top,n):# 更新每列的最值随着bottom下移forjinrange(m):col_min[j]min(col_min[j],a[bottom][j])col_max[j]max(col_max[j],a[bottom][j])# 现在问题变成在col_min和col_max上找最长子数组# 使得 max(col_max[l..r]) - min(col_min[l..r]) limit# 滑动窗口 单调队列left0min_qdeque()# 维护最小值存 (值, 索引)max_qdeque()# 维护最大值存 (值, 索引)forrightinrange(m):# 维护最小值队列单调递增whilemin_qandmin_q[-1][0]col_min[right]:min_q.pop()min_q.append((col_min[right],right))# 维护最大值队列单调递减whilemax_qandmax_q[-1][0]col_max[right]:max_q.pop()max_q.append((col_max[right],right))# 收缩左边界直到满足条件whileleftright:# 清理过期的队首元素whilemin_qandmin_q[0][1]left:min_q.popleft()whilemax_qandmax_q[0][1]left:max_q.popleft()current_diffmax_q[0][0]-min_q[0][0]ifcurrent_difflimit:break# 满足条件停止收缩# 不满足收缩左边界left1# 计算当前合法窗口的面积# 高度 bottom - top 1, 宽度 right - left 1area(bottom-top1)*(right-left1)ansmax(ans,area)print(ans)复杂度时间O(n² × m)空间O(m)2.5 关键细节坑点说明单调队列实现Python用deque队首弹出过期元素队尾维护单调性过期元素清理左边界右移时要弹出索引 left的元素窗口收缩逻辑先加入right再收缩left直到满足条件面积计算时机每次right扩展后都要计算因为窗口可能已经合法初始值设置col_min初始infcol_max初始-inf感谢提供完整题目现在我来更新闪耀的灯光的题解。这道题的核心是每次操作独立基于初始状态计算而不是累积修改。让我重新分析三、闪耀的灯光 ⭐⭐⭐⭐3.1 题目描述蓝桥公园有n×m盏灯初始亮度为a[i][j]。每盏灯有一个开关按一次亮度-1亮度最低降到a[i][j] - c如果当前亮度已经是a[i][j] - c再按一次会恢复为a[i][j]即每盏灯的亮度在a[i][j], a[i][j]-1, ..., a[i][j]-c这c1个值之间循环。进行t次操作每次选择一个子矩阵将该区域内每盏灯按k次开关。每次操作前所有灯恢复初始值。求每次操作后该子矩阵内所有灯的总亮度。数据范围n,m ≤ 300t ≤ 10⁵k ≤ 10⁹3.2 关键思路周期取模 二维前缀和核心观察每盏灯的亮度变化周期为c1按c1次回到原值按k次等价于按k % (c1)次设k k % (c1)则每盏灯亮度变化为-k但如果初始亮度不够减会循环等等重新理解循环灯的状态序列a[i][j] → a[i][j]-1 → ... → a[i][j]-c → a[i][j] → ...按k次后亮度 a[i][j] - (k % (c1))但如果结果为负数则加c1不对题目说数据保证每盏灯的亮度不会减少至负数且a[i][j] ≥ 10c ≤ 10所以a[i][j]-c ≥ 0更准确地按k次后亮度 a[i][j] - k其中k k % (c1)且a[i][j] - k ≥ a[i][j] - c因为k ≤ c。所以每盏灯按 k 次后亮度 a[i][j] - k % (c1)子矩阵总亮度设k k % (c1)num (x2-x11) × (y2-y11)为子矩阵格子数总亮度 Σ(a[i][j] - k)Σa[i][j] - num × kΣa[i][j]用二维前缀和 O(1) 求3.3 推演验证输入: n3, m3, c3 矩阵: 14 14 17 13 15 18 13 16 19 t3 操作1: x11,y11,x22,y22, k3 k 3 % 4 3 num 2×2 4 子矩阵和 14141315 56 总亮度 56 - 4×3 56 - 12 44 ✓ 操作2: x12,y12,x23,y23, k5 k 5 % 4 1 num 2×2 4 子矩阵和 15181619 68 总亮度 68 - 4×1 68 - 4 64 ✓ 操作3: x12,y13,x23,y23, k4 k 4 % 4 0 num 2×1 2 子矩阵和 1819 37 总亮度 37 - 2×0 37 ✓3.4 题解importsysinputsys.stdin.readline n,m,cmap(int,input().split())# 构建矩阵下标从1开始方便前缀和a[[0]*(m1)]for_inrange(n):row[0]list(map(int,input().split()))a.append(row)# 二维前缀和: pre_sum[i][j] 矩形(1,1)到(i,j)的元素和pre_sum[[0]*(m1)for_inrange(n1)]foriinrange(1,n1):forjinrange(1,m1):pre_sum[i][j](pre_sum[i-1][j]pre_sum[i][j-1]-pre_sum[i-1][j-1]a[i][j])tint(input())for_inrange(t):x1,y1,x2,y2,kmap(int,input().split())# k对周期(c1)取模因为按c1次等于没按kk%(c1)# 子矩阵格子数num(y2-y11)*(x2-x11)# 用二维前缀和求子矩阵原始亮度之和# 公式: sum(x1,y1到x2,y2) pre[x2][y2] - pre[x1-1][y2] - pre[x2][y1-1] pre[x1-1][y1-1]sub_sum(pre_sum[x2][y2]-pre_sum[x1-1][y2]-pre_sum[x2][y1-1]pre_sum[x1-1][y1-1])# 每盏灯减少k总共减少 num*kanssub_sum-num*kprint(ans)复杂度预处理O(n × m)每次查询O(1)总复杂度O(n × m t)3.5 关键细节坑点说明k % (c1)周期是c1不是c按c1次回到原值下标从1开始输入坐标就是1-indexed直接用不用转换二维前缀和公式pre[x2][y2] - pre[x1-1][y2] - pre[x2][y1-1] pre[x1-1][y1-1]符号别搞错“恢复初始值”每次操作独立不用维护修改状态直接用初始矩阵的前缀和t很大t ≤ 10⁵必须 O(1) 查询预处理前缀和是关键四、异或和之和 ⭐⭐⭐⭐⭐ 按位独立贡献法4.1 题目描述给定数组a求所有子数组的异或和的总和。即对每对1 ≤ L ≤ R ≤ n求a[L] ^ a[L1] ^ ... ^ a[R]把所有结果加起来。4.2 关键思路按位独立贡献法暴力思路O(n²)枚举所有子数组计算异或和累加。超时原因n ≤ 10⁵子数组数量O(n²)需要10¹⁰次操作。优化思路——按位独立异或运算按位独立第k位的结果只和第k位有关对于第k位如果子数组异或结果的第k位是1则贡献2^k到答案问题转化有多少个子数组其异或结果的第 k 位是 1前缀异或pre_xor[i] a[0] ^ a[1] ^ ... ^ a[i]子数组[L,R]的异或 pre_xor[R] ^ pre_xor[L-1]第 k 位为 1 的条件pre_xor[R]和pre_xor[L-1]的第k位不同因为0^11,1^01,0^00,1^10统计方法遍历所有pre_xor值统计第k位为0的个数cnt0为1的个数cnt1子数组数量 cnt0 × cnt1选一个0和一个1配对注意pre_xor数组有n1个元素包含pre_xor[-1]04.3 推演验证输入: n3, a[1, 2, 3] 前缀异或 pre[0] 0 (空前缀) pre[1] 1 01 pre[2] 1^2 3 11 pre[3] 3^3 0 00 所有子数组异或 [1]: 1 01 [2]: 2 10 [3]: 3 11 [1,2]: 1^2 3 11 [2,3]: 2^3 1 01 [1,2,3]: 1^2^3 0 00 总和 123310 10 按位计算 第0位1 pre中第0位: 0(0), 1(1), 3(1), 0(0) → cnt02, cnt12 贡献 2×2×1 4 第1位2 pre中第1位: 0(0), 1(0), 3(1), 0(0) → cnt03, cnt11 贡献 3×1×2 6 总和 46 10 ✓ 验证子数组第0位为1的个数 [1]:1 ✓, [2]:0, [3]:1 ✓, [1,2]:1 ✓, [2,3]:1 ✓, [1,2,3]:0 共4个cnt0×cnt14 ✓ 第1位为1的个数 [1]:0, [2]:1 ✓, [3]:1 ✓, [1,2]:1 ✓, [2,3]:0, [1,2,3]:0 共3个cnt0×cnt13? 但算出来是3×13贡献3×26而实际第1位为1的子数组和是 2338? 等等重新算 第1位为1的子数组[2]2, [3]2, [1,2]2第1位是1值是2 贡献 222 6? 不对[2]2(10), [3]3(11), [1,2]3(11) 第1位为1的值2, 2, 2 → 总和6但2338 哦我搞混了。按位独立的意思是 第1位为1则该子数组对总和的贡献包含 2^12。 有多少个子数组第1位为13个。所以贡献 3×26。 实际子数组值2,3,3它们的第1位都是1所以每个都贡献2到总和作为第1位的部分。 总和的第1位部分 222 6 ✓ 加上第0位部分4个子数组第0位为1每个贡献1共4。 总和 64 10 ✓4.4 题解nint(input())alist(map(int,input().split()))# 前缀异或数组pre_xor[i] a[0]^a[1]^...^a[i-1]# pre_xor[0] 0 表示空前缀pre_xor[0]*(n1)foriinrange(n):pre_xor[i1]pre_xor[i]^a[i]# 最多21位因为 a[i] ≤ 2^20MAX_BIT21ans0forkinrange(MAX_BIT):cnt00# 第k位为0的前缀异或个数cnt10# 第k位为1的前缀异或个数fornuminpre_xor:if(numk)1:cnt11else:cnt01# 第k位的总贡献 配对数 × 该位的权值# 0和1配对异或结果为1anscnt0*cnt1*(1k)print(ans)复杂度时间O(21 × n)空间O(n)可优化至O(1)4.5 关键细节坑点说明前缀异或数组大小n1个元素pre_xor[0]0对应空前缀容易漏掉位运算优先级(num k) 1的括号不能省略21位足够根据数据范围a[i] ≤ 2^2021位覆盖所有可能cnt0 cnt1 n1可以用这个验证计数是否正确long long答案可能很大Python自动处理C要开long long4.6 进一步优化空间优化不需要存pre_xor数组可以边读边处理nint(input())alist(map(int,input().split()))MAX_BIT21ans0forkinrange(MAX_BIT):cnt0,cnt11,0# pre_xor[0]0第0位是0所以cnt0初始为1xor_sum0fornumina:xor_sum^numif(xor_sumk)1:cnt11else:cnt01anscnt0*cnt1*(1k)print(ans)这样空间复杂度降到O(1)除了输入数组。 今日复盘总结题目核心技巧思维路径易错点国赛价值子串简写贡献法前缀和枚举右端点统计左端点合法个数下标越界、pre[-1]⭐⭐⭐最大子矩阵二维转一维单调队列枚举上下边界→滑动窗口→维护最值单调队列实现、过期元素⭐⭐⭐⭐闪耀的灯光二维前缀和子矩阵和→容斥公式下标从1开始、公式符号⭐⭐⭐⭐异或和之和按位独立贡献法异或按位独立→0/1配对统计空前缀pre[0]、位运算优先级⭐⭐⭐⭐⭐ 记得点赞收藏算法路上不迷路有问题评论区见
