备战蓝桥杯国赛【Day 17】

写在前面今天的4道题全部来自蓝桥杯真题核心考点包括贪心策略排序、自定义比较器、差分思想、前缀和贪心选择。这些题目看似简单但暗藏陷阱是检验代码实现能力和思维细致度的绝佳素材。 今日刷题清单题号题目来源类型难度核心考点1阿坤老师的独特瓷器蓝桥杯3994贪心排序⭐⭐⭐逆向遍历、维护最值、排序比较器2封闭图形个数蓝桥杯19733自定义排序⭐⭐⭐多关键字排序、cmp_to_key、数位拆分3摆玩具蓝桥杯5888贪心差分⭐⭐⭐⭐差分思想、贪心选择最大间隙4小蓝的零花钱蓝桥杯3236前缀和贪心⭐⭐⭐⭐前缀和判平衡、贪心选最小代价一、阿坤老师的独特瓷器1.1 题目描述阿坤老师有n个瓷器每个瓷器有两个属性直径d和高度h。一个瓷器被称为独特瓷器当且仅当它的直径d是所有瓷器中最大的直径最大的一定是独特瓷器或者它的高度h比所有直径比它大的瓷器的高度都要高换句话说将瓷器按直径从大到小排序后如果一个瓷器的高度是当前遍历过的最大值那它就是独特瓷器。1.2 关键思路排序逆向维护最大值暴力思路对每个瓷器遍历所有直径比它大的瓷器检查高度是否最大。时间O(n²)。超时原因n可能到10⁵O(n²)不可接受。优化思路按直径降序排序直径大的排前面逆向遍历从直径最大的开始维护当前见过的最大高度判断如果当前瓷器的高度≥ max_h则它是独特瓷器更新max_h为什么逆向遍历直径最大的瓷器一定是独特瓷器没有直径比它更大的从大到小遍历每个瓷器只需要和已经遍历过的即直径更大的比较高度用max_h维护已遍历瓷器的最大高度O(1) 判断1.3 推演验证输入: n5 瓷器: (d,h) [(3,5), (1,2), (4,7), (2,6), (5,1)] 按直径降序排序: (5,1), (4,7), (3,5), (2,6), (1,2) 逆向遍历从直径最大的开始: i0: (5,1), max_h1, 11 ✓, ans1 i1: (4,7), 71 ✓, max_h7, ans2 i2: (3,5), 57 ✗ i3: (2,6), 67 ✗ i4: (1,2), 27 ✗ ans 2 验证 - (5,1): 直径最大独特 ✓ - (4,7): 直径比它大的只有(5,1)h71独特 ✓ - (3,5): 直径比它大的有(5,1),(4,7)max_h757不独特 ✗ - (2,6): 直径比它大的有(5,1),(4,7),(3,5)max_h767不独特 ✗ - (1,2): 直径比它大的有...max_h727不独特 ✗1.4 题解nint(input())dh[]for_inrange(n):d,hmap(int,input().split())dh.append((d,h))# 按直径降序排序直径相同则按高度升序其实高度无所谓因为直径相同不会互相比较dhsorted(dh,keylambdax:(-x[0],x[1]))ans1# 直径最大的一定是独特瓷器max_hdh[0][1]# 当前最大高度foriinrange(1,n):# 如果当前高度 之前所有直径更大的的最大高度ifdh[i][1]max_h:ans1# 更新最大高度max_hmax(max_h,dh[i][1])print(ans)复杂度时间O(n log n)排序空间O(n)1.5 关键细节坑点说明排序方向直径降序所以keylambda x: -x[0]初始值ans1因为直径最大的瓷器一定是独特瓷器max_h更新时机先判断再更新还是先更新再判断应该是先判断用旧max_h然后更新直径相同的情况题目说直径比它大所以直径相同的不会互相影响。排序时直径相同的放一起遍历时会自然处理为什么dh[i][1] max_h后要max_h max(max_h, dh[i][1])其实dh[i][1] max_h时max_h dh[i][1]就行但为了代码简洁统一写max1.6 进一步优化思考原代码有个细节max_hmax(max_h,dh[i][1])ifdh[i][1]max_h:ans1这里先更新max_h再判断逻辑等价于ifdh[i][1]max_h:ans1max_hdh[i][1]else:max_hmax_h# 不变因为max_h更新后dh[i][1] max_h仍然成立max_h要么不变要么变小… 不对max_h max(max_h, dh[i][1])会让max_h变大或不变。实际上原代码的逻辑是先更新max_h max(max_h, dh[i][1])然后判断dh[i][1] max_h如果dh[i][1] max_h旧则max_h更新为dh[i][1]然后dh[i][1] max_h成立等于。如果dh[i][1] max_h旧则max_h不变dh[i][1] max_h成立等于。如果dh[i][1] max_h旧则max_h不变dh[i][1] max_h不成立。所以原代码等价于if dh[i][1] max_h_old: ans 1; max_h max(max_h_old, dh[i][1])逻辑正确。但建议写成更清晰的形式foriinrange(1,n):ifdh[i][1]max_h:ans1max_hdh[i][1]二、封闭图形个数2.1 题目描述蓝桥王国的数字大小规则很特别一个数字的大小由它的封闭图形个数决定。每个数字的封闭图形个数0, 4, 6, 91个82个1, 2, 3, 5, 70个排序规则封闭图形个数少的排在前面如果个数相同数字本身小的排在前面给定n个数字按此规则排序输出。2.2 关键思路多关键字排序核心自定义比较函数先比封闭图形个数个数相同再比数值大小。Python实现使用functools.cmp_to_key将比较函数转为key函数。2.3 推演验证输入: n3, a[18, 29, 6] 计算封闭图形个数 18: 1(1个) 0(8有2个?) 等等重新算 1: 0个, 8: 2个 → 18有2个 2: 0个, 9: 1个 → 29有1个 6: 1个 → 6有1个 排序 29: 1个 6: 1个个数相同629所以6在前 18: 2个 输出: 6 29 18 ✓2.4 题解fromfunctoolsimportcmp_to_key# 每个数字的封闭图形个数ls[1,0,0,0,1,0,1,0,2,1]# 索引: 0 1 2 3 4 5 6 7 8 9nint(input())alist(map(int,input().split()))defcompare(a,b): 比较函数返回负数表示aba排前面正数表示ab0表示相等 # 计算a的封闭图形个数numasum([ls[int(i)]foriinstr(a)])# 计算b的封闭图形个数numbsum([ls[int(i)]foriinstr(b)])# 先比封闭图形个数ifnumanumb:return-1elifnumanumb:return1# 个数相同比数字本身大小ifab:return-1elifab:return1else:return0# 使用cmp_to_key进行自定义排序a.sort(keycmp_to_key(compare))print(*a)复杂度时间O(n log n × digit)digit是数字位数通常很小空间O(n)2.5 关键细节坑点说明cmp_to_keyPython3 取消了sort(cmp...)必须用functools.cmp_to_key比较函数返回值返回负数表示aba排前面不是返回True/False数字转字符串str(a)拆分成每一位再转int查表ls数组索引ls[0]10有1个封闭图形ls[8]28有2个负数处理如果输入有负数str(-5)会得到-5int(-)会报错。但题目说正整数不用考虑2.6 优化版本预计算如果n很大每次比较都计算封闭图形个数会重复。可以预计算fromfunctoolsimportcmp_to_key ls[1,0,0,0,1,0,1,0,2,1]nint(input())alist(map(int,input().split()))# 预计算每个数字的封闭图形个数circle_count{}fornumina:ifnumnotincircle_count:circle_count[num]sum(ls[int(i)]foriinstr(num))defcompare(a,b):ca,cbcircle_count[a],circle_count[b]ifca!cb:return-1ifcacbelse1return-1ifabelse(1ifabelse0)a.sort(keycmp_to_key(compare))print(*a)三、摆玩具2.1 题目描述小蓝有n个玩具按高度从矮到高摆放在窗台上。他想分成k段使得所有分段的极差之和尽可能小。极差一段中最高和最矮的高度之差。输入n, k和高度数组h已排序输出最小极差和3.2 关键思路差分贪心选最大间隙核心观察数组已经升序排列如果不分段k1极差和 h[n-1] - h[0]整体极差如果分成k段需要在k-1个位置切断切断的位置相邻两个玩具的高度差越大切断后省下的极差越多贪心策略计算所有相邻高度差diff[i] h[i] - h[i-1]选择最大的k-1个差值作为切断点最小极差和 总极差 - 最大的k-1个差值之和为什么整体极差 h[n-1] - h[0] diff[1] diff[2] ... diff[n-1]如果在diff[i]处切断这一段对总极差的贡献就变成0因为被分成了两段各自计算极差所以要让总极差最小就要让省下的极差最大即选择最大的k-1个diff3.3 推演验证输入: n5, k2, h[2, 5, 7, 10, 13] 相邻差值: diff [3, 2, 3, 3] (5-23, 7-52, 10-73, 13-103) k2需要选1个最大差值切断 最大差值 3有3个都是3任选一个 如果不切断极差 13-2 11 切断后比如在第一个3处切断 段1: [2,5], 极差3 段2: [7,10,13], 极差6 总和 36 9 用公式总极差 - 最大差值 11 - 3 8? 不对... 等等重新理解 整体极差 13-2 11 diff总和 3233 11 ✓ 如果在diff[0]3处切断即在2和5之间切断 段1: [2], 极差0 段2: [5,7,10,13], 极差8 总和 08 8 用公式总极差 - 切断的差值 11 - 3 8 ✓ 样例输出是8 ✓3.4 题解n,kmap(int,input().split())hlist(map(int,input().split()))# 已经按高度排序题目说从矮到高摆放h.sort()# 计算相邻差值diff[]foriinrange(1,n):diff.append(h[i]-h[i-1])# 贪心选最大的k-1个差值作为切断点diff.sort(reverseTrue)# 总极差 最后一个 - 第一个 h[n-1] - h[0]# 也可以 sum(diff)totalh[-1]-h[0]# 减去最大的k-1个差值foriinrange(k-1):total-diff[i]print(total)更简洁的版本n,kmap(int,input().split())hlist(map(int,input().split()))h.sort()diff[h[i]-h[i-1]foriinrange(1,n)]diff.sort(reverseTrue)# 或者直接 sum(diff[k-1:])print(sum(diff[k-1:]))复杂度时间O(n log n)排序空间O(n)3.5 关键细节坑点说明h.sort()题目说从矮到高但输入不一定有序必须排序diff长度n-1个差值k段需要k-1个切断点k1的情况range(0)不执行循环total不变正确kn的情况每个玩具一段极差和为0。diff选n-1个剩下0个sum([])0✓排序方向diff.sort(reverseTrue)降序选前k-1个最大的3.6 本质理解整体极差 diff[0] diff[1] ... diff[n-2] 分成k段 选k-1个位置切断 切断后这k-1个diff不再计入总极差 所以最小极差和 sum(diff) - max(k-1个diff) 剩余(n-k)个diff的和这就是代码sum(diff[k-1:])的含义去掉最大的k-1个剩下的求和。四、小蓝的零花钱4.1 题目描述小蓝有一个长度为n的序列奇数和偶数的数量相等。他可以在某个位置切割将序列分成两段要求每段中奇数和偶数的数量都相等。切割的代价 切割位置两端元素的差的绝对值|a[i] - a[i1]|。小蓝有B元零花钱求最多能切割几次。输入n, B和序列a输出最多切割次数4.2 关键思路前缀和判平衡贪心选最小代价第一步判断可切割位置什么位置可以切割切割后左边一段奇偶数量相等右边一段奇偶数量相等因为整体奇偶数量相等所以如果左边相等右边一定也相等证明设整体有E个偶数O个奇数E O左边有e个偶数o个奇数若e o右边有E-e个偶数O-o个奇数因为EO且eo所以E-e O-o右边也相等 ✓所以只需要判断前缀中奇数和偶数是否相等第二步用前缀和找切割点遍历序列维护cnt遇到偶数1遇到奇数-1当cnt 0时说明当前位置前缀中奇偶数量相等可以切割切割代价 |a[i] - a[i1]|第三步贪心选择可能有多个可切割位置每个位置有不同的代价要最大化切割次数就要优先选择代价小的位置将所有可切割位置的代价排序从小到大选直到预算用完4.3 推演验证输入: n6, B3, a[1, 2, 3, 4, 5, 6] 遍历找切割点 i0: a[0]1(奇), cnt-1 i1: a[1]2(偶), cnt-110 → 可以切割代价|2-3|1 i2: a[2]3(奇), cnt0-1-1 i3: a[3]4(偶), cnt-110 → 可以切割代价|4-5|1 i4: a[4]5(奇), cnt0-1-1 可切割位置: [1, 1]代价都是1 排序: [1, 1] B3: 选第一个: B3-12, ans1 选第二个: B2-11, ans2 输出: 2 ✓4.4 题解n,bmap(int,input().split())alist(map(int,input().split()))cnt0# 前缀中(偶数个数 - 奇数个数)为0表示奇偶数量相等res[]# 存储所有可切割位置的代价# 遍历到n-2保证i1不越界foriinrange(n-1):ifa[i]%20:cnt1else:cnt-1# 前缀奇偶数量相等可以在这里切割ifcnt0:res.append(abs(a[i]-a[i1]))# 贪心优先选择代价小的res.sort()ans0forcostinres:ifbcost:# 注意原代码是 不是 严格大于才切割b-cost ans1else:breakprint(ans)复杂度时间O(n log n)排序res空间O(n)4.5 关键细节坑点说明cnt的更新偶数1奇数-1不是反过来cnt 0的含义前缀中偶数个数 奇数个数可以切割切割位置在i和i1之间切割代价是 b cost还是b cost原代码是严格大于。如果b cost不切割切割后b0但代码逻辑是不切range(n-1)遍历到倒数第二个元素因为切割需要i1为什么整体奇偶相等就能保证前缀和为0时左边奇偶相等整体奇偶相等所以右边也相等4.6 进一步优化如果n很大但B很小可以用**优先队列最小堆**动态维护但本题n ≤ 100直接排序即可。边界情况n2只有一个切割位置如果奇偶各一个没有可切割位置res为空输出0 今日复盘总结题目核心技巧思维路径易错点国赛价值独特瓷器排序逆向维护最值直径降序→从大到小遍历→维护最大高度排序方向、初始ans1、max_h更新时机⭐⭐⭐ 经典贪心封闭图形个数自定义排序数位拆分→查表→多关键字排序cmp_to_key用法、比较函数返回值⭐⭐⭐ 基础技巧摆玩具差分贪心选最大间隙升序排列→算相邻差→选最大k-1个切断diff长度n-1、排序方向、sum(diff[k-1:])⭐⭐⭐⭐ 差分思想小蓝的零花钱前缀和判平衡贪心选最小偶1奇-1→cnt0可切→代价排序从小到大cnt更新方向、bcost不是、range(n-1)⭐⭐⭐⭐ 综合应用