写在前面今天复盘的是蓝桥杯算法赛真题涵盖简单模拟、前缀和、位运算、哈希优化四大核心考点。这些题目难度梯度明显从入门到进阶是检验国赛备战成果的绝佳试金石。本文将对每道题进行深度拆解不仅给代码更讲清楚为什么这样写。 今日刷题清单题号题目来源类型难度核心考点1蘑菇炸弹蓝桥杯9497模拟⭐⭐数组遍历、条件判断2帕鲁服务器崩坏蓝桥杯19687前缀和⭐⭐⭐状态转移、区间查询3区间或蓝桥杯3691位运算前缀和⭐⭐⭐⭐按位独立、前缀和优化4异或森林蓝桥杯3400前缀异或哈希⭐⭐⭐⭐⭐数学转化、哈希计数、反向思考一、蘑菇炸弹 ⭐⭐ 热身题1.1 题目描述给定数组a统计有多少个位置i1 ≤ i ≤ n-1满足a[i] ≥ a[i-1] a[i1]。1.2 关键思路暴力遍历对于每个中间位置i检查是否大于等于两边之和。注意边界i从1到n-20-indexed即跳过第一个和最后一个元素。1.3 推演验证输入: n5, a[1, 3, 2, 5, 2] i1: a[1]3, a[0]a[2]123, 33 ✓ i2: a[2]2, a[1]a[3]358, 28 ✗ i3: a[3]5, a[2]a[4]224, 54 ✓ ans 21.4 题解nint(input())alist(map(int,input().split()))ans0# 遍历中间位置跳过首尾foriinrange(1,n-1):ifa[i]a[i-1]a[i1]:ans1print(ans)复杂度时间O(n)空间O(1)1.5 关键细节坑点说明遍历范围range(1, n-1)i从1到n-2确保i-1和i1都合法条件判断不是等于也算满足条件二、帕鲁服务器崩坏 ⭐⭐⭐ 前缀和基础2.1 题目描述给定01字符串1表示服务器关闭会重启0表示正常运行。重启成功定义从1变为0即位置i为1位置i1为0。求m次查询每次查询区间[l, r)内重启成功的次数。2.2 关键思路状态定义如果s[i] 0 and s[i-1] 1位置i是重启成功点用前缀和数组pre_sum[i]记录到位置i为止的重启成功次数区间查询pre_sum[r-1] - pre_sum[l-1]注意区间是[l, r)2.3 推演验证输入: n5, s10110, m4 位置: 0 1 2 3 4 字符: 1 0 1 1 0 pre_sum数组 pre_sum[0]0 i1: s[1]0, s[0]1 → 重启成功pre_sum[1]1 i2: s[2]1, s[1]0 → 不是 pre_sum[2]1 i3: s[3]1, s[2]1 → 不是 pre_sum[3]1 i4: s[4]0, s[3]1 → 重启成功pre_sum[4]2 pre_sum [0, 1, 1, 1, 2] 查询 [1, 2): l1, r2 lmax(0, 1-1)0, rmin(4, 2-1)1 pre_sum[1]-pre_sum[0] 1-0 1 ✓ 查询 [1, 3): l1, r3 l0, rmin(4, 3-1)2 pre_sum[2]-pre_sum[0] 1-0 1 ✓ 查询 [2, 4): l2, r4 l1, rmin(4, 4-1)3 pre_sum[3]-pre_sum[1] 1-1 0 ✓ 查询 [2, 5): l2, r5 l1, rmin(4, 5-1)4 pre_sum[4]-pre_sum[1] 2-1 1 ✓2.4 题解importsysinputsys.stdin.readline nint(input())sinput().strip()mint(input())# 前缀和数组pre_sum[i] 到位置i为止的重启成功次数pre_sum[0]*nforiinrange(1,n):ifint(s[i])0andint(s[i-1])1:pre_sum[i]1pre_sum[i-1]# 重启成功计数1else:pre_sum[i]pre_sum[i-1]# 继承前一个值# m次查询for_inrange(m):l,rmap(int,input().split())lmax(l-1,0)# 转换为0-indexedrmin(n-1,r-1)# 注意右边界print(pre_sum[r]-pre_sum[l])复杂度时间O(n m)空间O(n)2.5 关键细节坑点说明重启成功条件s[i]0 and s[i-1]1不是简单的01交替区间转换输入是[l,r)要转换为0-indexed并处理边界pre_sum[0]0第一个位置不可能重启成功边界处理l max(l-1, 0)防止l1时变成0r min(n-1, r-1)防止越界三、区间或 ⭐⭐⭐⭐ 位运算前缀和3.1 题目描述给定数组aq次询问每次求区间[l, r]的按位或结果。3.2 关键思路或运算性质只要有1就为1按位独立。核心思想对每一位单独处理对于第i位只要区间内有任意一个数该位为1结果该位就是1用前缀和统计每一位的1的个数O(1)判断区间内是否有13.3 推演验证输入: n5, q1 a [5, 1, 2, 3, 4] 二进制 5 101 1 001 2 010 3 011 4 100 按位分离 第0位1, 1, 0, 1, 0 → 前缀和: [1, 2, 2, 3, 3] 第1位0, 0, 1, 1, 0 → 前缀和: [0, 0, 1, 2, 2] 第2位1, 0, 0, 0, 1 → 前缀和: [1, 1, 1, 1, 2] 查询 [2, 4]1-indexed→ [1, 3]0-indexed 第0位: pre[3]-pre[0] 3-1 2 0 → 该位为1 第1位: pre[3]-pre[0] 2-0 2 0 → 该位为1 第2位: pre[3]-pre[0] 1-1 0 → 该位为0 结果: 011 3 验证: a[1]|a[2]|a[3] 1|2|3 3 ✓3.4 题解fromitertoolsimportaccumulateimportsysinputsys.stdin.readline n,qmap(int,input().split())alist(map(int,input().split()))# 对每一位单独处理构建前缀和# 第i位的前缀和a_bit[i][j] 表示前j个数中第i位为1的个数a_bit[]foriinrange(31):# 题目数据范围31位足够now[]forxina:now.append((xi)1)a_bit.append(list(accumulate(now)))# 处理查询for_inrange(q):l,rmap(int,input().split())l,rl-1,r-1# 转为0-indexedans0foriinrange(31):# 计算[l,r]区间内第i位1的个数ifl0:cnta_bit[i][r]else:cnta_bit[i][r]-a_bit[i][l-1]# 只要有1该位就是1ifcnt0:ans(1i)print(ans)复杂度时间O(31 * (n q))空间O(31 * n)3.5 关键细节坑点说明按位独立或运算没有进位每一位互不影响这是能分开处理的根本原因前缀和下标accumulate返回的是前缀和注意l0的特殊处理位运算优先级(x i) 1的括号不能省优先级低于31位足够根据题目数据范围决定一般int范围31位即可四、异或森林 ⭐⭐⭐⭐⭐ 前缀异或哈希压轴题4.1 题目描述给定长度为n的数字列表求有多少个子数组满足子数组元素异或结果不是平方数。4.2 关键思路反向思考 数学转化第一步正难则反直接求异或结果不是平方数很难转换思路总子数组数 - 异或结果是平方数的子数组数第二步前缀异或利用异或的自反性a ^ a 0设pre_xor[i] a[0] ^ a[1] ^ ... ^ a[i]子数组[l, r]的异或值 pre_xor[r] ^ pre_xor[l-1]第三步哈希优化问题转化为求有多少对(l, r)满足pre_xor[r] ^ pre_xor[l-1] xx是平方数即pre_xor[l-1] x ^ pre_xor[r]对于每个r只需要知道左边有多少个pre_xor值等于x ^ pre_xor[r]用**哈希表字典**维护前缀异或值的出现次数实现O(1)查询第四步枚举平方数数据范围内平方数的个数是有限的大约sqrt(max_value)个从小到大枚举平方数x i*i分别计算贡献4.3 推演验证输入: n3, a[1, 2, 3] 总子数组数 3*4/2 6 前缀异或 pre_xor[0] 1 pre_xor[1] 1^2 3 pre_xor[2] 3^3 0 平方数假设范围足够0, 1, 4, 9... 枚举 x0: dic{0:1} # pre_xor[-1]0 r0: pre_xor[0]1, 需要找 0^11, dic中没有ans0 dic{0:1, 1:1} r1: pre_xor[1]3, 需要找 0^33, dic中没有ans0 dic{0:1, 1:1, 3:1} r2: pre_xor[2]0, 需要找 0^00, dic中有1个ans1 dic{0:2, 1:1, 3:1} x0 贡献: 1 枚举 x1: dic{0:1} r0: 需要找 1^10, dic中有1个ans1 dic{0:1, 1:1} r1: 需要找 1^32, dic中没有ans0 dic{0:1, 1:1, 3:1} r2: 需要找 1^01, dic中有1个ans1 dic{0:1, 1:2, 3:1} x1 贡献: 2 ...其他平方数贡献为0 异或结果是平方数的子数组数 3 答案 6 - 3 3 验证 [1]: 11² ✓ [2]: 2 不是平方数 ✗ [3]: 3 不是平方数 ✗ [1,2]: 1^23 不是 ✗ [2,3]: 2^311² ✓ [1,2,3]: 1^2^300² ✓ 平方数子数组[1], [2,3], [1,2,3] → 3个 ✓ 答案 6-3 3 ✓4.4 题解nint(input())alist(map(int,input().split()))# 预处理前缀异或pre_xor[0]*n pre_xor[0]a[0]foriinrange(1,n):pre_xor[i]pre_xor[i-1]^a[i]# ans表示子数组异或结果是平方数的个数ans0# 从小到大枚举平方数根据数据范围200足够foriinrange(200):xi*i# 字典维护的是pre_xor中每个数字出现的次数# key: 前缀异或值, value: 出现次数dic{}# 最开始 pre_xor[-1] 0表示空前缀dic[0]1forrinrange(n):# 对于当前r找左边有多少个pre_xor[l-1] x ^ pre_xor[r]targetx^pre_xor[r]ansdic.get(target,0)# 把当前pre_xor[r]存入字典留给后面的r使用dic[pre_xor[r]]dic.get(pre_xor[r],0)1# 反向思考总子数组数 - 异或结果是平方数的子数组数totaln*(n1)//2anstotal-ansprint(ans)复杂度时间O(200 * n)空间O(n)4.5 关键细节坑点说明反向思考正着做很难总 - 不符合是常见技巧前缀异或性质pre_xor[r] ^ pre_xor[l-1]表示[l,r]的异或值利用自反性哈希表初始化dic[0] 1对应pre_xor[-1] 0表示空前缀容易漏掉枚举范围range(200)根据数据范围调整确保覆盖所有可能的平方数字典更新顺序先查询dic再更新当前值避免重复计数当前r不能和当前r配对 今日复盘总结题目核心技巧易错点国赛价值蘑菇炸弹简单模拟边界处理、等号条件⭐⭐ 基础送分帕鲁服务器崩坏前缀和区间转换、状态定义⭐⭐⭐ 模板题区间或位运算前缀和按位独立思想⭐⭐⭐⭐ 经典优化异或森林前缀异或哈希反向思考数学转化、字典初始化⭐⭐⭐⭐⭐ 压轴思维