备战蓝桥杯国赛【Day 10】

一、例题精讲

例题 1：三带一

题目描述

小蓝和小桥玩斗地主，小蓝只剩四张牌了，判断是否是"三带一"牌型。

三带一：四张手牌中，有三张一样，另外一张不与其他牌相同，即AAAB型。

输入：T TT轮，每轮一个长度为4的字符串

输出：每轮输出Yes或No

关键思路

判断逻辑：

1. 去重后只有2种字符（len(set(s)) == 2）
2. 其中一种出现1次或3次（s.count(s[0]) == 1 or s.count(s[0]) == 3）

💡为什么这样判断？因为四张牌只有两种字符，如果第一种出现1次，第二种必出现3次；如果第一种出现3次，第二种必出现1次。两种情况都是三带一！

推演验证

输入: 222K set('222K') = {'2', 'K'} → len=2 ✓ '222K'.count('2') = 3 → 满足条件 ✓ 输出: Yes ✓ 输入: 2233 set('2233') = {'2', '3'} → len=2 ✓ '2233'.count('2') = 2 → 不满足条件 ✗ 输出: No ✓

题解

t=int(input())for_inrange(t):s=input()# 去重后只有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)

关键细节

例题 2：DNA序列修正 ⭐重点

题目描述

两条DNA序列，需要让第二条与第一条互补（A-T, C-G）。

操作规则：

1. 选择第二条DNA的任意两个位置，交换他们的字符（一次修正两个位置）
2. 选择第二条DNA任意一个位置，替换为A/C/G/T中的一个（一次修正一个位置）

限制：每个位置上的碱基只能被操作一次！

目标：求最小操作次数。

关键思路

贪心策略：能交换就不替换！

• 交换操作：一次可以修正两个位置，代价为1
• 替换操作：一次只能修正一个位置，代价为1

所以优先尝试交换，无法交换的位置再用替换。

交换条件：对于位置i ii和j jj：

• b [ 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]]

推演验证

输入: N=5 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： 找j>0满足 b[j]==dic[a[0]]=T 且 b[0]==dic[a[j]] j=3: b[3]=T == dic[A]=T ✓, b[0]=A == dic[T]=A ✓ 交换b[0]和b[3]: b变成 TCGCA ans=1 遍历位置1： b[1]=C ≠ dic[C]=G ❌ 找j>1满足条件... 找不到 ans=2 (替换) 等等，这样得到2，但样例输出是2... ✓ 实际上位置1和位置2也可以交换： b[1]=C, b[2]=G 交换后: b[1]=G(✓), b[2]=C(✓) ans=2 ✓

题解

N=int(input())a=list(input())b=list(input())dic_of_DNA={'A':'T','T':'A','C':'G','G':'C'}ans=0foriinrange(N):ifb[i]!=dic_of_DNA[a[i]]:# 位置i不匹配# 贪心：优先找可以交换的位置jforjinrange(i+1,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# 找到就退出ans+=1# 一次操作（交换或替换）print(ans)

复杂度：时间O ( N 2 ) O(N^2)O(N2)，空间O ( 1 ) O(1)O(1)

关键细节

例题 3：计算函数值 ⭐数学转化

题目描述

神秘函数S ( x ) S(x)S(x)定义：

• S ( 0 ) = 1 S(0) = 1S(0)=1
• x 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

发现规律：

结论：$S(x) = $二进制表示中1的个数+ 1 + 1+1

推演验证（样例）

输入: x=7 7 = 111，1的个数 = 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层）

x=int(input())defsm(x):ifx==0:return1ifx%2==0:returnsm(x//2)else:returnsm(x-1)+1print(sm(x))

解法二：利用二进制性质（O ( log ⁡ x ) O(\log x)O(logx)）

x=int(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)

关键细节

例题 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 不相等！

推演验证

i=1: 二进制=1(和=1), 四进制=1(和=1) → 相等 ✓ i=2: 二进制=10(和=1), 四进制=2(和=2) → 不相等 i=3: 二进制=11(和=2), 四进制=3(和=3) → 不相等 i=4: 二进制=100(和=1), 四进制=10(和=1) → 相等 ✓ i=5: 二进制=101(和=2), 四进制=11(和=2) → 相等 ✓

题解

defbase4(s):"""求四进制表示的数位之和"""l=[]whiles>=4:s,b=divmod(s,4)# s=商, b=余数l.append(b)l.append(s)# 最后的商returnsum(l)defbase2(s):"""求二进制表示的数位之和"""# bin(5) = '0b101', split('b')[1] = '101'returnsum(list(map(int,bin(s).split('b')[1])))ans=0foriinrange(1,2025):ifbase2(i)==base4(i):ans+=1print(ans)

复杂度：时间O ( 2024 × log ⁡ 2024 ) O(2024 \times \log 2024)O(2024×log2024)，空间O ( 1 ) O(1)O(1)

关键细节

例题 5：依依的画作

题目描述

N NN个两位正整数，统计有多少对相邻数字不遵循规则（前一个的个位应该等于后一个的十位）。

关键思路

字符串索引：

• 个位：a[i][1]（字符串的第二个字符）
• 十位：a[i+1][0]（字符串的第一个字符）

统计：遍历0 00到N − 2 N-2N−2，统计a[i][1] != a[i+1][0]的次数。

推演验证

输入: 5 66 13 22 55 98 i=0: 66[1]=6, 13[0]=1 → 6≠1 ❌ 不遵循 i=1: 13[1]=3, 22[0]=2 → 3≠2 ❌ 不遵循 i=2: 22[1]=2, 55[0]=5 → 2≠5 ❌ 不遵循 i=3: 55[1]=5, 98[0]=9 → 5≠9 ❌ 不遵循 总共4对不遵循 输出: 4 ✓

题解

n=int(input())a=list(map(str,input().split()))# 统计不遵循规则的相邻对数print(sum(1foriinrange(n-1)ifa[i][1]!=a[i+1][0]))

复杂度：时间O ( N ) O(N)O(N)，空间O ( 1 ) O(1)O(1)

关键细节

二、今日刷题总结

模拟题解题模板

# 模板1：字符统计类cnt={}forcins:cnt[c]=cnt.get(c,0)+1# 或直接用 collections.Counter# 模板2：贪心交换类foriinrange(n):ifnotmatch(i):forjinrange(i+1,n):ifcan_swap(i,j):swap(i,j)breakans+=1# 模板3：进制转换类defto_base(n,base):"""将n转换为base进制，返回数位列表"""digits=[]whilen>=base:n,r=divmod(n,base)digits.append(r)digits.append(n)returndigits[::-1]# 反转得到正序# 模板4：字符串索引类# 两位数的个位和十位units=s[1]# 个位tens=s[0]# 十位

三、结语

模拟题是蓝桥杯的送分题，但也是丢分重灾区。今天的5道题告诉我们：

🌟今日收获：

1. 字符串处理要熟练：set()、count()、索引访问
2. 贪心思想：能交换就不替换，能一次解决就不分两次
3. 数学观察：递归函数先手动算几项，找规律
4. 进制转换：divmod()和bin()是利器
5. Pythonic写法：sum(1 for ... if ...)简洁高效

模拟题没有固定的算法模板，但有固定的解题套路：读题→找规律→写代码→验证。多练多总结，国赛模拟题全AC不是梦！💪

如果本文对你有帮助，欢迎点赞 👍 + 收藏 ⭐ + 关注 🔔，你的支持是我持续更新的动力！