备战蓝桥杯国赛【Day 8】

例题 1：数字统计（蓝桥杯基础题）

题目描述

统计范围[L, R]的所有整数中，数字2出现的次数。

输入格式

L R

输出格式

数字2出现的次数。

题解

直接遍历每个数，转成字符串统计2的个数。

l,r=map(int,input().split())ans=0foriinrange(l,r+1):ans+=str(i).count('2')print(ans)

推演验证

输入: 2 22 i=2: "2" → 1个2, ans=1 i=3~11: 无2, ans=1 i=12: "12" → 1个2, ans=2 i=20: "20" → 1个2, ans=3 i=21: "21" → 1个2, ans=4 i=22: "22" → 2个2, ans=6 输出: 6 ✓

复杂度分析

优化思路

数据范围R <= 10^4，暴力即可。如果R <= 10^18，需要用数位DP。

例题 2：接水问题（蓝桥杯经典题）

题目描述

m个水龙头，n个人接水，每人接水量w[i]。每人每秒接水量为1。求所有人接完水的最短时间。

输入格式

n m w1 w2 ... wn

输出格式

最短时间（秒）。

题解

贪心策略：用堆维护每个龙头的剩余接水量，每次选接完最早的龙头，分配下一个人。

importheapq n,m=map(int,input().split())w=list(map(int,input().split()))# 初始化m个龙头，前m个人直接分配long=w[:m]heapq.heapify(long)i=m# 下一个待分配的人的索引whilei<n:# 取出最快接完的龙头minn=heapq.heappop(long)# 分配下一个人，该龙头累计接水量增加heapq.heappush(long,minn+w[i])i+=1# 最后一个接完的时间就是堆中的最大值print(max(long))

推演验证

输入: 5 3 4 4 1 2 1 初始化: long = [4, 4, 1] (堆化后: [1, 4, 4]) i=3, w[3]=2: pop最小=1, push 1+2=3, long=[3, 4, 4] i=4, w[4]=1: pop最小=3, push 3+1=4, long=[4, 4, 4] 结束, max(long)=4 输出: 4 ✓

复杂度分析

关键细节

例题 3：小蓝的零花钱（蓝桥杯真题）

题目描述

长度为n的序列，偶数和奇数数量相等。每次操作选一个位置切割，要求两段中偶数和奇数数量都相等。代价为切割两端元素的差的绝对值。预算B，求最多操作次数。

输入格式

n B a1 a2 ... an

输出格式

最多操作次数。

题解

步骤1：找所有合法切割点。遍历每个位置，统计左边偶数和奇数数量，当偶数==奇数时，该位置可切割。

步骤2：收集所有合法切割的代价，排序。

步骤3：从小到大选，直到预算不够。

n,b=map(int,input().split())a=list(map(int,input().split()))cnt=0# 当前偶数-奇数的差值res=[]# 所有合法切割的代价# 遍历每个可能的切割位置（0到n-2）foriinrange(n-1):ifa[i]%2==0:cnt+=1else:cnt-=1# 如果cnt==0，说明[0..i]中偶数=奇数，可以切割ifcnt==0:# 代价为切割两端元素的差的绝对值res.append(abs(a[i]-a[i+1]))# 贪心：按代价从小到大选res.sort()ans=0forcostinres:ifb>=cost:b-=cost ans+=1else:breakprint(ans)

推演验证

输入: 6 3 1 2 3 4 5 6 i=0: a[0]=1(奇), cnt=-1, 不为0 i=1: a[1]=2(偶), cnt=0, 合法! 代价=|2-3|=1, res=[1] i=2: a[2]=3(奇), cnt=-1, 不为0 i=3: a[3]=4(偶), cnt=0, 合法! 代价=|4-5|=1, res=[1,1] i=4: a[4]=5(奇), cnt=-1, 不为0 res=[1,1], 排序后=[1,1] b=3, 选第一个: b=2, ans=1 选第二个: b=1, ans=2 输出: 2 ✓

复杂度分析

关键细节

例题 4：石子合并（蓝桥杯 P545）

题目描述

n个部落，人数t[i]。每次合并两个部落，花费为人数之和。求合并成一个部落的最小总花费。

题解

importheapq n=int(input())a=list(map(int,input().split()))heapq.heapify(a)ans=0whilelen(a)>=2:x=heapq.heappop(a)y=heapq.heappop(a)cost=x+y ans+=cost heapq.heappush(a,cost)print(ans)

推演验证

n=4, a=[1,2,3,4] 堆: [1,2,3,4] 第1轮: 取1,2, 合并=3, ans=3, 堆=[3,3,4] 第2轮: 取3,3, 合并=6, ans=9, 堆=[4,6] 第3轮: 取4,6, 合并=10, ans=19, 堆=[10] 输出: 19 ✓

例题 5：分箱问题（蓝桥杯 P532）

题目描述

纪念品价格上限w，n个纪念品，每组最多两件，价格之和<= w。求最少分组数。

题解

w=int(input())n=int(input())a=[int(input())for_inrange(n)]a.sort()l,r=0,n-1ans=0whileTrue:ifl==r:ans+=1breakifl>r:breakifa[l]+a[r]<=w:ans+=1l+=1r-=1else:ans+=1r-=1print(ans)

例题 6：翻硬币（蓝桥杯 P209）

题目描述

初始状态s，目标状态t，每次翻转相邻两个硬币。求最少操作次数。

题解

s=list(input())t=list(input())n=len(s)ans=0foriinrange(n-1):ifs[i]==t[i]:continue# 翻转 i 和 i+1s[i]=t[i]s[i+1]='*'ifs[i+1]=='o'else'o'ans+=1print(ans)

例题 7：三国游戏（蓝桥杯真题）—— 重点变形题

题目描述

魏(X)、蜀(Y)、吴(Z)三个国家，初始士兵为0。n个事件，每个事件让X,Y,Z分别增加A[i], B[i], C[i]。游戏结束时，若某国士兵 > 另外两国之和，则获胜。求最多发生多少个事件能让某国获胜。若无法获胜输出-1。

关键观察

获胜条件：X > Y + Z等价于X - Y - Z > 0

贪心策略：对于某个国家获胜的情况，计算每个事件的"贡献值"：

• 若想让 X 获胜：贡献 =A[i] - B[i] - C[i]
• 若想让 Y 获胜：贡献 =B[i] - A[i] - C[i]
• 若想让 Z 获胜：贡献 =C[i] - A[i] - B[i]

核心洞察：事件可以控制顺序！让贡献大的事件先发生，这样累加和能尽快大于0，且不会中途掉下去。

为什么排序有效？

• 如果先发生贡献小的事件，累加和可能一直小于0
• 如果先发生贡献大的事件，累加和尽快大于0，后面即使有小贡献也能维持

完整代码

n=int(input())A=list(map(int,input().split()))B=list(map(int,input().split()))C=list(map(int,input().split()))defwin(X,Y,Z):""" 计算第一个国家获胜时，最多能发生多少个事件 X: 获胜国家的增量数组 Y, Z: 另外两个国家的增量数组 """w=0# 当前累计贡献contribute=[]# 每个事件对获胜的贡献值foriinrange(n):# 事件i发生后，X增加X[i]，Y和Z增加Y[i]和Z[i]# 对X获胜的贡献 = X[i] - Y[i] - Z[i]contribute.append(X[i]-Y[i]-Z[i])# 贪心：贡献大的事件先发生，让累加和尽快大于0contribute.sort(reverse=True)foriinrange(n):w+=contribute[i]# 如果加入第i个事件后，累加和<=0，说明前i个事件无法维持获胜# 返回i（因为range从0开始，i就是前面成功的事件数）ifw<=0:returni# 所有事件都发生，累加和始终>0returnn# 分别计算三个国家获胜的情况，取最大值result=max(win(A,B,C),win(B,A,C),win(C,A,B))ifresult==0:print(-1)# 无法让任何国家获胜else:print(result)

推演验证

输入: 3 1 2 3 2 3 2 1 0 7 事件0: A=1, B=2, C=1 → X贡献=1-2-1=-2, Y贡献=2-1-1=0, Z贡献=1-2-1=-2 事件1: A=2, B=3, C=0 → X贡献=2-3-0=-1, Y贡献=3-2-0=1, Z贡献=0-2-3=-5 事件2: A=3, B=2, C=7 → X贡献=3-2-7=-6, Y贡献=2-3-7=-8, Z贡献=7-3-2=2 win(A,B,C): 贡献=[-2,-1,-6], 排序=[-1,-2,-6] i=0: w=-1<=0, 返回0 win(B,A,C): 贡献=[0,1,-8], 排序=[1,0,-8] i=0: w=1>0 i=1: w=1+0=1>0 i=2: w=1+0-8=-7<=0, 返回2 win(C,A,B): 贡献=[-2,-5,2], 排序=[2,-2,-5] i=0: w=2>0 i=1: w=2-2=0<=0, 返回1 result = max(0, 2, 1) = 2 输出: 2 ✓

复杂度分析

关键细节

贪心正确性证明

为什么贡献大的先发生最优？

假设有两个事件，贡献分别为p > q。如果先q后p：

• 累加过程：q, q+p
• 如果q < 0，可能第一步就失败

如果先p后q：

• 累加过程：p, p+q
• p更大，更容易先大于0，后续更稳定

结论：按贡献从大到小排序，能让累加和尽快突破0，且最稳定。

📊 今日刷题总结