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

6123. 哞叫时间

Week 1
2月18日

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

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

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

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

一种哞叫一般地定义为子串 $c_i{c}_j{c}_j$，其中某字符 $c\_i$ 之后紧跟着 $2$ 个某字符 $c_j$，且 $c_i\ne c_j$。

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

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

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

输入格式

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

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

输出格式

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

每行输出一种哞叫。

数据范围

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

输入样例1：

10 2
zzmoozzmoo

输出样例1：

1
moo

样例1解释

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

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

输入样例2：

17 2
momoobaaaaaqqqcqq

输出样例2：

3
aqq
baa
cqq

样例2解释

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

此外，位置 $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) * 2abb.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 = 0for x in range(-2, 3):if 0 <= j + x <= n - 3:s2 = s[j + x:j + x + 3]if s2 == pattern:sign = 1breakif 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] += 1break  # 只能修改一次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)

代码逻辑解释：

1. 预处理阶段：

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

2. 核心函数update：

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

3. 主处理流程：

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

4. 结果处理：

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

关键优化点：

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

---

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