【蓝桥杯集训·每日一题2025】AcWing6123.哞叫时间python

6123. 哞叫时间

Week 1 2月18日

农夫约翰正在试图向埃尔茜描述他最喜欢的 USACO 竞赛，但她很难理解为什么他这么喜欢它。

他说「竞赛中我最喜欢的部分是贝茜说 『现在是哞哞时间』并在整个竞赛中一直哞哞叫」。

埃尔茜仍然不理解，所以农夫约翰将竞赛以文本文件形式下载，并试图解释他的意思。

竞赛被定义为一个长度为 N N N 的小写字母字符串。

一种哞叫一般地定义为子串 c i c j c j c_ic_jc_j ci​cj​cj​，其中某字符 c _ i c\_i c_i 之后紧跟着 2 2 2 个某字符 c j c_j cj​，且 c i ≠ c j c_i \neq c_j ci​=cj​。

根据农夫约翰的说法，贝茜哞叫了很多，所以如果某种哞叫在竞赛中出现了至少 F F F 次，那可能就是贝茜发出的。

然而，农夫约翰的下载可能损坏，文本文件可能存在至多一个字符与原始文件不同。

将可能的误差考虑在内，输出所有可能是贝茜发出的哞叫，按字母顺序排序。

输入格式

输入的第一行包含 N N N 和 F F F，表示字符串的长度以及贝茜的哞叫的频次下限。

第二行包含一个长度为 N N N 的小写字母字符串，表示竞赛。

输出格式

输出可能是贝茜发出的哞叫的数量，以下是按字典序排序的哞叫列表。

每行输出一种哞叫。

数据范围

3 ≤ N ≤ 20000 3 \le N \le 20000 3≤N≤20000, 1 ≤ F ≤ N 1 \le F \le N 1≤F≤N

输入样例1： 10 2 zzmoozzmoo 输出样例1： 1 moo 样例1解释

在这个样例中，任何字符变化都不会影响答案。

唯一贝茜可能发出的哞叫是 moo。

输入样例2： 17 2 momoobaaaaaqqqcqq 输出样例2： 3 aqq baa cqq 样例2解释

在这个样例中，位置 8 8 8（从零开始索引）的 a 可能是由 b 损坏导致的，这使得 baa 成为一种贝茜发出两次的可能的哞叫。

此外，位置 11 11 11 的 q 可能是由 c 损坏导致的，这使得 cqq 成为一种贝茜可能的哞叫。

aqq 可以通过将 c 换成 a 来达到。

输入样例3： 3 1 ooo 输出样例3： 25 aoo boo coo doo eoo foo goo hoo ioo joo koo loo moo noo poo qoo roo soo too uoo voo woo xoo yoo zoo

---

思路：

两种枚举方式：

枚举所有abb形式 时间复杂度O(26 * 25 * n)

枚举能变化一次的字母 时间复杂度O(26*n)

code1：

n, f = map(int, input().split()) s = input() # 生成所有可能的abb组合 abb = [] for i in range(26): for j in range(26): if i != j: str = chr(ord('a') + i) + chr(ord('a') + j) * 2 abb.append(str) # 统计每个abb组合的出现次数 cnt = [0] * (26 * 25) for i in range(len(abb)): pattern = abb[i] for j in range(n - 2): s1 = s[j:j + 3] if s1 == pattern: cnt[i] += 1 # 处理出现次数为f-1的情况 for i in range(len(abb)): if cnt[i] == f - 1: pattern = abb[i] for j in range(n - 2): s1 = s[j:j + 3] # 检查修改是否会影响原有的abb组合 sign = 0 for x in range(-2, 3): if 0 <= j + x <= n - 3: s2 = s[j + x:j + x + 3] if s2 == pattern: sign = 1 break if sign: continue # 如果会影响原有的abb组合，跳过 # 检查当前子串是否可以通过修改一个字符变为abb组合 if (s1[0] == pattern[0] and s1[1] == pattern[1]) or \ (s1[0] == pattern[0] and s1[2] == pattern[2]) or \ (s1[1] == pattern[1] and s1[2] == pattern[2]): cnt[i] += 1 break # 只能修改一次 ans = [] for i in range(len(abb)): if cnt[i] >= f: ans.append(abb[i]) print(len(ans)) for i in sorted(ans): print(i)

---

code2:

n, f = map(int, input().split()) # 将字符串转换为0-25的数字表示（a-z） s = [ord(x) - ord('a') for x in input()] # cnt[i][j] 记录ijj出现的次数 cnt = [[0] * 26 for _ in range(26)] ans = [] def update(l, r, c): l = max(l, 0) # 处理左边界 r = min(r, n - 1) # 处理右边界 for i in range(l, r - 1): # 遍历所有可能的3字符窗口起始位置 # 检查是否是abb模式 if s[i] != s[i + 1] and s[i + 1] == s[i + 2]: cnt[s[i]][s[i + 2]] += c # 更新对应模式的计数 # 如果达到阈值且是增加操作（c=1） if cnt[s[i]][s[i + 2]] >= f and c == 1: # 转换为字符串形式 ans.append(chr(ord('a') + s[i]) + chr(ord('a') + s[i + 2]) * 2) update(0, n - 1, 1) for i in range(n): # 遍历每个可能修改的位置 temp = s[i] # 保存原始字符 # 第一步：消除当前字符对周围的影响（c=-1） update(i - 2, i + 2, -1) # 修改会影响前后2个位置的模式 # 尝试修改为其他字符 for j in range(26): if s[i] != j: # 跳过与原字符相同的情况 s[i] = j # 临时修改字符 # 第二步：计算修改后的影响（c=1） update(i - 2, i + 2, 1) # 添加新字符的影响 update(i - 2, i + 2, -1) # 恢复现场 s[i] = temp # 恢复原始字符 # 第三步：重新统计原始字符的影响（c=1） update(i - 2, i + 2, 1) # 去重并排序结果 ans = sorted(set(ans)) print(len(ans)) for i in ans: print(i)

代码逻辑解释：

预处理阶段：

将输入字符串转换为数字形式（a->0, b->1…），方便处理初始化二维计数数组cnt，用于统计每个abb模式的出现次数

核心函数update：

作用：在指定区间内扫描所有abb模式，并更新计数器参数c控制增加（1）或减少（-1）计数通过滑动窗口（每次检查3个字符）的方式遍历区间

主处理流程：

初始统计：调用update(0, n-1, 1)统计原始字符串中的所有abb模式遍历每个字符位置： 先消除当前字符对周围5个字符范围（i-2到i+2）的影响尝试将该位置修改为其他25个字母（共26种可能）对每种可能的修改： 临时修改字符计算修改后的影响（会覆盖前后5个字符范围）立即回滚修改（为了不影响后续测试其他字符） 最后恢复原始字符并重新统计其影响

结果处理：

使用set去重（可能重复添加相同模式）按字典序排序后输出

关键优化点：

局部更新：只处理受修改影响的区域（i-2到i+2），而不是全盘重新扫描，将时间复杂度从O(n^2)降低到O(n)即时回滚：在测试每个可能的字符修改时，立即回滚修改状态，避免创建多个字符串副本

---

END 如果有更多问题或需要进一步的帮助，可以在评论区留言讨论哦！ 如果喜欢的话，请给博主点个关注 谢谢