备战蓝桥杯国赛【Day 8】

例题 1数字统计蓝桥杯基础题项目内容类型暴力枚举 / 数学核心遍历区间统计数字出现次数题目描述统计范围[L, R]的所有整数中数字2出现的次数。输入格式L R输出格式数字2出现的次数。题解直接遍历每个数转成字符串统计2的个数。l,rmap(int,input().split())ans0foriinrange(l,r1):ansstr(i).count(2)print(ans)推演验证输入: 2 22 i2: 2 → 1个2, ans1 i3~11: 无2, ans1 i12: 12 → 1个2, ans2 i20: 20 → 1个2, ans3 i21: 21 → 1个2, ans4 i22: 22 → 2个2, ans6 输出: 6 ✓复杂度分析指标复杂度说明时间O((R-L) * log R)遍历区间每个数转字符串空间O(1)只维护计数器优化思路数据范围R 10^4暴力即可。如果R 10^18需要用数位DP。例题 2接水问题蓝桥杯经典题项目内容类型贪心 堆优先队列核心每次选最快接完水的龙头分配下一个人题目描述m个水龙头n个人接水每人接水量w[i]。每人每秒接水量为1。求所有人接完水的最短时间。输入格式n m w1 w2 ... wn输出格式最短时间秒。题解贪心策略用堆维护每个龙头的剩余接水量每次选接完最早的龙头分配下一个人。importheapq n,mmap(int,input().split())wlist(map(int,input().split()))# 初始化m个龙头前m个人直接分配longw[:m]heapq.heapify(long)im# 下一个待分配的人的索引whilein:# 取出最快接完的龙头minnheapq.heappop(long)# 分配下一个人该龙头累计接水量增加heapq.heappush(long,minnw[i])i1# 最后一个接完的时间就是堆中的最大值print(max(long))推演验证输入: 5 3 4 4 1 2 1 初始化: long [4, 4, 1] (堆化后: [1, 4, 4]) i3, w[3]2: pop最小1, push 123, long[3, 4, 4] i4, w[4]1: pop最小3, push 314, long[4, 4, 4] 结束, max(long)4 输出: 4 ✓复杂度分析指标复杂度说明时间O(n log m)堆操作O(log m)共n次空间O(m)堆的大小关键细节坑点说明堆存的是累计接水量不是单个人的接水量是龙头上所有人的总和max(long)取结果堆顶是最小但答案是最后一个完成的即堆中最大前m个人直接入堆不需要比较直接分配例题 3小蓝的零花钱蓝桥杯真题项目内容类型贪心 排序核心先找所有合法切割点再按代价从小到大选题目描述长度为n的序列偶数和奇数数量相等。每次操作选一个位置切割要求两段中偶数和奇数数量都相等。代价为切割两端元素的差的绝对值。预算B求最多操作次数。输入格式n B a1 a2 ... an输出格式最多操作次数。题解步骤1找所有合法切割点。遍历每个位置统计左边偶数和奇数数量当偶数奇数时该位置可切割。步骤2收集所有合法切割的代价排序。步骤3从小到大选直到预算不够。n,bmap(int,input().split())alist(map(int,input().split()))cnt0# 当前偶数-奇数的差值res[]# 所有合法切割的代价# 遍历每个可能的切割位置0到n-2foriinrange(n-1):ifa[i]%20:cnt1else:cnt-1# 如果cnt0说明[0..i]中偶数奇数可以切割ifcnt0:# 代价为切割两端元素的差的绝对值res.append(abs(a[i]-a[i1]))# 贪心按代价从小到大选res.sort()ans0forcostinres:ifbcost:b-cost ans1else:breakprint(ans)推演验证输入: 6 3 1 2 3 4 5 6 i0: a[0]1(奇), cnt-1, 不为0 i1: a[1]2(偶), cnt0, 合法! 代价|2-3|1, res[1] i2: a[2]3(奇), cnt-1, 不为0 i3: a[3]4(偶), cnt0, 合法! 代价|4-5|1, res[1,1] i4: a[4]5(奇), cnt-1, 不为0 res[1,1], 排序后[1,1] b3, 选第一个: b2, ans1 选第二个: b1, ans2 输出: 2 ✓复杂度分析指标复杂度说明时间O(n log n)遍历O(n) 排序O(n log n)空间O(n)存储代价数组关键细节坑点说明cnt的含义偶数个数 - 奇数个数为0时平衡只遍历到n-2最后一段需要至少一个元素代价是abs(a[i]-a[i1])切割位置的两端元素贪心排序后从小到大选预算有限先选代价小的例题 4石子合并蓝桥杯 P545项目内容链接https://www.lanqiao.cn/problems/545/learning/类型贪心 堆核心每次选最小的两个合并题目描述n个部落人数t[i]。每次合并两个部落花费为人数之和。求合并成一个部落的最小总花费。题解importheapq nint(input())alist(map(int,input().split()))heapq.heapify(a)ans0whilelen(a)2:xheapq.heappop(a)yheapq.heappop(a)costxy anscost heapq.heappush(a,cost)print(ans)推演验证n4, a[1,2,3,4] 堆: [1,2,3,4] 第1轮: 取1,2, 合并3, ans3, 堆[3,3,4] 第2轮: 取3,3, 合并6, ans9, 堆[4,6] 第3轮: 取4,6, 合并10, ans19, 堆[10] 输出: 19 ✓例题 5分箱问题蓝桥杯 P532项目内容链接https://www.lanqiao.cn/problems/532/learning/类型贪心 排序 双指针核心最小配最大题目描述纪念品价格上限wn个纪念品每组最多两件价格之和 w。求最少分组数。题解wint(input())nint(input())a[int(input())for_inrange(n)]a.sort()l,r0,n-1ans0whileTrue:iflr:ans1breakiflr:breakifa[l]a[r]w:ans1l1r-1else:ans1r-1print(ans)例题 6翻硬币蓝桥杯 P209项目内容链接https://www.lanqiao.cn/problems/209/learning/类型贪心 从左往右扫核心遇到不同就翻题目描述初始状态s目标状态t每次翻转相邻两个硬币。求最少操作次数。题解slist(input())tlist(input())nlen(s)ans0foriinrange(n-1):ifs[i]t[i]:continue# 翻转 i 和 i1s[i]t[i]s[i1]*ifs[i1]oelseoans1print(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后面即使有小贡献也能维持完整代码nint(input())Alist(map(int,input().split()))Blist(map(int,input().split()))Clist(map(int,input().split()))defwin(X,Y,Z): 计算第一个国家获胜时最多能发生多少个事件 X: 获胜国家的增量数组 Y, Z: 另外两个国家的增量数组 w0# 当前累计贡献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(reverseTrue)foriinrange(n):wcontribute[i]# 如果加入第i个事件后累加和0说明前i个事件无法维持获胜# 返回i因为range从0开始i就是前面成功的事件数ifw0:returni# 所有事件都发生累加和始终0returnn# 分别计算三个国家获胜的情况取最大值resultmax(win(A,B,C),win(B,A,C),win(C,A,B))ifresult0:print(-1)# 无法让任何国家获胜else:print(result)推演验证输入: 3 1 2 3 2 3 2 1 0 7 事件0: A1, B2, C1 → X贡献1-2-1-2, Y贡献2-1-10, Z贡献1-2-1-2 事件1: A2, B3, C0 → X贡献2-3-0-1, Y贡献3-2-01, Z贡献0-2-3-5 事件2: A3, B2, C7 → X贡献3-2-7-6, Y贡献2-3-7-8, Z贡献7-3-22 win(A,B,C): 贡献[-2,-1,-6], 排序[-1,-2,-6] i0: w-10, 返回0 win(B,A,C): 贡献[0,1,-8], 排序[1,0,-8] i0: w10 i1: w1010 i2: w10-8-70, 返回2 win(C,A,B): 贡献[-2,-5,2], 排序[2,-2,-5] i0: w20 i1: w2-200, 返回1 result max(0, 2, 1) 2 输出: 2 ✓复杂度分析指标复杂度说明时间O(n log n)排序O(n log n)三次调用空间O(n)贡献值数组关键细节坑点说明事件顺序可控这是本题的关键可以任意排序事件贡献值可能为负负贡献的事件放在后面前面先用正贡献垫高返回i的含义第i个事件加入后首次0说明前i个成功result0输出-1无法让任何国家获胜贪心正确性证明为什么贡献大的先发生最优假设有两个事件贡献分别为p q。如果先q后p累加过程q, qp如果q 0可能第一步就失败如果先p后q累加过程p, pqp更大更容易先大于0后续更稳定结论按贡献从大到小排序能让累加和尽快突破0且最稳定。 今日刷题总结题号/来源考点贪心类型难度核心技巧数字统计暴力枚举-⭐字符串统计接水问题堆贪心优先队列⭐⭐⭐每次选最快完成的龙头小蓝的零花钱排序贪心排序后从小到大选⭐⭐⭐先找合法点再按代价选P545石子合并堆⭐⭐⭐每次取最小两个P532分箱问题排序双指针⭐⭐最小配最大P209翻硬币从左往右扫⭐⭐遇到不同就翻三国游戏排序贪心贡献大的先发生⭐⭐⭐⭐控制事件顺序让累加和尽快0