写在前面今天的题目全部来自蓝桥杯算法赛真题难度直接对标国赛涵盖了差分数组进阶应用、贪心策略、二分查找、优先队列、大数运算等核心考点。这些题目不仅是国赛的高频考点更是区分省一和国一的关键分水岭 今日刷题清单题号题目类型难度核心考点1字符迁移蓝桥杯17164⭐⭐⭐差分数组、循环移位2食堂蓝桥杯19724⭐⭐⭐⭐贪心、分类讨论3X进制减法蓝桥杯2108⭐⭐⭐⭐大数运算、进制转换4巧克力蓝桥杯1596⭐⭐⭐⭐⭐贪心、优先队列、堆5管道蓝桥杯3544⭐⭐⭐⭐⭐二分查找、区间合并一、核心算法速查1.1 差分数组进阶# 基础差分区间加法diff[l]k diff[r1]-k# 进阶差分循环移位字符迁移# 将字符转换为数字差分后还原再转回字符1.2 贪心策略# 策略1能配对就配对食堂问题# 策略2从后往前优先队列巧克力问题# 策略3局部最优推全局最优1.3 二分查找模板# 找最小满足条件的值left,right0,max_valwhileleftright:mid(leftright)//2ifcheck(mid):# mid满足条件rightmid# 尝试更小else:leftmid1# 需要更大print(left)二、例题精讲例题 1字符迁移 ⭐差分进阶项目内容链接https://www.lanqiao.cn/problems/17164/learning/类型差分数组 循环移位核心将字符转为数字差分处理循环移位再转回字符题目描述给定字符串q qq次操作每次将区间[ l , r ] [l,r][l,r]的字符向后移动k kk位循环。关键思路将字符问题转化为数字问题字符转数字a - 0, b - 1, ..., z - 25差分数组处理区间加法对26取模还原前缀和数字转回字符推演验证输入: n5, sabcde, q1 操作: [1,3,2] # 将[1,3]的字符后移2位 字符转数字a0, b1, c2, d3, e4 差分操作后还原s [3, 4, 5, 4, 0] 结果: defea ✓题解n,qmap(int,input().split())s[0]list(input())# 1-indexeddiff[0]*(n2)# 字符转数字构建差分数组foriinrange(1,n1):s[i]ord(s[i])-97diff[i]s[i]-s[i-1]# q次操作for_inrange(q):l,r,kmap(int,input().split())kk%26diff[l]k diff[r1]-k# 还原前缀和转回字符foriinrange(1,n1):s[i]diff[i]s[i-1]print(chr(s[i]%2697),end)复杂度时间O ( n q ) O(n q)O(nq)空间O ( n ) O(n)O(n)例题 2食堂 ⭐⭐⭐贪心分类讨论项目内容链接https://www.lanqiao.cn/problems/19724/learning/类型贪心 分类讨论核心优先配对能坐满就坐满逐步降级处理关键思路贪心策略大桌优先配大组合逐步降级6人桌33→222→ 降级为4人桌4人桌4→22→3→2题解qint(input())for_inrange(q):a2,a3,a4,b4,b6map(int,input().split())res0# 6人桌先33配对d3a3//2ifb6d3:resb6*6a3-b6*2else:resd3*6a3-d3*2b6-d3 b4b6ifa2b6:resb6*2a2-b6else:resa2*2a20# 4人桌4 → 22 → 3 → 2ifb4a4:resa4*4b4-a4 d2a2//2ifb4d2:resd2*4b4-d2 a2-d2*2ifb4a3:resa3*3b4-a3ifa2!0:res2else:resb4*3else:resb4*4else:resb4*4print(res)复杂度时间O ( q ) O(q)O(q)空间O ( 1 ) O(1)O(1)例题 3X进制减法 ⭐⭐⭐大数运算项目内容链接https://www.lanqiao.cn/problems/2108/learning/类型大数运算 进制转换核心从低位到高位每位进制取最小防止溢出关键思路A − B ∑ ( a i − b i ) × x i A - B \sum (a_i - b_i) \times x_iA−B∑(ai−bi)×xi要使A − B A - BA−B最小每位进制都取最小值m a x ( a i 1 , b i 1 , 2 ) max(a_i1, b_i1, 2)max(ai1,bi1,2)题解Mod1000000007Nint(input())n1int(input())num1list(map(int,input().split()))n2int(input())num2list(map(int,input().split()))# 补齐B的位数whilelen(num2)n1:num2[0]num2 ans0x1# 从低位到高位遍历foriinrange(n1-1,-1,-1):ans(ans(num1[i]-num2[i])*x)%Mod xx*max(num1[i]1,num2[i]1,2)%Modprint(ans%Mod)复杂度时间O ( n ) O(n)O(n)空间O ( n ) O(n)O(n)例题 4巧克力 ⭐⭐⭐⭐⭐ 贪心优先队列项目内容链接https://www.lanqiao.cn/problems/1596/learning/类型贪心 优先队列小根堆核心从后往前贪心每天选最便宜的可用巧克力关键思路为什么不能简单按价格排序反例价格1保质期10天数量2 价格3保质期4天数量3 价格10保质期5天数量4。简单排序会导致前面吃便宜的后面不得不吃贵的。正确策略按保质期从大到小排序从最后一天往前遍历维护小根堆每天选最便宜的题解importheapq x,nmap(int,input().split())l[]foriinrange(n):a,b,cmap(int,input().split())l.append([a,b,c])# 按保质期从大到小排序l.sort(keylambdapair:-pair[1])res,j0,0q[]# 从最后一天往前遍历foriinrange(x,0,-1):whilejnandl[j][1]i:heapq.heappush(q,[l[j][0],l[j][1],l[j][2]])j1ifnotq:print(-1)breaktheapq.heappop(q)rest[0]t[2]-1ift[2]:heapq.heappush(q,t)else:print(res)复杂度时间O ( n log n x log n ) O(n \log n x \log n)O(nlognxlogn)空间O ( n ) O(n)O(n)例题 5管道 ⭐⭐⭐⭐⭐ 二分区间合并项目内容链接https://www.lanqiao.cn/problems/3544/learning/类型二分查找 区间合并核心二分最小时间检查该时间是否能覆盖整个管道关键思路二分答案时间T TT越大水流扩散越远具有单调性。check(T)计算每个阀门在T TT时刻覆盖的区间[Li-(T-Si), Li(T-Si)]合并所有区间检查是否覆盖[1, Len]题解defcheck(Ti,values,Len):section[]forLi,Siinvalues:ifTiSi:spreadTi-Si section.append((Li-spread,Lispread))section.sort()ifnotsectionorsection[0][0]1:returnFalseright_boundarysection[0][1]foriinrange(1,len(section)):ifsection[i][0]-right_boundary1:right_boundarymax(right_boundary,section[i][1])else:breakreturnright_boundaryLen n,Lenmap(int,input().split())values[list(map(int,input().split()))for_inrange(n)]left,right0,10**9whileleftright:mid(leftright)//2ifcheck(mid,values,Len):rightmidelse:leftmid1print(left)复杂度每次check为O ( n log n ) O(n \log n)O(nlogn)二分O ( log 10 9 ) O(\log 10^9)O(log109)总时间O ( n log n log 10 9 ) O(n \log n \log 10^9)O(nlognlog109)三、今日刷题总结题号题目考点难度核心技巧1字符迁移差分进阶⭐⭐⭐字符转数字差分循环移位2食堂贪心分类⭐⭐⭐⭐大桌优先配对逐步降级3X进制减法大数运算⭐⭐⭐⭐从低位到高位取最小进制4巧克力贪心堆⭐⭐⭐⭐⭐从后往前小根堆选最小5管道二分区间合并⭐⭐⭐⭐⭐二分答案检查区间覆盖核心算法模板汇总# 模板1差分处理循环移位 foriinrange(1,n1):s[i]ord(s[i])-97diff[i]s[i]-s[i-1]diff[l]k;diff[r1]-kforiinrange(1,n1):s[i]diff[i]s[i-1]print(chr(s[i]%2697),end)# 模板2贪心优先队列从后往前 l.sort(keylambdax:-x[1])q[]j0foriinrange(x,0,-1):whilejnandl[j][1]i:heapq.heappush(q,l[j]);j1theapq.heappop(q)# 处理t...# 模板3二分查找找最小满足条件 left,right0,max_valwhileleftright:mid(leftright)//2ifcheck(mid):rightmidelse:leftmid1print(left)# 模板4区间合并 section.sort()right_boundarysection[0][1]foriinrange(1,len(section)):ifsection[i][0]-right_boundary1:right_boundarymax(right_boundary,section[i][1])else:break四、结语今天的5道题都是蓝桥杯算法赛真题难度直接对标国赛今日收获差分进阶字符转数字处理循环移位拓展了差分的应用场景贪心策略大桌优先配对、从后往前选最小贪心无处不在大数运算X进制减法的取模技巧防止溢出优先队列维护可用集合动态选最优是高级贪心的标配二分答案将最优化问题转化为判定问题配合check函数记住看到区间修改想差分看到最优化问题想贪心看到最小/最大满足条件想二分继续加油国赛见如果本文对你有帮助欢迎点赞 收藏 ⭐ 关注 你的支持是我持续更新的动力 
