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(i1) for i, ch in enumerate(s) if ch target] print( .join(positions) if positions else -1)注意这类基础题往往设置隐蔽的边界条件比如空字符串输入或目标字符不存在的情况。建议在本地测试时补充以下用例输入 和 a输入hello 和 z2.2 B题 - 贪心算法应用这是一个典型的区间调度问题需要选择最多不重叠的课程时间段。标准解法是将区间按结束时间排序然后进行贪心选择将课程按结束时间升序排序初始化当前结束时间为第一个课程的结束时间遍历后续课程若开始时间≥当前结束时间则选择该课程关键证明这种策略能保证每次选择后剩余的可用时间最大化。时间复杂度主要在排序的O(nlogn)n int(input()) courses [tuple(map(int, input().split())) for _ in range(n)] courses.sort(keylambda 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] cd[x1][y21] - cd[x21][y1] - cd[x21][y21] c最后对d求二维前缀和得到结果矩阵这个算法的关键在于理解差分数组如何通过四个角的修改影响整个子矩阵。时间复杂度优化到O(k nm)n, m, k map(int, input().split()) matrix [list(map(int, input().split())) for _ in range(n)] d [[0]*(m2) for _ in range(n2)] for _ in range(k): x1, y1, x2, y2, c map(int, input().split()) d[x1][y1] c d[x1][y21] - c d[x21][y1] - c d[x21][y21] c # 计算二维前缀和 for i in range(1, n1): for j in range(1, m1): 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(n1)] size [1]*(n1) 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]*(n1) primes [] for i in range(2, n1): 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第三步模数处理由于结果需要对1e97取模需要预处理阶乘和逆元MOD 10**97 max_n 1e6 fact [1]*(max_n1) inv_fact [1]*(max_n1) for i in range(1, max_n1): 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[i1] * (i1) % MOD def comb(n, k): return fact[n] * inv_fact[k] % MOD * inv_fact[n-k] % MOD最终解法需要结合上述所有组件是典型的竞赛压轴题风格。我在比赛中因没有及时想到动态规划转移方程而耗时较多这也反映出数论题的解题经验需要长期积累。5. 比赛总结与提升建议通过这次训练赛我总结了几个关键经验点模板准备将常用算法如并查集、快速幂、线段树等写成可复用的代码片段但要注意理解内在原理而非死记硬背调试技巧对边界情况如n0,1单独测试使用assert语句验证中间结果在WA时先检查算法思路而非盲目调试代码时间分配前30分钟应快速解决简单题中段时间主攻中等难度题最后留足时间思考难题和检查建议选手定期参加此类训练赛赛后务必进行题目复盘。可以将自己的解法与标程对比学习更优的实现方式。对于这次比赛的H题我后来参考了其他选手的解法发现可以利用五边形数定理进一步优化动态规划这提醒我要持续扩展数学知识面。
