牛客小白月赛133 详细题解｜C字符串匹配+D质因数贪心，一遍看懂两道中档题
📌 比赛前言
本次牛客小白月赛133于2026.5.29晚开赛，整场比赛难度梯度友好，面向算法入门选手，一共6道题目，整体难度从模拟逐步过渡到字符串思维、数论贪心。其中**C题（字符串构造匹配）、D题（最小公倍数融合求全局GCD）**是本场比赛两道核心中档题，也是拉开分数的关键题目。
两道题核心考察点总结：
-
C题：字符串预处理+前后缀最小值优化，核心陷阱为双连续子串可重叠，暴力枚举会直接超时，需要线性时间优化
-
D题：数论质因数分解+贪心思维，无需复杂GCD/LCM公式推导，抓住公共质因子核心结论即可秒解
本文会完整还原两道题目原题、剥离冗余题干、一步步推导解题思路，附上带完整注释的AC代码、全部边界坑点复盘，新手看完可以彻底吃透同类题型，全文无晦涩黑科技，适合入门选手收藏复盘。
🔴 C题：愿望卷轴与真名刻印（字符串匹配）
1.1 完整原题还原
给定固定模板字符串A = awdec（长度5）、模板字符串B = Fantasy\_Blue（长度12）。
现有长度为n的字符串S，我们可以执行字符修改操作：每次将S中任意一个字符替换为大小写字母或下划线，单次修改消耗1点代价，总修改代价不能超过k。
询问：能否在总代价≤k的前提下，修改字符串S，使得S中同时包含A、B两个连续子串。
输入输出约束
-
多组测试用例，T≤1e4
-
每组输入n,k和字符串S，1≤n≤1e5，所有用例n总和≤2e5
-
输出Yes/No，代表是否可以完成要求
核心规则补充
-
子串要求连续，非连续字符不算匹配成功
-
A和B两个子串允许位置重叠，重叠位置的字符只需要修改一次，无需重复计费（本题最大考点）
1.2 极简题意（一句话读懂）
给一个长字符串，允许改最多k个字符，问能否让字符串里同时出现连续的awdec和Fantasy_Blue，两个片段可以重叠，求是否可行。
1.3 解题难点分析
很多新手第一反应是暴力枚举A的所有起始位置、B的所有起始位置，两两组合计算总修改代价，但是暴力双重循环时间复杂度为O(n²)，面对n=1e5的数据会直接超时，完全无法通过。
同时大部分选手会忽略重叠场景：两个模板串重叠时，重叠部分字符修改一次即可同时满足两个模板要求，不能直接直接两个代价相加。因此我们只需要分两种不重叠的排布情况，再用前缀最小值优化时间即可覆盖所有场景：
-
情况一：***段在前，B片段在后（无重叠）
-
情况二：B片段在前，***段在后（无重叠）
只要两种情况任意一种总修改代价≤k，答案即为Yes；反之输出No。而重叠场景的总代价一定小于等于无重叠场景，因此只要无重叠存在合法方案，重叠一定也存在，无需单独计算重叠情况，大幅简化代码逻辑。
1.4 分步解题思路
步骤1：预处理代价数组
提前遍历字符串S，预处理出两个代价数组：
-
costA[i]：S从下标i开始，连续5个字符修改为A串需要的修改次数
-
costB[i]：S从下标i开始，连续12个字符修改为B串需要的修改次数
该步骤时间复杂度O(n)，线性遍历即可完成。
步骤2：前缀最小值优化查询
我们遍历B串的每一个合法起始位置j，想要找到j之前所有合法A串位置中，修改代价最小的那一个，两者代价相加就是总代价。
如果每一次都遍历前面所有A位置找最小值，还是O(n²)，因此我们维护一个前缀最小值变量，遍历过程中实时更新前方最小A代价，做到单次遍历O(n)。
步骤3：双向校验两种排布
-
遍历所有B的位置，匹配前方最小A代价（A在前B在后）
-
遍历所有A的位置，匹配前方最小B代价（B在前A在后）
任意一种满足总代价≤k，直接判定可行。
1.5 完整AC代码+逐行详细注释
import sys
def main():
# 快速读入，适配大数据多组输入，避免input超时
data = sys.stdin.read().split()
ptr = 0
T = int(data[ptr])
ptr += 1
# 固定两个模板字符串
A = "awdec"
B = "Fantasy_Blue"
la = len(A) # A长度5
lb = len(B) # B长度12
res = [] # 统一存储答案，最后一次性输出，减少IO耗时
for _ in range(T):
n, k = int(data[ptr]), int(data[ptr+1])
ptr += 2
s = data[ptr]
ptr += 1
# 预处理costA：每个位置开头匹配A的修改开销
costA = [float('inf')] * n
for i in range(n - la + 1):
cnt = 0
for p in range(la):
if s[i+p] != A[p]:
cnt += 1
costA[i] = cnt
# 预处理costB：每个位置开头匹配B的修改开销
costB = [float('inf')] * n
for i in range(n - lb + 1):
cnt = 0
for p in range(lb):
if s[i+p] != B[p]:
cnt += 1
costB[i] = cnt
ok = False
# 场景1：A在前，B在后，遍历所有B的起始位置
min_a = float('inf')
for j in range(n):
# 更新j位置之前所有合法A的最小开销
if j - la >= 0:
min_a = min(min_a, costA[j - la])
# 当前j位置可以放B，判断前方最小A开销+B开销是否合法
if j + lb <= n:
if min_a + costB[j] <= k:
ok = True
break
# 场景2：B在前，A在后，遍历所有A的起始位置
if not ok:
min_b = float('inf')
for j in range(n):
if j - lb >= 0:
min_b = min(min_b, costB[j - lb])
if j + la <= n:
if min_b + costA[j] <= k:
ok = True
break
res.append("Yes" if ok else "No")
# 统一输出所有答案
print('\n'.join(res))
if __name__ == "__main__":
main()
1.6 复杂度分析&易错坑点复盘
时间复杂度
预处理代价数组：O(n*(lenA+lenB))，lenA、lenB为固定常数，因此整体为线性O(n)，完全满足2e5的数据上限。
新手高频踩坑点
-
暴力双重循环超时：不要两层循环枚举A、B所有位置，必须用前缀最小值优化
-
忽略字符串边界：A只能从0~n-5位置开始，B只能从0~n-12位置开始，越界位置无意义
-
慢速输入超时：多组大数据必须用sys.stdin.read()一次性读入，禁止循环input()
🔵 D题：魔力共鸣：最小公倍数融合（数论贪心）
2.1 完整原题还原
给定长度为n的正整数数组，你可以执行任意次融合操作：
-
选取数组中两个不同的数字，将两个数直接删除
-
往数组中插入两个数的最小公倍数lcm(x,y)
单次操作后数组长度减少1（删2加1）。
目标：让数组中所有数字的全局最大公约数GCD严格大于1，求最少需要多少次操作；无法达成输出-1。
输入输出约束
-
T≤100组用例，n≤1e5，数组元素1≤a[i]≤1e5
-
所有用例n总和≤1e5
2.2 极简题意（一句话读懂）
每次把两个数合并成它们的最小公倍数，数组长度每次减一，求最少操作次数，让数组所有数公共GCD>1。
2.3 核心数论结论（本题解题关键）
很多新手看到LCM、GCD直接望而却步，其实本题不需要计算任何LCM和GCD，只需要一个核心数学结论：
两个数合并为LCM后，保留两个数全部的质因子；多次合并之后，数组内所有数字含有的公共质因子永远不会新增，只会保留原有出现过的质因子。
想要最终所有数GCD>1，等价于：最终所有数必须共享同一个质数因子。
举个例子：如果数组中有多个数字含有质因子2，我们只需要保留所有含2的数字，把其余不含2的数字全部合并掉，最终数组所有数都会含有因子2，全局GCD必然≥2。
2.4 贪心解题思路
-
对数组每一个数字分解质因数，统计每一个质数在整个数组中出现的总次数
-
找到出现次数最多的质数p，假设出现次数为cnt
-
我们保留这cnt个含有p的数字，剩下n-cnt个数字需要全部合并消除
-
需要的最少操作次数 = 总长度n - 最多相同质因子的个数
特殊边界判断
-
数组中存在数字1：数字1没有任何质因子，永远无法参与构造公共GCD，直接忽略
-
所有数字都是1：没有任何质因子，永远无法满足要求，直接输出-1
-
原数组全局GCD本身就大于1：无需任何操作，输出0
2.5 完整AC代码+逐行详细注释
import sys
import math
from collections import defaultdict
# 函数：对一个数字分解质因数，返回去重后的质因子集合
def get_prime_factors(x):
factors = set()
# 数字1无质因子，直接返回空集合
if x == 1:
return factors
temp = x
# 试除法分解质因数
for p in range(2, int(math.isqrt(temp)) + 1):
if temp % p == 0:
factors.add(p)
while temp % p == 0:
temp //= p
# 剩余大于1的数也是质因子
if temp > 1:
factors.add(temp)
return factors
def solve():
data = list(map(int, sys.stdin.read().split()))
idx = 0
T = data[idx]
idx += 1
for _ in range(T):
n = data[idx]
idx += 1
a = data[idx:idx+n]
idx += n
# 统计每个质数出现的总次数
prime_cnt = defaultdict(int)
for num in a:
factors = get_prime_factors(num)
for p in factors:
prime_cnt[p] += 1
# 没有任何质因子（全是1），无解
if not prime_cnt:
print(-1)
continue
# 找到出现次数最多的质因子
max_cnt = max(prime_cnt.values())
# 最少操作次数 = 总个数 - 最多同因子数字个数
ans = n - max_cnt
print(ans)
if __name__ == "__main__":
solve()
2.6 复杂度分析&易错坑点复盘
时间复杂度
瓶颈为试除法分解质因数，单个数分解复杂度为O(√x)，x≤1e5，√x最大为300左右，整体可以轻松通过1e5的数据量。
新手高频踩坑点
-
质因子重复统计：一个数字含有多个相同质因子，只需要统计一次，因此分解后要用集合去重
-
特判数字1：忘记处理1会导致统计错误，1无质因子无法贡献公共公约数
-
强行计算LCM/GCD：完全不需要模拟合并过程，模拟一定会超时，本题只需要统计质因子即可
📊 整场比赛两道题目复盘总结
3.1 两道题考察核心能力
-
C题：字符串预处理+前缀优化思维，考察新手是否能避开暴力枚举的惯性思维，学会用线性优化降低时间复杂度，属于字符串经典套路题
-
D题：数论本质洞察，考察跳出模拟操作、透过现象看数学本质的能力，小白赛数论题几乎都不需要模拟过程，核心是找数学不变量
3.2 新手刷题建议
-
遇到字符串匹配题：优先预处理代价数组，再用前缀/后缀最值优化，拒绝暴力双重循环
-
遇到GCD/LCM合并类题目：永远优先分析质因子变化规律，90%的同类题目都不需要实际计算GCD和LCM
-
大数据输入场景：Python务必使用sys.stdin.read()快速读入，循环input一定会超时
3.3 同类拓展题目推荐
-
字符串同类：牛客小白月赛 字符串代价匹配、双窗口重叠匹配题
-
数论同类：合并数字求公共公约数、质因子统计贪心系列题目
✅ 全文总结
本次小白月赛C、D两道中档题，没有复杂算法和高阶数据结构，全部依托基础算法思维+基础数论知识即可满分通过。对于算法新手而言，相比于背代码模板，学会规避暴力、挖掘题目隐藏数学规律才是进阶关键。
后续小白月赛我会看心情持续更新全套题解，需要整套A-F全题解析可以随时留言！
京公网安备 11010502036488号