万网ecs网站环境搭建,全网营销式网站,linux做网站用什么语言,做科研有什么好的网站6123. 哞叫时间
Week 1 2月18日 农夫约翰正在试图向埃尔茜描述他最喜欢的 USACO 竞赛#xff0c;但她很难理解为什么他这么喜欢它。
他说「竞赛中我最喜欢的部分是贝茜说 『现在是哞哞时间』并在整个竞赛中一直哞哞叫」。
埃尔茜仍然不理解#xff0c;所以农夫约翰将竞赛以…
6123. 哞叫时间
Week 1 2月18日 农夫约翰正在试图向埃尔茜描述他最喜欢的 USACO 竞赛但她很难理解为什么他这么喜欢它。
他说「竞赛中我最喜欢的部分是贝茜说 『现在是哞哞时间』并在整个竞赛中一直哞哞叫」。
埃尔茜仍然不理解所以农夫约翰将竞赛以文本文件形式下载并试图解释他的意思。
竞赛被定义为一个长度为 N N N 的小写字母字符串。
一种哞叫一般地定义为子串 c i c j c j c_ic_jc_j cicjcj其中某字符 c _ i c\_i c_i 之后紧跟着 2 2 2 个某字符 c j c_j cj且 c i ≠ c j c_i \neq c_j cicj。
根据农夫约翰的说法贝茜哞叫了很多所以如果某种哞叫在竞赛中出现了至少 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) * 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 # 更新对应模式的计数# 如果达到阈值且是增加操作c1if 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-1update(i - 2, i 2, -1) # 修改会影响前后2个位置的模式# 尝试修改为其他字符for j in range(26):if s[i] ! j: # 跳过与原字符相同的情况s[i] j # 临时修改字符# 第二步计算修改后的影响c1update(i - 2, i 2, 1) # 添加新字符的影响update(i - 2, i 2, -1) # 恢复现场s[i] temp # 恢复原始字符# 第三步重新统计原始字符的影响c1update(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到i2的影响尝试将该位置修改为其他25个字母共26种可能对每种可能的修改 临时修改字符计算修改后的影响会覆盖前后5个字符范围立即回滚修改为了不影响后续测试其他字符 最后恢复原始字符并重新统计其影响 结果处理 使用set去重可能重复添加相同模式按字典序排序后输出
关键优化点
局部更新只处理受修改影响的区域i-2到i2而不是全盘重新扫描将时间复杂度从O(n^2)降低到O(n)即时回滚在测试每个可能的字符修改时立即回滚修改状态避免创建多个字符串副本 END 如果有更多问题或需要进一步的帮助可以在评论区留言讨论哦 如果喜欢的话请给博主点个关注 谢谢
