前言这篇文章我把自己从青铜到AK踩过的坑、总结的技巧全部分享出来。全文7000字附可直接套用的代码模板建议收藏后慢慢看。一、先读题 30 秒胜过写码两小时1.1 你真的会读题吗很多同学拿到题就开始写写了一半发现理解错了题意推倒重来 ——时间就这么没的。我的读题三步法步骤做什么关注什么第 1 遍速读搞清楚 输入什么、输出什么数据范围、时间限制第 2 遍精读找出约束条件和坑点恰好、最多、至少第 3 遍验证用样例反推题意边界样例、特殊样例1.2 实战案例看这道题的描述给定一个数组找出和最大的连续子数组返回其最大和。很简单对吧LeetCode 第 53 题经典动态规划。但如果题目改成给定一个数组找出和最大的非空连续子数组返回其最大和。数组长度≥1。有区别吗有。前者隐含了可以选空数组和为 0后者明确了非空。当数组全是负数时答案完全不同。一个词的差别就是 0 分和 100 分的距离。二、数据范围决定算法选型2.1 这是最重要的技巧没有之一比赛时拿到题先看数据范围再想算法。数据范围就是出题人给你的 暗示数据规模可选时间复杂度对应算法n ≤ 20O(2^n)状态压缩、暴力搜索n ≤ 100O(n^3)Floyd、区间 DPn ≤ 1000O(n^2)普通 DP、双循环枚举n ≤ 10^5O(n log n)排序、二分、线段树、堆n ≤ 10^6O(n)贪心、双指针、前缀和n ≤ 10^9O(log n)数学公式、快速幂、矩阵快速幂2.2 举个例子题目求数组中第 K 大的数。n ≤ 100 → 冒泡排序取第 K 个随便写n ≤ 10^5 → 快速排序 O (n log n)能过n ≤ 10^7 → 必须用快速选择 O (n)排序会超时数据范围告诉你该用什么而不是你想用什么就用什么。三、暴力出奇迹先看看能不能过3.1 什么时候暴力是正解很多人看不起暴力解法但比赛里能过的暴力就是好解法。尤其是比赛前两道题数据范围通常很小暴力直接 AC省时省力。判断标准n ≤ 1000 → O (n^2) 暴力大概率能过涉及字符串匹配 → 先试试 O (n*m)不行再上 KMP几何题 → 暴力枚举所有组合比想复杂算法快得多3.2 暴力的正确姿势cpp运行// ❌ 错误写法边算边输出容易超时 for (int i 0; i n; i) { for (int j 0; j n; j) { cout a[i] a[j] endl; } } // ✅ 正确写法关闭同步 批量输出 ios::sync_with_stdio(false); cin.tie(nullptr); // 或者用 printfC 选手记住这两行能救你无数次 TLE。四、前缀和与差分数组题的瑞士军刀4.1 前缀和区间求和 O (1)这是我用得最多的技巧没有之一。模板代码python运行def prefix_sum(arr): n len(arr) pre [0] * (n 1) for i in range(n): pre[i 1] pre[i] arr[i] return pre # 求 arr[l...r] 的和0-based闭区间 def range_sum(pre, l, r): return pre[r 1] - pre[l]适用场景多次区间求和查询子数组和相关问题配合哈希表找 和为 K 的子数组4.2 差分区间更新 O (1)如果题目是 对数组的某个区间统一加上 val差分就是你的朋友。cpp运行// 差分数组 d原数组 a // 区间 [l, r] 加 val d[l] val; d[r 1] - val; // 最后求前缀和还原 for (int i 1; i n; i) { a[i] a[i - 1] d[i]; }经典题型航班预订统计拼车区间加法记住数组题想优化先想前缀和和差分。五、双指针让 O (n^2) 变 O (n) 的魔法5.1 什么时候用双指针满足单调性的问题双指针基本都能上。常见类型类型典型题目核心思想快慢指针环形链表、找中点一个走一步一个走两步左右指针两数之和、盛最多水两端向中间逼近滑动窗口最长无重复子串右指针扩展左指针收缩5.2 滑动窗口模板必背python运行def sliding_window(s): left 0 window {} # 窗口内的状态 result 0 for right in range(len(s)): # 1. 右指针扩展把 s[right] 加入窗口 char s[right] window[char] window.get(char, 0) 1 # 2. 判断是否需要收缩左指针 while 窗口不满足条件: # 3. 左指针收缩把 s[left] 移出窗口 left_char s[left] window[left_char] - 1 if window[left_char] 0: del window[left_char] left 1 # 4. 更新答案 result max(result, right - left 1) return result这个模板能解决 80% 的子串 / 子数组问题最长无重复字符子串最小覆盖子串长度最小的子数组找到字符串中所有字母异位词背下来比赛直接套。六、二分查找不只是 找数6.1 二分的本质单调性判定很多人以为二分只能用来 在有序数组里找某个数太狭隘了。二分的本质是如果一个问题的答案具有单调性满足条件的是连续一段就可以用二分来猜答案。6.2 二分答案模板python运行def binary_search_answer(nums, target): left 最小值 right 最大值 while left right: mid (left right) // 2 if check(mid): # mid 这个答案行不行 right mid # 行试试更小的 else: left mid 1 # 不行得更大 return left6.3 经典应用题目给定一个数组和一个整数 m将数组分成 m 个非空连续子数组使得这 m 个子数组各自和的最大值最小。思路猜一个答案 mid最大子数组和为 mid判断能不能把数组分成不超过 m 段每段和≤mid如果能 → 答案≤mid往小了猜如果不能 → 答案 mid往大了猜python运行def splitArray(nums, m): def check(max_sum): count 1 current 0 for num in nums: if current num max_sum: count 1 current num if count m: return False else: current num return True left max(nums) right sum(nums) while left right: mid (left right) // 2 if check(mid): right mid else: left mid 1 return left最大化最小值、最小化最大值—— 看到这种描述直接二分答案。七、90% 的人不知道的比赛技巧7.1 打表找规律遇到数学题、找规律题想不出公式怎么办暴力打小数据的表然后肉眼找规律。举个例子上楼梯每次可以走 1 步或 2 步问 n 阶楼梯有多少种走法暴力打表n1 → 1 n2 → 2 n3 → 3 n4 → 5 n5 → 8哦这不就是斐波那契数列吗公式直接出来了。比赛里的数学题十有八九可以打表找规律。7.2 对拍调试你的代码过了样例但 WA 了自己又找不到错写一个暴力解法保证正确但可能超时写一个随机数据生成器然后两个程序对拍。# shell 对拍脚本 while true; do python3 generate.py test.in # 生成随机数据 python3 brute.py test.in out1 # 暴力解法正确 python3 solve.py test.in out2 # 你的解法 if diff out1 out2; then echo OK else echo WA! cat test.in # 输出出错的数据 break fi done跑 1000 组数据bug 无所遁形。7.3 骗分技巧实在做不出来别空着能骗一分是一分特殊值骗分题目说 n≥1n1 时答案是什么直接特判输出小规模骗分n≤20 时暴力大数据随便输出个值样例输出实在不会把样例输出写上万一测试用例就是样例呢比赛排名有时候就差那 5 分、10 分。八、比赛时间分配策略8.1 两小时比赛怎么分配时间做什么目标0-10 分钟通读所有题目标记难度确定做题顺序10-40 分钟做签到题 简单题先把稳拿的分拿到40-90 分钟攻克中等题核心得分点90-110 分钟难题骗分 检查能拿多少拿多少最后 10 分钟检查提交别因为低级错误丢分8.2 关键原则先易后难不要死磕一道题卡住了先跳每道题最多想 20 分钟想不出来就先放放提交前检查数组开够了吗long long 了吗多组数据初始化了吗九、推荐刷题路线最后给大家一个从入门到比赛获奖的刷题路径第一阶段入门数组、字符串、排序、二分目标比赛前两题稳过题量约 50 道第二阶段进阶DP、贪心、图论基础、数据结构目标中等题能做出来题量约 150 道第三阶段高阶高级数据结构、数论、网络流、计算几何目标冲击排行榜题量300 道 刷题平台推荐LeetCode基础、Codeforces比赛、洛谷国内题库写在最后编程比赛这东西天赋决定上限努力决定下限。大多数人还没到拼天赋的程度 —— 把基础算法练熟模板背好常见题型一看就有思路进 Top 10% 真的不难。最怕的就是题刷了不少但从不总结每次遇到类似的题还是重新想一遍。收藏这篇文章比赛前翻一翻比你刷 10 道水题有用得多。互动时间你最近参加了什么比赛成绩怎么样有什么想看的算法专题评论区聊聊点赞最高的我下期写如果这篇文章对你有帮助点赞 收藏⭐ 关注三连支持一下下期更新《动态规划从入门到精通10 道经典题带你吃透 DP》