一、例题精讲例题 1三带一项目内容类型字符串 模拟核心统计字符出现次数判断是否为AAAB型题目描述小蓝和小桥玩斗地主小蓝只剩四张牌了判断是否是三带一牌型。三带一四张手牌中有三张一样另外一张不与其他牌相同即AAAB型。输入T TT轮每轮一个长度为4的字符串输出每轮输出Yes或No关键思路判断逻辑去重后只有2种字符len(set(s)) 2其中一种出现1次或3次s.count(s[0]) 1 or s.count(s[0]) 3为什么这样判断因为四张牌只有两种字符如果第一种出现1次第二种必出现3次如果第一种出现3次第二种必出现1次。两种情况都是三带一推演验证输入: 222K set(222K) {2, K} → len2 ✓ 222K.count(2) 3 → 满足条件 ✓ 输出: Yes ✓ 输入: 2233 set(2233) {2, 3} → len2 ✓ 2233.count(2) 2 → 不满足条件 ✗ 输出: No ✓题解tint(input())for_inrange(t):sinput()# 去重后只有2种字符且其中一种出现1次或3次iflen(set(s))2and(s.count(s[0])1ors.count(s[0])3):print(Yes)else:print(No)复杂度时间O ( T × 4 ) O(T \times 4)O(T×4)空间O ( 1 ) O(1)O(1)关键细节坑点说明s.count(s[0])统计第一个字符出现次数利用对称性判断len(set(s))2必须恰好2种字符1种AAAA或3种都不行或运算的优先级and优先级高于or需要加括号例题 2DNA序列修正 ⭐重点项目内容类型贪心 模拟核心优先交换修正两个位置无法交换则替换题目描述两条DNA序列需要让第二条与第一条互补A-T, C-G。操作规则选择第二条DNA的任意两个位置交换他们的字符一次修正两个位置选择第二条DNA任意一个位置替换为A/C/G/T中的一个一次修正一个位置限制每个位置上的碱基只能被操作一次目标求最小操作次数。关键思路贪心策略能交换就不替换交换操作一次可以修正两个位置代价为1替换操作一次只能修正一个位置代价为1所以优先尝试交换无法交换的位置再用替换。交换条件对于位置i ii和j jjb [ i ] b[i]b[i]应该是a [ i ] a[i]a[i]的互补碱基b [ j ] b[j]b[j]应该是a [ j ] a[j]a[j]的互补碱基交换后b [ i ] b[i]b[i]变成d i c [ a [ i ] ] dic[a[i]]dic[a[i]]且b [ j ] b[j]b[j]变成d i c [ a [ j ] ] dic[a[j]]dic[a[j]]即b[j] dic[a[i]]且b[i] dic[a[j]]推演验证输入: N5 a ACGTG b ACGTC dic {A:T,T:A,C:G,G:C} 位置0: a[0]A, dic[A]T, b[0]A ≠ T ❌ 位置1: a[1]C, dic[C]G, b[1]C ≠ G ❌ 位置2: a[2]G, dic[G]C, b[2]G ≠ C ❌ 位置3: a[3]T, dic[T]A, b[3]T ≠ A ❌ 位置4: a[4]G, dic[G]C, b[4]C C ✓ 遍历位置0 找j0满足 b[j]dic[a[0]]T 且 b[0]dic[a[j]] j3: b[3]T dic[A]T ✓, b[0]A dic[T]A ✓ 交换b[0]和b[3]: b变成 TCGCA ans1 遍历位置1 b[1]C ≠ dic[C]G ❌ 找j1满足条件... 找不到 ans2 (替换) 等等这样得到2但样例输出是2... ✓ 实际上位置1和位置2也可以交换 b[1]C, b[2]G 交换后: b[1]G(✓), b[2]C(✓) ans2 ✓题解Nint(input())alist(input())blist(input())dic_of_DNA{A:T,T:A,C:G,G:C}ans0foriinrange(N):ifb[i]!dic_of_DNA[a[i]]:# 位置i不匹配# 贪心优先找可以交换的位置jforjinrange(i1,N):# 交换条件b[j]是a[i]的互补且b[i]是a[j]的互补ifb[j]dic_of_DNA[a[i]]andb[i]dic_of_DNA[a[j]]:b[i],b[j]b[j],b[i]# 交换break# 找到就退出ans1# 一次操作交换或替换print(ans)复杂度时间O ( N 2 ) O(N^2)O(N2)空间O ( 1 ) O(1)O(1)关键细节坑点说明交换条件b[j]dic[a[i]] and b[i]dic[a[j]]必须双向满足break的重要性找到交换对象后立即break避免重复操作ans统计无论交换还是替换ans都1因为都是一次操作贪心正确性交换一次修两个替换一次修一个优先交换一定最优例题 3计算函数值 ⭐数学转化项目内容类型递归 数学核心发现规律$S(x) $ 二进制中1的个数 1 11题目描述神秘函数S ( x ) S(x)S(x)定义S ( 0 ) 1 S(0) 1S(0)1x xx为偶数S ( x ) S ( x / 2 ) S(x) S(x/2)S(x)S(x/2)x xx为奇数S ( x ) S ( x − 1 ) 1 S(x) S(x-1) 1S(x)S(x−1)1求S ( x ) S(x)S(x)的值。关键思路手动推演找规律S(0) 1 S(1) S(0) 1 2 S(2) S(1) 2 S(3) S(2) 1 3 S(4) S(2) 2 S(5) S(4) 1 3 S(6) S(3) 3 S(7) S(6) 1 4发现规律x二进制S(x)二进制1的个数0010 11121 121021 131132 1410021 1510132 1611032 1711143 1结论$S(x) $二进制表示中1的个数 1 11推演验证样例输入: x7 7 1111的个数 3 S(7) 3 1 4 ✓ 递归验证 S(7) S(6) 1 S(3) 1 S(2) 1 1 S(1) 2 S(0) 1 2 1 3 4 ✓题解解法一直接递归题目给定范围x ≤ 10 6 x \leq 10^6x≤106递归深度最多20层xint(input())defsm(x):ifx0:return1ifx%20:returnsm(x//2)else:returnsm(x-1)1print(sm(x))解法二利用二进制性质O ( log ⁡ x ) O(\log x)O(logx)xint(input())# S(x) 二进制1的个数 1print(bin(x).count(1)1)复杂度递归版时间O ( log ⁡ x ) O(\log x)O(logx)递归深度空间O ( log ⁡ x ) O(\log x)O(logx)递归栈二进制版时间O ( log ⁡ x ) O(\log x)O(logx)空间O ( 1 ) O(1)O(1)关键细节坑点说明递归终止条件x0返回1不是0奇偶判断先判断偶数x%20因为0也是偶数数学规律发现S ( x ) p o p c o u n t ( x ) 1 S(x) popcount(x) 1S(x)popcount(x)1可以极大简化代码例题 4穿越时空之门 ⭐进制转换项目内容类型进制转换 枚举核心二进制数位之和 四进制数位之和题目描述计算1到2024中有多少个数满足二进制表示中各数位之和四进制表示中各数位之和。关键思路进制转换方法二进制bin(n)返回0b1010去掉前缀后求各位数字和四进制不断除以4取余直到商为0四进制转换过程以 6 为例 6 ÷ 4 1 ... 2 1 ÷ 4 0 ... 1 所以 6 的四进制 12数位和 1 2 3 6 的二进制 110数位和 1 1 0 2 不相等推演验证i1: 二进制1(和1), 四进制1(和1) → 相等 ✓ i2: 二进制10(和1), 四进制2(和2) → 不相等 i3: 二进制11(和2), 四进制3(和3) → 不相等 i4: 二进制100(和1), 四进制10(和1) → 相等 ✓ i5: 二进制101(和2), 四进制11(和2) → 相等 ✓题解defbase4(s):求四进制表示的数位之和l[]whiles4:s,bdivmod(s,4)# s商, b余数l.append(b)l.append(s)# 最后的商returnsum(l)defbase2(s):求二进制表示的数位之和# bin(5) 0b101, split(b)[1] 101returnsum(list(map(int,bin(s).split(b)[1])))ans0foriinrange(1,2025):ifbase2(i)base4(i):ans1print(ans)复杂度时间O ( 2024 × log ⁡ 2024 ) O(2024 \times \log 2024)O(2024×log2024)空间O ( 1 ) O(1)O(1)关键细节坑点说明divmod(s, 4)同时返回商和余数避免两次运算bin(s).split(b)[1]去掉0b前缀获取纯二进制字符串范围range(1, 2025)包含1到2024四进制最后一步循环结束后s4直接加入列表例题 5依依的画作项目内容类型字符串 模拟核心前一个的个位 ! 后一个的十位题目描述N NN个两位正整数统计有多少对相邻数字不遵循规则前一个的个位应该等于后一个的十位。关键思路字符串索引个位a[i][1]字符串的第二个字符十位a[i1][0]字符串的第一个字符统计遍历0 00到N − 2 N-2N−2统计a[i][1] ! a[i1][0]的次数。推演验证输入: 5 66 13 22 55 98 i0: 66[1]6, 13[0]1 → 6≠1 ❌ 不遵循 i1: 13[1]3, 22[0]2 → 3≠2 ❌ 不遵循 i2: 22[1]2, 55[0]5 → 2≠5 ❌ 不遵循 i3: 55[1]5, 98[0]9 → 5≠9 ❌ 不遵循 总共4对不遵循 输出: 4 ✓题解nint(input())alist(map(str,input().split()))# 统计不遵循规则的相邻对数print(sum(1foriinrange(n-1)ifa[i][1]!a[i1][0]))复杂度时间O ( N ) O(N)O(N)空间O ( 1 ) O(1)O(1)关键细节坑点说明字符串索引a[i][1]是个位a[i1][0]是十位map(str, ...)输入直接当字符串处理避免转int再转str遍历范围range(n-1)最后一对是a[n-2]和a[n-1]简洁写法sum(1 for ... if ...)是Pythonic的计数方式二、今日刷题总结题号题目考点难度核心技巧1三带一字符串统计⭐⭐set()去重 count()计数2DNA序列修正贪心模拟⭐⭐⭐优先交换双向匹配条件3计算函数值递归数学⭐⭐⭐发现规律p o p c o u n t ( x ) 1 popcount(x) 1popcount(x)14穿越时空之门进制转换⭐⭐⭐divmod()bin()5依依的画作字符串索引⭐⭐字符串索引 生成器表达式模拟题解题模板# 模板1字符统计类cnt{}forcins:cnt[c]cnt.get(c,0)1# 或直接用 collections.Counter# 模板2贪心交换类foriinrange(n):ifnotmatch(i):forjinrange(i1,n):ifcan_swap(i,j):swap(i,j)breakans1# 模板3进制转换类defto_base(n,base):将n转换为base进制返回数位列表digits[]whilenbase:n,rdivmod(n,base)digits.append(r)digits.append(n)returndigits[::-1]# 反转得到正序# 模板4字符串索引类# 两位数的个位和十位unitss[1]# 个位tenss[0]# 十位三、结语模拟题是蓝桥杯的送分题但也是丢分重灾区。今天的5道题告诉我们今日收获字符串处理要熟练set()、count()、索引访问贪心思想能交换就不替换能一次解决就不分两次数学观察递归函数先手动算几项找规律进制转换divmod()和bin()是利器Pythonic写法sum(1 for ... if ...)简洁高效模拟题没有固定的算法模板但有固定的解题套路读题→找规律→写代码→验证。多练多总结国赛模拟题全AC不是梦如果本文对你有帮助欢迎点赞 收藏 ⭐ 关注 你的支持是我持续更新的动力