1. 项目背景与核心价值作为一名计算机专业考研过来人我深知东华大学复试机试环节的OJ系统对考生意味着什么。这套每日3题打卡计划源于我去年备考时的真实经历——通过持续攻克OJ题库中的典型题目最终在复试环节取得了满分成绩。现在把133~135这三道经典题目的解题思路和避坑指南整理出来希望能帮助更多学弟学妹少走弯路。东华OJ系统最大的特点在于其看似基础实则暗藏玄机的命题风格。题目往往以基础算法为外壳但测试用例会针对边界条件和特殊场景进行严格检验。这三道题分别考察了字符串处理、动态规划和图论基础都是复试高频考点也是容易拉开分差的关键题型。2. 题目133特殊字符串匹配2.1 题目重述给定主串S和模式串P判断P是否为S的特殊子串。特殊子串定义为在S中可以通过删除任意数量字符得到P且剩余字符的相对顺序保持不变。例如SaxbcydzPabcd时返回true。2.2 双指针解法实现def is_special_substring(s: str, p: str) - bool: i j 0 while i len(s) and j len(p): if s[i] p[j]: j 1 i 1 return j len(p)关键点这个解法时间复杂度O(n)空间复杂度O(1)。注意循环终止条件要同时判断两个指针避免数组越界。2.3 常见错误分析边界条件遗漏未处理空字符串情况P为空时应该返回True指针移动错误在字符匹配时才移动j指针但无论是否匹配都要移动i指针过早终止当j到达P末尾时就立即返回可能错过后续更优解本题不适用3. 题目134最小路径覆盖3.1 问题建模给定DAG图求最少需要多少条路径才能覆盖所有顶点路径不可有重复顶点。这实际上可以转化为二分图的最大匹配问题。3.2 匈牙利算法实现def max_matching(graph): match_to [-1] * len(graph) result 0 def bpm(u, seen): for v in graph[u]: if not seen[v]: seen[v] True if match_to[v] -1 or bpm(match_to[v], seen): match_to[v] u return True return False for u in range(len(graph)): if bpm(u, [False] * len(graph)): result 1 return result3.3 转换公式最小路径覆盖数 顶点数 - 最大匹配数。需要注意必须先将DAG转换为二分图顶点编号要从0开始连续分布邻接表表示法更节省空间4. 题目135拓扑排序计数4.1 问题难点给定n个课程和m个先修关系计算完成所有课程的合法顺序总数。这是典型的拓扑排序计数问题但n≤12的约束暗示着可以用状态压缩DP来优化。4.2 状态转移方程定义dp[mask]表示已选课程集合为mask时的方案数dp[mask] Σ dp[mask ^ (1i)] 对于所有i满足 1. i在mask中 2. i的所有前驱课程都在mask中4.3 代码实现def count_topological_sort(n, prerequisites): pre [0] * n for u, v in prerequisites: pre[v] | 1 u dp [0] * (1 n) dp[0] 1 for mask in range(1 n): if not dp[mask]: continue for i in range(n): if not (mask (1 i)) and (pre[i] mask) pre[i]: dp[mask | (1 i)] dp[mask] return dp[(1 n) - 1]5. 调试与优化经验5.1 输入处理陷阱东华OJ的输入格式常有这些坑多组测试数据未明确说明组数需要用while(cinn)处理字符串可能包含空格建议用getline读取整行数据范围边界值如n0或n1e5的情况5.2 时间优化技巧在DP问题中预处理所有可能的状态转移使用位运算代替集合操作输入输出用scanf/printf代替cin/cout5.3 内存管理要点全局变量初始化要放在每组数据开始前vector等容器注意及时clear()大数组尽量定义在全局区6. 复试实战建议代码风格即使题目简单也要写注释特别是边界条件处理测试用例至少设计以下三种情况最小规模输入如n1最大规模输入测试时间限制特殊结构数据如完全图、链状图调试输出保留调试代码但注释掉方便考官查看调试思路我在练习时建立了一个错题本记录每道题的错误原因和改正方法。比如在拓扑排序计数题中最初忽略了状态转移的条件判断导致结果偏大。后来通过打印中间状态发现了这个问题。这种系统性的复盘让我的代码通过率从60%提升到了95%以上。