备战蓝桥杯国赛【Day 7】

例题 1装船问题蓝桥杯 P532项目内容链接https://www.lanqiao.cn/problems/532/learning/类型反向扫描 贪心核心最轻配最重能装一起装题目描述船载重wn个货物每次最多装两件和 w。求最少运输次数。输入输出输入w, n, 然后n个货物重量 输出最少运输次数贪心证明设最轻为a最重为b。若a b w则a和任何货都能配对其他货 b。所以a和b配对最优不浪费a的配对能力。若a b w则b无法和任何货配对b必须单独运。完整代码wint(input())nint(input())p[int(input())for_inrange(n)]p.sort()l,r0,n-1ans0whileTrue:iflr:ans1breakiflr:breakifp[l]p[r]w:l1r-1ans1else:r-1ans1print(ans)推演过程w10, p[1,2,8,9] 排序: [1,2,8,9] l0(1), r3(9): 191010 → 配对, ans1, l1,r2 l1(2), r2(8): 281010 → 配对, ans2, l2,r1 l2r1 → 结束 输出: 2 ✓复杂度指标复杂度说明时间O(n log n)排序 双指针空间O(1)原地操作易错点错误后果修正忘记排序双指针失效必须先sort()l r放l r后面死循环或漏算先判l r例题 2回文判断蓝桥杯 P1371项目内容链接https://www.lanqiao.cn/problems/1371/learning/类型反向扫描核心两头逐位比较题目描述判断字符串s是否为回文。两种写法对比写法1切片简洁但费空间sinput()print(Yifss[::-1]elseN)写法2双指针竞赛推荐O(1)空间sinput()l,r0,len(s)-1okYwhilelr:ifs[l]!s[r]:okNbreakl1r-1print(ok)复杂度对比写法时间空间适用切片O(n)O(n)快速验证双指针O(n)O(1)竞赛、大数据例题 3最小长度子数组蓝桥杯 P1372项目内容链接https://www.lanqiao.cn/problems/1372/learning/类型滑动窗口核心右扩左缩维护区间和题目描述给定数组a和整数s找和 s的最短连续子数组长度。关键细节左闭右开[l, r)r指向下一个待加入的元素区间长度 r - l无需1收缩时total - a[l]l 1逻辑清晰完整代码n,smap(int,input().split())alist(map(int,input().split()))min_lenn1l,r0,0total0whileln:whilernandtotals:totala[r]r1iftotals:min_lenmin(min_len,r-l)total-a[l]l1print(min_lenifmin_lennelse0)推演过程状态表n5, s7, a[2,3,1,2,4] 轮次 | l | r | total | 操作 | min_len :---:|:---:|:---:|:---|:---|:---: 初始 | 0 | 0 | 0 | - | 6 1 | 0 | 4 | 8 | 扩到r3,total87 | min(6,4)4 | 1 | 4 | 6 | 减a[0]2 | - 2 | 1 | 5 | 10 | 扩到r4,total107 | min(4,4)4 | 2 | 5 | 7 | 减a[1]3 | - 3 | 2 | 5 | 7 | total7,不扩 | min(4,3)3 | 3 | 5 | 6 | 减a[2]1 | - 4 | 3 | 5 | 6 | r到头 | - | 4 | 5 | 4 | 减a[3]2 | - 5 | 4 | 5 | 4 | r到头 | - | 5 | 5 | 0 | 减a[4]4 | 结束 输出: 3 (子数组 [1,2,4])为什么是 O(n)l和r都只往右走不回退。每个元素被访问两次总2n次操作。例题 4恰好 k 个蓝桥杯 P1621—— 重点变形题项目内容链接https://www.lanqiao.cn/problems/1621/learning/类型滑动窗口 容斥转化核心“恰好k个” “至少k个” - “至少(k1)个”题目描述求有多少个子数组满足区间中恰好有 k 个数字 m。为什么需要容斥直接求恰好k个很困难滑动窗口天然维护至少关系。利用容斥恰好k个 至少k个 - 至少(k1)个辅助函数求至少k个defat_least_k(a,n,m,k):求子数组中 m 的元素个数至少为 k 的个数ifk0:returnn*(n1)//2left,right0,0cnt0ans0whileleftn:whilerightnandcntk:ifa[right]m:cnt1right1ifcntk:ansn-right1else:breakifa[left]m:cnt-1left1returnans主函数n,m,kmap(int,input().split())alist(map(int,input().split()))ansat_least_k(a,n,m,k)-at_least_k(a,n,m,k1)print(ans)推演验证n5, m3, k2, a[1,3,2,4,3] at_least_k(2): l0,r0,cnt0 扩: r1,cnt1; r2,cnt1; r3,cnt2,r4 ans2 ([0,3],[0,4]), 缩l1,cnt2 ans2 ([1,3],[1,4]), 缩l2,cnt1 扩: r4,cnt2,r5 ans1 ([2,4]), 缩l3,cnt2 ans1 ([3,4]), 缩l4,cnt1 扩: cnt12,r5到头,结束 at_least_k(2) 6 at_least_k(3): 扩: r4,cnt3,r5 ans1 ([0,4]), 缩l1,cnt3 ans1 ([1,4]), 缩l2,cnt2 扩: cnt23,结束 at_least_k(3) 2 恰好2个 6 - 2 4 ✓关键洞察原题直接写法容斥写法适用场景ans n - right 1at_least_k(k) - at_least_k(k1)原题数据弱可能过但严谨要容斥认为找到k个就合法严格恰好需要减比赛时看题意至少直接写恰好用容斥例题 5近似 gcd项目内容来源https://www.lanqiao.cn/problems/2209/learning/类型滑动窗口 计数核心窗口内最多一个元素不是 g 的倍数题目描述给定数组a和整数g求有多少个子数组满足区间内最多只有一个元素不是g的倍数且长度 2。思路分析滑动窗口维护窗口内不是g倍数的元素个数cnt。cnt 1时窗口合法cnt 1时收缩左边界直到cnt 1统计子数组对于每个右端点j以j结尾的合法子数组有j - i个i为最左合法位置且长度需 2。完整代码n,gmap(int,input().split())alist(map(int,input().split()))i0# 左指针cnt0# 窗口内不是g倍数的元素个数ans0forjinrange(n):# 右指针ifa[j]%g!0:cnt1# 收缩左边界直到最多一个不是g的倍数whilecnt1:ifa[i]%g!0:cnt-1i1# 以j结尾的合法子数组从i到j-1开始共 j-i 个长度2ifj-i1:# 确保子数组长度至少为2ansj-iprint(ans)推演验证n5, g2, a[1,2,3,4,5] j0: a[0]1%2!0, cnt1, i0, j-i01, 不统计 j1: a[1]2%20, cnt1, i0, j-i11, ans1 ([0,1]) j2: a[2]3%2!0, cnt2, 收缩: i0,a[0]1%2!0,cnt1,i1 cnt1, j-i11, ans1 ([1,2]) j3: a[3]4%20, cnt1, i1, j-i21, ans2 ([1,3],[2,3]) j4: a[4]5%2!0, cnt2, 收缩: i1,a[1]2%20,cnt2; i2,a[2]3%2!0,cnt1,i3 cnt1, j-i11, ans1 ([3,4]) ans 1121 5 验证所有长度2的子数组: [0,1][1,2]: 1不是2倍数 → 1个 ✓ [0,2][1,2,3]: 1,3不是 → 2个 ✗ [1,2][2,3]: 3不是 → 1个 ✓ [1,3][2,3,4]: 3不是 → 1个 ✓ [2,3][3,4]: 3不是 → 1个 ✓ [3,4][4,5]: 5不是 → 1个 ✓ 共5个 ✓复杂度分析指标复杂度说明时间O(n)双指针各走一遍空间O(1)只维护计数器例题 6日志统计蓝桥杯 P179项目内容来源https://www.lanqiao.cn/problems/179/learning/类型滑动窗口 哈希计数核心时间窗口内统计点赞数判断热帖题目描述小明维护着一个程序员论坛。现在他收集了一份点赞日志日志共有N行。每一行的格式是ts id表示在ts时刻编号id的帖子收到一个赞。如果一个帖子曾在任意一个长度为D的时间段内收到不少于K个赞就认为该帖子曾是热帖。具体来说如果存在某个时刻T满足该帖在[T, TD)这段时间内左闭右开区间收到不少于K个赞该帖就曾是热帖。给定日志统计所有曾是热帖的帖子编号按从小到大顺序输出。输入格式N D K ts1 id1 ts2 id2 ... tsN idN输出格式每行一个热帖id按从小到大顺序。样例输入7 10 2 0 1 0 10 10 10 10 1 9 1 100 3 100 3输出1 3题解关键观察日志按时间排序后对于每条日志i以它为右端点维护一个时间窗口[j, i]使得ts[i] - ts[j] D。窗口内统计每个id的点赞数。双指针i遍历所有日志右指针j维护窗口左边界。当ts[i] - ts[j] D时j右移收缩窗口。inputsys.stdin.readline n,d,kmap(int,input().split())# 读取日志logs[]for_inrange(n):ts,idmap(int,input().split())logs.append((ts,id))# 按时间排序logs.sort(keylambdax:x[0])cnt{}# 窗口内每个id的点赞数hotset()# 热帖集合j0# 左指针foriinrange(n):# 右指针ts_i,id_ilogs[i]# 当前日志进入窗口cnt[id_i]cnt.get(id_i,0)1# 收缩左边界维护时间窗口 [j, i] 满足 ts[i] - ts[j] dwhilejiandts_i-logs[j][0]d:ts_j,id_jlogs[j]cnt[id_j]-1ifcnt[id_j]0:delcnt[id_j]j1# 判断当前id是否为热帖ifcnt.get(id_i,0)k:hot.add(id_i)# 按顺序输出foridinsorted(hot):print(id)推演过程可视化输入: 7 10 2 日志: [(0,1), (0,10), (9,1), (10,10), (10,1), (100,3), (100,3)] 排序后: [(0,1), (0,10), (9,1), (10,10), (10,1), (100,3), (100,3)] i0: ts0, id1, cnt{1:1} j0, 0-0010, 不收缩 cnt[1]12, 不是热帖 i1: ts0, id10, cnt{1:1, 10:1} j0, 0-0010, 不收缩 cnt[10]12, 不是热帖 i2: ts9, id1, cnt{1:2, 10:1} j0, 9-0910, 不收缩 cnt[1]22 → hot.add(1) ✓ i3: ts10, id10, cnt{1:2, 10:2} j0, 10-01010, 收缩! j0: 出(0,1), cnt{1:1, 10:2}, j1 j1: 10-01010, 收缩! j1: 出(0,10), cnt{1:1, 10:1}, j2 j2: 10-9110, 停止 cnt[10]12, 不是热帖 (但之前窗口内有2个10已经被统计过) i4: ts10, id1, cnt{1:2, 10:1} j2, 10-9110, 不收缩 cnt[1]22 → hot.add(1) (已在集合中) i5: ts100, id3, cnt{1:2, 10:1, 3:1} j2, 100-99110, 大幅收缩... ... 一直收缩到 j5 j5: 100-100010, 停止 cnt{3:1}, cnt[3]12, 不是热帖 i6: ts100, id3, cnt{3:2} j5, 100-100010, 不收缩 cnt[3]22 → hot.add(3) ✓ 输出: 1, 3 (排序后)复杂度分析指标复杂度说明时间O(n log n)排序O(n log n) 双指针O(n)空间O(n)存储日志 哈希表计数关键易错点坑点说明修正左闭右开区间[T, TD)即ts[i] - ts[j] D时j要出窗口while ts_i - logs[j][0] d先加后减当前日志先进入窗口再收缩顺序不能反输出排序题目要求按id从小到大输出最后sorted(hot)计数为0要删除防止哈希表无限增长if cnt[id_j] 0: del cnt[id_j]与例题3P1372的对比对比项P1372 最短子数组P179 日志统计窗口维护区间和 s时间差 D收缩条件total s后收缩左边界ts[i] - ts[j] D时收缩统计对象子数组长度每个id的出现次数数据结构变量total哈希表cnt答案更新min_lenhot集合 今日刷题总结题号考点双指针类型难度核心技巧P532装船配对反向扫描⭐⭐贪心证明、排序后两头凑P1371回文判断反向扫描⭐双指针O(1)空间P1372最短子数组滑动窗口⭐⭐⭐左闭右开、右扩左缩P1621恰好k个滑动窗口容斥⭐⭐⭐⭐“恰好转至少减至少k1”P8809近似GCD滑动窗口计数⭐⭐⭐⭐窗口内最多一个不满足P179日志统计滑动窗口哈希⭐⭐⭐⭐时间窗口、左闭右开、哈希计数