1. 竞赛背景与个人解题思路
ZUFE寒假训练赛是浙江财经大学面向ACM-ICPC竞赛选手举办的常规性编程赛事。这类比赛通常包含8-12道算法题，涵盖动态规划、图论、数据结构等核心知识点。作为参赛选手，我习惯在赛后整理完整的解题报告，既是对自己思路的复盘，也能帮助其他选手理解题目背后的算法思想。
今年这套题目的难度梯度设计合理，从基础模拟题到需要复杂推导的压轴题都有涉及。特别值得注意的是D题和H题，前者考察了不常见的二维差分变形应用，后者则需要结合数论和组合数学知识。接下来我将按照题目顺序，详细讲解每道题的解题思路和实现细节。
2. 题目详解与核心算法分析
2.1 A题 - 基础字符串处理
题目要求统计给定字符串中特定字符的出现位置。这是典型的签到题，但需要注意两个易错点：
- 字符串索引通常从0开始还是1开始（本题明确要求从1开始计数）
- 大小写敏感问题（样例中明确提示区分大小写）
我的实现采用线性扫描方式，时间复杂度O(n)：
s = input().strip() target = input().strip() positions = [str(i+1) for i, ch in enumerate(s) if ch == target] print(' '.join(positions) if positions else -1)注意：这类基础题往往设置隐蔽的边界条件，比如空字符串输入或目标字符不存在的情况。建议在本地测试时补充以下用例：
- 输入："" 和 "a"
- 输入："hello" 和 "z"
2.2 B题 - 贪心算法应用
这是一个典型的区间调度问题，需要选择最多不重叠的课程时间段。标准解法是将区间按结束时间排序，然后进行贪心选择：
- 将课程按结束时间升序排序
- 初始化当前结束时间为第一个课程的结束时间
- 遍历后续课程，若开始时间≥当前结束时间则选择该课程
关键证明：这种策略能保证每次选择后剩余的可用时间最大化。时间复杂度主要在排序的O(nlogn)：
n = int(input()) courses = [tuple(map(int, input().split())) for _ in range(n)] courses.sort(key=lambda x: x[1]) count = 0 last_end = -1 for start, end in courses: if start >= last_end: count += 1 last_end = end print(count)实际比赛中，有选手尝试按开始时间排序导致WA。这说明理解贪心算法的适用条件非常重要——不是所有区间问题都适用同一种排序策略。
3. 中等难度题目解析
3.1 D题 - 二维差分进阶
题目给出一个n×m的矩阵，要求进行若干次子矩阵加法操作后输出最终矩阵。暴力解法O(knm)显然会超时，必须使用二维差分技巧：
- 初始化差分数组d（比原矩阵多一行一列）
- 对每个操作(x1,y1,x2,y2,c)：
- d[x1][y1] += c
- d[x1][y2+1] -= c
- d[x2+1][y1] -= c
- d[x2+1][y2+1] += c
- 最后对d求二维前缀和得到结果矩阵
这个算法的关键在于理解差分数组如何通过四个角的修改影响整个子矩阵。时间复杂度优化到O(k + nm)：
n, m, k = map(int, input().split()) matrix = [list(map(int, input().split())) for _ in range(n)] d = [[0]*(m+2) for _ in range(n+2)] for _ in range(k): x1, y1, x2, y2, c = map(int, input().split()) d[x1][y1] += c d[x1][y2+1] -= c d[x2+1][y1] -= c d[x2+1][y2+1] += c # 计算二维前缀和 for i in range(1, n+1): for j in range(1, m+1): d[i][j] += d[i-1][j] + d[i][j-1] - d[i-1][j-1] print(matrix[i-1][j-1] + d[i][j], end=' ') print()踩坑记录：第一次提交时忘记处理矩阵的原始值，直接输出了差分数组。这种错误在时间压力下很容易出现，建议在编码前写好注释明确每个步骤的目的。
3.2 F题 - 并查集变种
这道题看似标准的并查集应用，但需要维护额外信息——每个集合的大小。经典的并查集实现需要增加size数组：
parent = [i for i in range(n+1)] size = [1]*(n+1) def find(u): while parent[u] != u: parent[u] = parent[parent[u]] u = parent[u] return u def union(u, v): root_u = find(u) root_v = find(v) if root_u == root_v: return if size[root_u] < size[root_v]: parent[root_u] = root_v size[root_v] += size[root_u] else: parent[root_v] = root_u size[root_u] += size[root_v]题目特殊之处在于要求输出每次合并后的最大集合大小。为此需要维护一个全局最大值变量，在每次成功合并后更新：
max_size = 1 for _ in range(m): u, v = map(int, input().split()) union(u, v) print(max_size)实测发现使用路径压缩和按秩合并后，算法效率完全满足题目约束（n,m ≤ 1e5）。并查集的常数优化在实际比赛中非常重要，建议选手熟记优化后的模板代码。
4. 高阶题目深度剖析
4.1 H题 - 数论与组合数学
这道压轴题要求计算满足特定条件的排列组合数，涉及以下知识点：
- 质数筛法（埃氏筛或欧拉筛）
- 模逆元计算（费马小定理）
- 组合数公式推导
解题步骤分解：
第一步：质数预处理使用欧拉筛预处理1e6范围内的质数，时间复杂度O(n)：
def euler_sieve(n): is_prime = [True]*(n+1) primes = [] for i in range(2, n+1): if is_prime[i]: primes.append(i) for p in primes: if i*p > n: break is_prime[i*p] = False if i % p == 0: break return primes第二步：问题转化经分析发现，题目实际要求的是：将n分解为若干个≥2的整数之和，且这些整数都是质数。这相当于计算质数分割方案数，可以使用动态规划：
定义dp[i]表示数字i的质数分割方案数，转移方程为： dp[i] = Σ dp[i-p] 对所有≤i的质数p
第三步：模数处理由于结果需要对1e9+7取模，需要预处理阶乘和逆元：
MOD = 10**9+7 max_n = 1e6 fact = [1]*(max_n+1) inv_fact = [1]*(max_n+1) for i in range(1, max_n+1): fact[i] = fact[i-1] * i % MOD inv_fact[max_n] = pow(fact[max_n], MOD-2, MOD) for i in range(max_n-1, -1, -1): inv_fact[i] = inv_fact[i+1] * (i+1) % MOD def comb(n, k): return fact[n] * inv_fact[k] % MOD * inv_fact[n-k] % MOD最终解法需要结合上述所有组件，是典型的竞赛压轴题风格。我在比赛中因没有及时想到动态规划转移方程而耗时较多，这也反映出数论题的解题经验需要长期积累。
5. 比赛总结与提升建议
通过这次训练赛，我总结了几个关键经验点：
模板准备：将常用算法（如并查集、快速幂、线段树等）写成可复用的代码片段，但要注意理解内在原理而非死记硬背
调试技巧：
- 对边界情况（如n=0,1）单独测试
- 使用assert语句验证中间结果
- 在WA时先检查算法思路而非盲目调试代码
时间分配：
- 前30分钟应快速解决简单题
- 中段时间主攻中等难度题
- 最后留足时间思考难题和检查
建议选手定期参加此类训练赛，赛后务必进行题目复盘。可以将自己的解法与标程对比，学习更优的实现方式。对于这次比赛的H题，我后来参考了其他选手的解法，发现可以利用五边形数定理进一步优化动态规划，这提醒我要持续扩展数学知识面。
的差异)
