备战蓝桥杯国赛【Day 14】

📌写在前面：今天复盘的是蓝桥杯算法赛真题，涵盖简单模拟、前缀和、位运算、哈希优化四大核心考点。这些题目难度梯度明显，从入门到进阶，是检验国赛备战成果的绝佳试金石。本文将对每道题进行深度拆解，不仅给代码，更讲清楚为什么这样写。

📚 今日刷题清单

一、蘑菇炸弹 ⭐⭐ 热身题

1.1 题目描述

给定数组a，统计有多少个位置i（1 ≤ i ≤ n-1）满足：a[i] ≥ a[i-1] + a[i+1]。

1.2 关键思路

• 暴力遍历：对于每个中间位置i，检查是否大于等于两边之和。
• 注意边界：i从1到n-2（0-indexed），即跳过第一个和最后一个元素。

1.3 推演验证

输入: n=5, a=[1, 3, 2, 5, 2] i=1: a[1]=3, a[0]+a[2]=1+2=3, 3>=3 ✓ i=2: a[2]=2, a[1]+a[3]=3+5=8, 2>=8 ✗ i=3: a[3]=5, a[2]+a[4]=2+2=4, 5>=4 ✓ ans = 2

1.4 题解

n=int(input())a=list(map(int,input().split()))ans=0# 遍历中间位置（跳过首尾）foriinrange(1,n-1):ifa[i]>=a[i-1]+a[i+1]:ans+=1print(ans)

复杂度：时间O(n)，空间O(1)

1.5 关键细节

二、帕鲁服务器崩坏 ⭐⭐⭐ 前缀和基础

2.1 题目描述

给定01字符串，1表示服务器关闭（会重启），0表示正常运行。

• 重启成功定义：从1变为0（即位置i为1，位置i+1为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 推演验证

输入: n=5, s="10110", m=4 位置: 0 1 2 3 4 字符: 1 0 1 1 0 pre_sum数组： pre_sum[0]=0 i=1: s[1]=0, s[0]=1 → 重启成功！pre_sum[1]=1 i=2: s[2]=1, s[1]=0 → 不是 pre_sum[2]=1 i=3: s[3]=1, s[2]=1 → 不是 pre_sum[3]=1 i=4: s[4]=0, s[3]=1 → 重启成功！pre_sum[4]=2 pre_sum = [0, 1, 1, 1, 2] 查询 [1, 2): l=1, r=2 l=max(0, 1-1)=0, r=min(4, 2-1)=1 pre_sum[1]-pre_sum[0] = 1-0 = 1 ✓ 查询 [1, 3): l=1, r=3 l=0, r=min(4, 3-1)=2 pre_sum[2]-pre_sum[0] = 1-0 = 1 ✓ 查询 [2, 4): l=2, r=4 l=1, r=min(4, 4-1)=3 pre_sum[3]-pre_sum[1] = 1-1 = 0 ✓ 查询 [2, 5): l=2, r=5 l=1, r=min(4, 5-1)=4 pre_sum[4]-pre_sum[1] = 2-1 = 1 ✓

2.4 题解

importsysinput=sys.stdin.readline n=int(input())s=input().strip()m=int(input())# 前缀和数组：pre_sum[i] = 到位置i为止的重启成功次数pre_sum=[0]*nforiinrange(1,n):ifint(s[i])==0andint(s[i-1])==1:pre_sum[i]=1+pre_sum[i-1]# 重启成功，计数+1else:pre_sum[i]=pre_sum[i-1]# 继承前一个值# m次查询for_inrange(m):l,r=map(int,input().split())l=max(l-1,0)# 转换为0-indexedr=min(n-1,r-1)# 注意右边界print(pre_sum[r]-pre_sum[l])

复杂度：时间O(n + m)，空间O(n)

2.5 关键细节

三、区间或 ⭐⭐⭐⭐ 位运算+前缀和

3.1 题目描述

给定数组a，q次询问，每次求区间[l, r]的按位或结果。

3.2 关键思路

• 或运算性质：只要有1就为1，按位独立。
• 核心思想：对每一位单独处理！
  • 对于第i位，只要区间内有任意一个数该位为1，结果该位就是1
  • 用前缀和统计每一位的1的个数，O(1)判断区间内是否有1

3.3 推演验证

输入: n=5, q=1 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 题解

fromitertoolsimportaccumulateimportsysinput=sys.stdin.readline n,q=map(int,input().split())a=list(map(int,input().split()))# 对每一位单独处理，构建前缀和# 第i位的前缀和：a_bit[i][j] 表示前j个数中，第i位为1的个数a_bit=[]foriinrange(31):# 题目数据范围，31位足够now=[]forxina:now.append((x>>i)&1)a_bit.append(list(accumulate(now)))# 处理查询for_inrange(q):l,r=map(int,input().split())l,r=l-1,r-1# 转为0-indexedans=0foriinrange(31):# 计算[l,r]区间内第i位1的个数ifl==0:cnt=a_bit[i][r]else:cnt=a_bit[i][r]-a_bit[i][l-1]# 只要有1，该位就是1ifcnt>0:ans+=(1<<i)print(ans)

复杂度：时间O(31 * (n + q))，空间O(31 * n)

3.5 关键细节

四、异或森林 ⭐⭐⭐⭐⭐ 前缀异或+哈希（压轴题）

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] = x（x是平方数）
• 即：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 推演验证

输入: n=3, 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... 枚举 x=0: dic={0:1} # pre_xor[-1]=0 r=0: pre_xor[0]=1, 需要找 0^1=1, dic中没有，ans+=0 dic={0:1, 1:1} r=1: pre_xor[1]=3, 需要找 0^3=3, dic中没有，ans+=0 dic={0:1, 1:1, 3:1} r=2: pre_xor[2]=0, 需要找 0^0=0, dic中有1个，ans+=1 dic={0:2, 1:1, 3:1} x=0 贡献: 1 枚举 x=1: dic={0:1} r=0: 需要找 1^1=0, dic中有1个，ans+=1 dic={0:1, 1:1} r=1: 需要找 1^3=2, dic中没有，ans+=0 dic={0:1, 1:1, 3:1} r=2: 需要找 1^0=1, dic中有1个，ans+=1 dic={0:1, 1:2, 3:1} x=1 贡献: 2 ...（其他平方数贡献为0） 异或结果是平方数的子数组数 = 3 答案 = 6 - 3 = 3 验证： [1]: 1=1² ✓ [2]: 2 不是平方数 ✗ [3]: 3 不是平方数 ✗ [1,2]: 1^2=3 不是 ✗ [2,3]: 2^3=1=1² ✓ [1,2,3]: 1^2^3=0=0² ✓ 平方数子数组：[1], [2,3], [1,2,3] → 3个 ✓ 答案 = 6-3 = 3 ✓

4.4 题解

n=int(input())a=list(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表示子数组异或结果是平方数的个数ans=0# 从小到大枚举平方数（根据数据范围，200足够）foriinrange(200):x=i*i# 字典维护的是pre_xor中每个数字出现的次数# key: 前缀异或值, value: 出现次数dic={}# 最开始 pre_xor[-1] = 0（表示空前缀）dic[0]=1forrinrange(n):# 对于当前r，找左边有多少个pre_xor[l-1] = x ^ pre_xor[r]target=x^pre_xor[r]ans+=dic.get(target,0)# 把当前pre_xor[r]存入字典，留给后面的r使用dic[pre_xor[r]]=dic.get(pre_xor[r],0)+1# 反向思考：总子数组数 - 异或结果是平方数的子数组数total=n*(n+1)//2ans=total-ansprint(ans)

复杂度：时间O(200 * n)，空间O(n)

4.5 关键细节

🎯 今日复盘总结