1. 从一道国赛填空题说起跑步计划最近在整理蓝桥杯的历年真题特别是国赛级别的题目发现很多同学对填空题有种又爱又恨的感觉。爱的是它不像编程大题那样需要完整的代码框架和复杂的调试似乎“门槛”低一些恨的是填空题往往考察的是对算法核心逻辑的极致理解、对边界条件的敏锐洞察以及那么一点点的“灵光一现”。一个微小的疏忽就可能导致答案谬以千里前功尽弃。今天想和大家深入聊聊的就是一道典型的国赛填空题——“跑步计划”。这道题本身没有出现在我手头最全的公开真题库里但“跑步计划”这个名称非常具有代表性它指向了一类经典的规划与优化问题。这类问题在蓝桥杯乃至各类算法竞赛中屡见不鲜其内核往往是动态规划、贪心算法或者是基于日期、星期的周期性计算。它考察的不仅仅是写出一个能跑的代码更是如何在有限的时间内通过逻辑推理和数学建模找到那个确定无疑的答案。对于备赛的同学来说研究这类题目比单纯刷编程大题更有价值。因为填空题的求解过程本质上是对你算法思维严密性的一次高压测试。你需要自己设计数据结构和算法自己验证边界最终输出一个数字或字符串。这个过程里没有在线评测系统给你反馈“答案错误”你只能依靠自己的逻辑来保证正确性。这恰恰是算法能力的核心。所以这篇文章我不会直接给出某道特定“跑步计划”题的答案——那样没有意义。我将以“跑步计划”为引子拆解这类问题常见的出题套路、核心的解题框架以及我们在实战中必须警惕的那些“坑”。我会假设几种最有可能的题目背景比如基于星期的训练计划、基于目标里程的动态规划、或者带有约束条件的最优安排然后手把手带你走过完整的分析、建模、求解和验证流程。我们的目标不是解一道题而是掌握解一类题的方法。2. 拆解“跑步计划”类题目的四大核心套路在真正动手解题之前我们必须先判断题目属于哪种类型。根据“跑步计划”这个名称和蓝桥杯国赛的命题风格我梳理了四种最有可能的出题方向。每一种方向对应的解题工具和思考重心都完全不同。2.1 套路一周期性日期计算这是最直观也可能最简单的一种。题目可能会这样描述“小明从2023年3月1日星期三开始执行跑步计划他计划每周一、三、五跑步每周日休息其余时间力量训练。请问第100天时他在进行什么训练”或者“从某年某月某日开始按照某个固定周期循环执行计划问第N天或某个特定日期的状态。”核心考点日期处理、取模运算、周期循环。解题关键确定最小正周期通常是7天一周但有时计划可能以两周或更长时间为周期。建立映射关系将周期内的每一天映射到一个具体的活动跑步、休息、力量等。通常用一个数组来表示。计算偏移量计算目标日期相对于起始日期过去了多少天。这里要小心是否需要考虑起始日期当天是第0天还是第1天这是一个高频易错点。取模定位将总天数偏移量对周期长度取模得到的余数就是目标日期在周期中的位置通过映射数组即可查到活动。避坑指南边界日务必明确“第N天”是否包含起始日。常见的歧义是如果从第一天开始那么“第一天后”是第二天而“第一天”就是起始日。题目通常会说“从当天开始计算”或“经过N天后”需要仔细辨析。闰年与月份如果计划跨年或涉及具体月份就需要实现准确的日期推移函数考虑闰年能被4整除但不能被100整除或者能被400整除的年份和各个月份的天数。索引从0还是1开始编程时我们的数组索引通常从0开始。如果周期是7天那么days % 7的结果是0~6需要清晰地定义plan[0]对应的是周期内的哪一天比如是起始日对应的活动。2.2 套路二基于规则的递推或动态规划这类题目难度会上一个台阶。例如“小明想通过N天达到总跑步里程M公里。他每天最多跑10公里且为了健康不能连续两天都跑超过5公里。请问他有多少种不同的跑步计划每天里程数为正整数”或者“每次跑步会消耗体力恢复体力需要时间如何安排计划使得总收益最大”。核心考点动态规划DP的状态设计与转移方程。解题关键定义状态这是最难也是最关键的一步。状态必须能够唯一描述一个“子问题”的局面。对于跑步计划状态维度通常包括dp[i][j]表示前i天总里程为j的方案数或者dp[i][j][k]其中k表示第i天的跑步状态如是否高强度以满足“不能连续”之类的约束。建立转移方程思考从第i-1天如何合法地转移到第i天。例如dp[i][j] dp[i-1][j - x]其中x是第i天选择的跑步里程它需要满足题目约束1 x 10且可能与前一天的选择有关。初始化dp[0][0] 1通常表示0天跑0公里有1种方案什么都不做。其他状态初始为0。计算结果最终答案通常是dp[N][M]即N天恰好跑完M公里的方案数。避坑指南状态爆炸如果总天数N和总里程M很大状态数量N * M可能会超出内存或时间限制。这时需要观察数据范围或者思考能否用滚动数组优化空间因为dp[i]只依赖于dp[i-1]。约束条件的处理“不能连续两天都超过5公里”这类约束意味着我们的状态需要“记住”前一天是否高强度。因此状态需要增加一维变成dp[i][j][h]其中h0/1表示第i天是否是高强度。那么转移时如果今天想跑高强度x5就必须从昨天是低强度h0的状态转移过来。模运算方案数往往巨大题目通常会要求对一个大质数如1e97取模。在递推过程中每次加法后就要立即取模防止整数溢出。2.3 套路三贪心选择与最优安排“小明每次跑步后需要休息至少一天才能进行下一次跑步。给定一个未来N天的天气评分分数越高越适合跑步如何选择跑步的日子使得总天气评分最高”这就是一个典型的贪心或DP问题但有时会设计成能用贪心巧妙解决。核心考点贪心策略的证明、区间选择。解题关键识别贪心结构这个问题实际上类似于“不能相邻的最大子序列和”。一个经典的贪心思路是遍历每一天如果今天的天气评分是正数原则上应该跑。但受限于不能连续我们需要一个更系统的办法。动态规划解法更通用定义dp[i][0/1]表示考虑前i天且第i天不跑/跑能获得的最大评分。转移方程为dp[i][0] max(dp[i-1][0], dp[i-1][1])// 第i天不跑前一天跑或不跑都可以。dp[i][1] dp[i-1][0] score[i]// 第i天跑前一天必须不跑。 最终答案是max(dp[N][0], dp[N][1])。贪心解法如果所有天气评分都是非负的那么一个直观的贪心是从第一天开始只要今天能跑前一天没跑且评分0就跑。但这不一定最优。例如评分序列[5, 4, 5]贪心会选择第1、3天总评分10但最优解是第2、? 实际上第1、3天就是最优。更复杂的贪心需要证明。对于填空题数据规模小用DP是稳妥的。避坑指南盲目贪心贪心算法必须要有严格的数学证明否则极易出错。在竞赛中如果对贪心策略没有绝对把握优先使用动态规划等能保证正确性的方法尤其是填空题只要算法正确、复杂度允许就能得到答案。初始化与边界DP的初始状态dp[0][0] 0, dp[0][1] -INF负无穷因为第0天不可能跑。注意天数索引与实际数据的对应关系。2.4 套路四数学建模与组合计数这是最难的一类可能涉及数论、组合数学。例如“小明有一周7天他至少要跑3天且跑步的日子不能全部集中在周末周六、周日。问有多少种不同的每周计划安排”假设只要跑步日的集合不同就算不同计划。核心考点容斥原理、组合数计算。解题关键转化为组合问题从7天中选出至少3天跑步总方案数为C(7,3) C(7,4) C(7,5) C(7,6) C(7,7)。处理约束“不能全部集中在周末”。周末有2天周六、周日。所谓“全部集中在周末”意味着所有跑步的日子都是周末这两天中的。那么跑步日全部是周末的子集有多少种从周末2天中选出至少3天这不可能因为只有2天。所以实际上“全部集中在周末”意味着跑步的日子是周末的一个子集且天数3。但周末最多只有2天所以不存在这样的方案。因此约束条件实际上没有排除任何方案这是一个陷阱。更复杂的约束如果约束是“跑步的日子不能全部是工作日周一到周五”那么我们就需要计算“全部是工作日”的方案数然后用总方案数减去它。这里“全部是工作日”意味着从5个工作日中选出至少3天方案数为C(5,3) C(5,4) C(5,5)。避坑指南仔细理解约束的语义“全部集中在A”是指跑步日的集合是A的子集而不是指A中的每一天都跑步。这是组合计数的常见坑点。善用容斥原理当约束条件是“不能同时满足多个性质”时容斥原理是利器。公式是总方案数 - 违反一个性质的方案数 违反两个性质的方案数 - ...。大数计算与取模组合数C(n, m)在n较大时需要用预处理阶乘和逆元的方法来计算并在计算过程中取模。3. 实战推演构建一个完整的解题流程假设我们遇到一道虚构但符合国赛难度的“跑步计划”填空题题目描述如下“小林决定进行一项为期30天的跑步计划。他每天可以选择跑0,2,4,6公里只能选这些偶数里程。为了可持续发展他规定任何连续三天跑步的总里程不能超过10公里。此外整个30天计划的总里程必须恰好达到80公里。请问小林有多少种不同的计划方案答案可能很大请输出其对1000000007取模的结果。”我们来一步步拆解这道题。3.1 第一步问题抽象与状态定义这显然是一个带有复杂约束的计数问题动态规划是首选方法。约束分析每日选项{0, 2, 4, 6}连续三天约束day[i] day[i-1] day[i-2] 10总里程约束sum(day[1..30]) 80总天数约束30天。状态设计 我们需要记录过去两天的选择才能判断今天的选择是否合法。因此状态需要包含i表示当前是第几天已完成前i天的安排。j表示第i-1天跑的里程。k表示第i-2天跑的里程。s表示前i天累计的总里程。那么我们可以定义dp[i][j][k][s]为完成了前i天的安排且第i-1天跑j公里第i-2天跑k公里累计总里程为s的方案数。状态空间评估i最大30j和k来自集合{0,2,4,6}4种可能s最大为80总里程。状态总数约为30 * 4 * 4 * 81 ≈ 38880完全在可接受范围内。3.2 第二步转移方程与初始化初始化 第0天时没有“前一天”和“前两天”。我们可以引入虚拟的“第-1天”和“第-2天”并假设它们跑了0公里且累计里程为0。这样初始状态可以设为dp[0][0][0][0] 1。其他状态为0。这里dp[0][j][k][s]中的j和k代表“第-1天”和“第-2天”的里程我们固定为0。这是一种常见的技巧将边界条件纳入状态。转移方程 现在我们要安排第i天i从1到30的里程xx ∈ {0, 2, 4, 6}。 转移的前提是必须满足连续三天约束x j k 10。 如果满足那么状态可以从dp[i-1][j][k][s]转移到dp[i][x][j][s x]。 用伪代码表示就是for i in [1, 30]: for j in {0,2,4,6}: for k in {0,2,4,6}: for s in [0, 80]: if dp[i-1][j][k][s] 0: for x in {0,2,4,6}: if x j k 10 and s x 80: dp[i][x][j][s x] dp[i-1][j][k][s] dp[i][x][j][s x] % MOD最终答案 我们需要的是30天结束后总里程恰好为80的所有方案。即我们需要对所有的j,k求和ans sum( dp[30][j][k][80] for j in {0,2,4,6} for k in {0,2,4,6} ) % MOD3.3 第三步代码实现与细节处理虽然填空题不需要提交代码但我们必须通过编写程序来求解答案。这里有几个实现细节至关重要。细节1状态索引映射j和k的取值范围是{0,2,4,6}有4个值。在代码中用数组存储时我们更习惯用连续的索引0,1,2,3。因此需要建立一个映射value - index。例如idx {0:0, 2:1, 4:2, 6:3}。在转移时用索引来访问数组。细节2滚动数组优化注意到dp[i]只依赖于dp[i-1]我们可以使用滚动数组将空间复杂度从O(天数*4*4*81)降到O(2*4*4*81)。我们只需要两个三维数组dp_cur和dp_pre交替使用。细节3模运算每次加法后立即取模防止中间结果溢出即使在Python中取模操作也能保证结果范围。一个简化的Python求解框架MOD 1000000007 values [0, 2, 4, 6] V len(values) # 4 days 30 target 80 # 初始化dp_pre: dp_pre[j_idx][k_idx][s] # 第0天虚拟的第-1天和第-2天里程为0总里程为0 dp_pre [[[0]*(target1) for _ in range(V)] for _ in range(V)] dp_pre[0][0][0] 1 # j_idx0对应0公里k_idx0对应0公里 for i in range(1, days1): dp_cur [[[0]*(target1) for _ in range(V)] for _ in range(V)] for j_idx in range(V): for k_idx in range(V): for s in range(target1): if dp_pre[j_idx][k_idx][s] 0: continue val_j values[j_idx] val_k values[k_idx] for x_idx, x in enumerate(values): if x val_j val_k 10 and s x target: dp_cur[x_idx][j_idx][s x] (dp_cur[x_idx][j_idx][s x] dp_pre[j_idx][k_idx][s]) % MOD dp_pre dp_cur ans 0 for j_idx in range(V): for k_idx in range(V): ans (ans dp_pre[j_idx][k_idx][target]) % MOD print(ans)运行这段代码我们就可以得到最终的答案这里是一个示例框架实际数值需要运行计算。3.4 第四步验证与思考得到答案后我们如何进行快速验证确保大概率正确呢小规模测试将天数改为3天总里程目标改为一个较小的值如4公里手动枚举所有合法计划与程序输出对比。这是验证DP逻辑最有效的方法。检查边界总里程80是否可达每天最多6公里30天最多180公里80是可达的。连续三天约束是否过严最极端的三天是64010或62210或44210。这意味着不能出现6,4,2或6,6,?这样的连续组合。约束是合理的。答案合理性如果程序跑出的结果是一个非常大的数比如几百万、上千万对于30天、状态空间不大的DP来说是合理的。如果结果非常小比如个位数或者为0就需要回头检查约束条件是否理解有误或者初始化、转移过程是否有bug。4. 填空题的终极考验思维陷阱与易错点复盘即使掌握了方法填空题仍然可能因为一些隐蔽的陷阱而失分。结合“跑步计划”这类题目我总结了几条血泪教训。4.1 陷阱一对“连续”概念的误解题目说“任何连续三天跑步的总里程不能超过10公里”。这里的“连续三天”是指日历上连续的三天还是指有跑步活动的连续三天通常是前者即只要时间上连续无论其中是否有0公里休息的日子都算连续三天。例如[6, 0, 6]这三天总里程是12超过了10是违反规则的。很多同学会误以为只计算“跑步日”忽略了休息日0公里也占一天。这是最大的思维陷阱之一。在定义状态转移时我们的约束判断x j k 10正是基于这种理解j和k可能是0。4.2 陷阱二起始与结束的边界处理在我们的DP状态设计中我们引入了虚拟的“第-1天”和“第-2天”并假设其里程为0。这巧妙地处理了开头两天的约束问题。对于第1天它的“前两天”和“前一天”都是虚拟的0因此只需满足x 0 0 10这总是成立。对于第2天它的“前两天”是虚拟的0“前一天”是第1天的里程j约束为x j 0 10。这完全符合题意。如果不这样处理就需要单独为第1天和第2天写特殊的转移逻辑代码会变得复杂且容易出错。这种“增加虚拟状态以统一处理”的技巧在DP中非常实用。4.3 陷阱三答案取模的时机题目要求输出答案对1000000007取模。这里有两个关键点必须在计算过程中取模而不是最后才取模。因为中间累加的结果可能已经远超64位整数范围虽然在Python中无所谓但在C/Java中会溢出。养成在每次加法、乘法后立即取模的习惯。最终答案取模后可能为0。如果答案是1000000007的倍数取模后就是0。如果你得到0不要立刻以为自己做错了要检查逻辑。当然更常见的是题目设计的答案通常不会恰好是模数的倍数。4.4 陷阱四盲目相信样例或直觉有些填空题会提供样例输入输出。但请注意填空题的样例可能非常具有误导性出题人有时会用一个简单的、特殊的样例其计算路径可能掩盖了真正的复杂情况。例如样例可能总天数很短如3天使得某些约束根本不起作用。因此在通过样例后一定要自己设计几个更复杂、更能体现约束条件的测试用例比如测试连续三天约束的边界构造[4,4,4]总和1210是否被正确排除测试总里程约束总里程超过目标或不足目标时方案数是否为0测试极值每天跑0公里总里程0是否只有1种方案如果目标里程是0只有通过了这些针对性测试你才能对算法的正确性有足够的信心。5. 从解题到备赛如何高效利用真题训练最后我想分享一下如何将这类填空题的练习价值最大化。刷题不是目的通过题目训练思维模式才是。第一步严格模拟考试环境找一道陌生的填空题设定一个合理的时间比如20-30分钟准备纸笔。不要打开编译器先完全用脑和纸笔分析。写出关键的状态定义、转移方程、初始化条件和最终答案表达式。这个过程能极大锻炼你的抽象建模能力。很多同学离开IDE就不会思考了这是大忌。第二步实现与验证时间到后再用电脑实现代码。此时你会发现自己纸上推导的漏洞可能是边界条件可能是循环顺序也可能是某个细节理解偏差。将这些错误记录下来形成一个专属的“易错点清单”。例如“DP状态设计时经常忘记记录总重量/总里程等累加约束”、“日期计算题总是搞不清第N天是否包含起始日”。第三步举一反三解完一道“跑步计划”主动去寻找同类型题目。例如蓝桥杯真题中可能有“砝码称重”、“数字三角形”、“礼物采购”等问题它们的内核都是约束条件下的计数或优化。尝试用今天总结的“四大套路”去套用看它们分别属于哪一类并比较状态设计上的异同。这样就能将一道题的经验扩散到一类题。第四步总结模板与技巧将一些通用的技巧固化下来。比如DP状态设计口诀“当前阶段 对后续决策有影响的过去信息 累积量”。日期周期问题“先算偏移量再取模注意边界天”。组合计数问题“正难则反善用容斥”。填空题验证“小数据暴力枚举对拍”。把这些心得记在笔记里每次练习前看一遍形成肌肉记忆。回到“跑步计划”这道题它更像一个载体承载的是对动态规划、状态压缩、边界处理、问题建模等综合能力的考察。国赛的填空题从来不会考你记忆模板它考的是你在陌生问题面前能否快速拆解、准确建模、严谨实现。希望这篇长文拆解的思路和陷阱能帮助你下次面对任何“计划”、“安排”、“方案数”问题时都能有条不紊地找到那把关键的钥匙。真正的提升就来自于这种从一道题到一类题的深度思考和反复锤炼。
蓝桥杯国赛“跑步计划”类填空题解题套路与动态规划实战
1. 从一道国赛填空题说起跑步计划最近在整理蓝桥杯的历年真题特别是国赛级别的题目发现很多同学对填空题有种又爱又恨的感觉。爱的是它不像编程大题那样需要完整的代码框架和复杂的调试似乎“门槛”低一些恨的是填空题往往考察的是对算法核心逻辑的极致理解、对边界条件的敏锐洞察以及那么一点点的“灵光一现”。一个微小的疏忽就可能导致答案谬以千里前功尽弃。今天想和大家深入聊聊的就是一道典型的国赛填空题——“跑步计划”。这道题本身没有出现在我手头最全的公开真题库里但“跑步计划”这个名称非常具有代表性它指向了一类经典的规划与优化问题。这类问题在蓝桥杯乃至各类算法竞赛中屡见不鲜其内核往往是动态规划、贪心算法或者是基于日期、星期的周期性计算。它考察的不仅仅是写出一个能跑的代码更是如何在有限的时间内通过逻辑推理和数学建模找到那个确定无疑的答案。对于备赛的同学来说研究这类题目比单纯刷编程大题更有价值。因为填空题的求解过程本质上是对你算法思维严密性的一次高压测试。你需要自己设计数据结构和算法自己验证边界最终输出一个数字或字符串。这个过程里没有在线评测系统给你反馈“答案错误”你只能依靠自己的逻辑来保证正确性。这恰恰是算法能力的核心。所以这篇文章我不会直接给出某道特定“跑步计划”题的答案——那样没有意义。我将以“跑步计划”为引子拆解这类问题常见的出题套路、核心的解题框架以及我们在实战中必须警惕的那些“坑”。我会假设几种最有可能的题目背景比如基于星期的训练计划、基于目标里程的动态规划、或者带有约束条件的最优安排然后手把手带你走过完整的分析、建模、求解和验证流程。我们的目标不是解一道题而是掌握解一类题的方法。2. 拆解“跑步计划”类题目的四大核心套路在真正动手解题之前我们必须先判断题目属于哪种类型。根据“跑步计划”这个名称和蓝桥杯国赛的命题风格我梳理了四种最有可能的出题方向。每一种方向对应的解题工具和思考重心都完全不同。2.1 套路一周期性日期计算这是最直观也可能最简单的一种。题目可能会这样描述“小明从2023年3月1日星期三开始执行跑步计划他计划每周一、三、五跑步每周日休息其余时间力量训练。请问第100天时他在进行什么训练”或者“从某年某月某日开始按照某个固定周期循环执行计划问第N天或某个特定日期的状态。”核心考点日期处理、取模运算、周期循环。解题关键确定最小正周期通常是7天一周但有时计划可能以两周或更长时间为周期。建立映射关系将周期内的每一天映射到一个具体的活动跑步、休息、力量等。通常用一个数组来表示。计算偏移量计算目标日期相对于起始日期过去了多少天。这里要小心是否需要考虑起始日期当天是第0天还是第1天这是一个高频易错点。取模定位将总天数偏移量对周期长度取模得到的余数就是目标日期在周期中的位置通过映射数组即可查到活动。避坑指南边界日务必明确“第N天”是否包含起始日。常见的歧义是如果从第一天开始那么“第一天后”是第二天而“第一天”就是起始日。题目通常会说“从当天开始计算”或“经过N天后”需要仔细辨析。闰年与月份如果计划跨年或涉及具体月份就需要实现准确的日期推移函数考虑闰年能被4整除但不能被100整除或者能被400整除的年份和各个月份的天数。索引从0还是1开始编程时我们的数组索引通常从0开始。如果周期是7天那么days % 7的结果是0~6需要清晰地定义plan[0]对应的是周期内的哪一天比如是起始日对应的活动。2.2 套路二基于规则的递推或动态规划这类题目难度会上一个台阶。例如“小明想通过N天达到总跑步里程M公里。他每天最多跑10公里且为了健康不能连续两天都跑超过5公里。请问他有多少种不同的跑步计划每天里程数为正整数”或者“每次跑步会消耗体力恢复体力需要时间如何安排计划使得总收益最大”。核心考点动态规划DP的状态设计与转移方程。解题关键定义状态这是最难也是最关键的一步。状态必须能够唯一描述一个“子问题”的局面。对于跑步计划状态维度通常包括dp[i][j]表示前i天总里程为j的方案数或者dp[i][j][k]其中k表示第i天的跑步状态如是否高强度以满足“不能连续”之类的约束。建立转移方程思考从第i-1天如何合法地转移到第i天。例如dp[i][j] dp[i-1][j - x]其中x是第i天选择的跑步里程它需要满足题目约束1 x 10且可能与前一天的选择有关。初始化dp[0][0] 1通常表示0天跑0公里有1种方案什么都不做。其他状态初始为0。计算结果最终答案通常是dp[N][M]即N天恰好跑完M公里的方案数。避坑指南状态爆炸如果总天数N和总里程M很大状态数量N * M可能会超出内存或时间限制。这时需要观察数据范围或者思考能否用滚动数组优化空间因为dp[i]只依赖于dp[i-1]。约束条件的处理“不能连续两天都超过5公里”这类约束意味着我们的状态需要“记住”前一天是否高强度。因此状态需要增加一维变成dp[i][j][h]其中h0/1表示第i天是否是高强度。那么转移时如果今天想跑高强度x5就必须从昨天是低强度h0的状态转移过来。模运算方案数往往巨大题目通常会要求对一个大质数如1e97取模。在递推过程中每次加法后就要立即取模防止整数溢出。2.3 套路三贪心选择与最优安排“小明每次跑步后需要休息至少一天才能进行下一次跑步。给定一个未来N天的天气评分分数越高越适合跑步如何选择跑步的日子使得总天气评分最高”这就是一个典型的贪心或DP问题但有时会设计成能用贪心巧妙解决。核心考点贪心策略的证明、区间选择。解题关键识别贪心结构这个问题实际上类似于“不能相邻的最大子序列和”。一个经典的贪心思路是遍历每一天如果今天的天气评分是正数原则上应该跑。但受限于不能连续我们需要一个更系统的办法。动态规划解法更通用定义dp[i][0/1]表示考虑前i天且第i天不跑/跑能获得的最大评分。转移方程为dp[i][0] max(dp[i-1][0], dp[i-1][1])// 第i天不跑前一天跑或不跑都可以。dp[i][1] dp[i-1][0] score[i]// 第i天跑前一天必须不跑。 最终答案是max(dp[N][0], dp[N][1])。贪心解法如果所有天气评分都是非负的那么一个直观的贪心是从第一天开始只要今天能跑前一天没跑且评分0就跑。但这不一定最优。例如评分序列[5, 4, 5]贪心会选择第1、3天总评分10但最优解是第2、? 实际上第1、3天就是最优。更复杂的贪心需要证明。对于填空题数据规模小用DP是稳妥的。避坑指南盲目贪心贪心算法必须要有严格的数学证明否则极易出错。在竞赛中如果对贪心策略没有绝对把握优先使用动态规划等能保证正确性的方法尤其是填空题只要算法正确、复杂度允许就能得到答案。初始化与边界DP的初始状态dp[0][0] 0, dp[0][1] -INF负无穷因为第0天不可能跑。注意天数索引与实际数据的对应关系。2.4 套路四数学建模与组合计数这是最难的一类可能涉及数论、组合数学。例如“小明有一周7天他至少要跑3天且跑步的日子不能全部集中在周末周六、周日。问有多少种不同的每周计划安排”假设只要跑步日的集合不同就算不同计划。核心考点容斥原理、组合数计算。解题关键转化为组合问题从7天中选出至少3天跑步总方案数为C(7,3) C(7,4) C(7,5) C(7,6) C(7,7)。处理约束“不能全部集中在周末”。周末有2天周六、周日。所谓“全部集中在周末”意味着所有跑步的日子都是周末这两天中的。那么跑步日全部是周末的子集有多少种从周末2天中选出至少3天这不可能因为只有2天。所以实际上“全部集中在周末”意味着跑步的日子是周末的一个子集且天数3。但周末最多只有2天所以不存在这样的方案。因此约束条件实际上没有排除任何方案这是一个陷阱。更复杂的约束如果约束是“跑步的日子不能全部是工作日周一到周五”那么我们就需要计算“全部是工作日”的方案数然后用总方案数减去它。这里“全部是工作日”意味着从5个工作日中选出至少3天方案数为C(5,3) C(5,4) C(5,5)。避坑指南仔细理解约束的语义“全部集中在A”是指跑步日的集合是A的子集而不是指A中的每一天都跑步。这是组合计数的常见坑点。善用容斥原理当约束条件是“不能同时满足多个性质”时容斥原理是利器。公式是总方案数 - 违反一个性质的方案数 违反两个性质的方案数 - ...。大数计算与取模组合数C(n, m)在n较大时需要用预处理阶乘和逆元的方法来计算并在计算过程中取模。3. 实战推演构建一个完整的解题流程假设我们遇到一道虚构但符合国赛难度的“跑步计划”填空题题目描述如下“小林决定进行一项为期30天的跑步计划。他每天可以选择跑0,2,4,6公里只能选这些偶数里程。为了可持续发展他规定任何连续三天跑步的总里程不能超过10公里。此外整个30天计划的总里程必须恰好达到80公里。请问小林有多少种不同的计划方案答案可能很大请输出其对1000000007取模的结果。”我们来一步步拆解这道题。3.1 第一步问题抽象与状态定义这显然是一个带有复杂约束的计数问题动态规划是首选方法。约束分析每日选项{0, 2, 4, 6}连续三天约束day[i] day[i-1] day[i-2] 10总里程约束sum(day[1..30]) 80总天数约束30天。状态设计 我们需要记录过去两天的选择才能判断今天的选择是否合法。因此状态需要包含i表示当前是第几天已完成前i天的安排。j表示第i-1天跑的里程。k表示第i-2天跑的里程。s表示前i天累计的总里程。那么我们可以定义dp[i][j][k][s]为完成了前i天的安排且第i-1天跑j公里第i-2天跑k公里累计总里程为s的方案数。状态空间评估i最大30j和k来自集合{0,2,4,6}4种可能s最大为80总里程。状态总数约为30 * 4 * 4 * 81 ≈ 38880完全在可接受范围内。3.2 第二步转移方程与初始化初始化 第0天时没有“前一天”和“前两天”。我们可以引入虚拟的“第-1天”和“第-2天”并假设它们跑了0公里且累计里程为0。这样初始状态可以设为dp[0][0][0][0] 1。其他状态为0。这里dp[0][j][k][s]中的j和k代表“第-1天”和“第-2天”的里程我们固定为0。这是一种常见的技巧将边界条件纳入状态。转移方程 现在我们要安排第i天i从1到30的里程xx ∈ {0, 2, 4, 6}。 转移的前提是必须满足连续三天约束x j k 10。 如果满足那么状态可以从dp[i-1][j][k][s]转移到dp[i][x][j][s x]。 用伪代码表示就是for i in [1, 30]: for j in {0,2,4,6}: for k in {0,2,4,6}: for s in [0, 80]: if dp[i-1][j][k][s] 0: for x in {0,2,4,6}: if x j k 10 and s x 80: dp[i][x][j][s x] dp[i-1][j][k][s] dp[i][x][j][s x] % MOD最终答案 我们需要的是30天结束后总里程恰好为80的所有方案。即我们需要对所有的j,k求和ans sum( dp[30][j][k][80] for j in {0,2,4,6} for k in {0,2,4,6} ) % MOD3.3 第三步代码实现与细节处理虽然填空题不需要提交代码但我们必须通过编写程序来求解答案。这里有几个实现细节至关重要。细节1状态索引映射j和k的取值范围是{0,2,4,6}有4个值。在代码中用数组存储时我们更习惯用连续的索引0,1,2,3。因此需要建立一个映射value - index。例如idx {0:0, 2:1, 4:2, 6:3}。在转移时用索引来访问数组。细节2滚动数组优化注意到dp[i]只依赖于dp[i-1]我们可以使用滚动数组将空间复杂度从O(天数*4*4*81)降到O(2*4*4*81)。我们只需要两个三维数组dp_cur和dp_pre交替使用。细节3模运算每次加法后立即取模防止中间结果溢出即使在Python中取模操作也能保证结果范围。一个简化的Python求解框架MOD 1000000007 values [0, 2, 4, 6] V len(values) # 4 days 30 target 80 # 初始化dp_pre: dp_pre[j_idx][k_idx][s] # 第0天虚拟的第-1天和第-2天里程为0总里程为0 dp_pre [[[0]*(target1) for _ in range(V)] for _ in range(V)] dp_pre[0][0][0] 1 # j_idx0对应0公里k_idx0对应0公里 for i in range(1, days1): dp_cur [[[0]*(target1) for _ in range(V)] for _ in range(V)] for j_idx in range(V): for k_idx in range(V): for s in range(target1): if dp_pre[j_idx][k_idx][s] 0: continue val_j values[j_idx] val_k values[k_idx] for x_idx, x in enumerate(values): if x val_j val_k 10 and s x target: dp_cur[x_idx][j_idx][s x] (dp_cur[x_idx][j_idx][s x] dp_pre[j_idx][k_idx][s]) % MOD dp_pre dp_cur ans 0 for j_idx in range(V): for k_idx in range(V): ans (ans dp_pre[j_idx][k_idx][target]) % MOD print(ans)运行这段代码我们就可以得到最终的答案这里是一个示例框架实际数值需要运行计算。3.4 第四步验证与思考得到答案后我们如何进行快速验证确保大概率正确呢小规模测试将天数改为3天总里程目标改为一个较小的值如4公里手动枚举所有合法计划与程序输出对比。这是验证DP逻辑最有效的方法。检查边界总里程80是否可达每天最多6公里30天最多180公里80是可达的。连续三天约束是否过严最极端的三天是64010或62210或44210。这意味着不能出现6,4,2或6,6,?这样的连续组合。约束是合理的。答案合理性如果程序跑出的结果是一个非常大的数比如几百万、上千万对于30天、状态空间不大的DP来说是合理的。如果结果非常小比如个位数或者为0就需要回头检查约束条件是否理解有误或者初始化、转移过程是否有bug。4. 填空题的终极考验思维陷阱与易错点复盘即使掌握了方法填空题仍然可能因为一些隐蔽的陷阱而失分。结合“跑步计划”这类题目我总结了几条血泪教训。4.1 陷阱一对“连续”概念的误解题目说“任何连续三天跑步的总里程不能超过10公里”。这里的“连续三天”是指日历上连续的三天还是指有跑步活动的连续三天通常是前者即只要时间上连续无论其中是否有0公里休息的日子都算连续三天。例如[6, 0, 6]这三天总里程是12超过了10是违反规则的。很多同学会误以为只计算“跑步日”忽略了休息日0公里也占一天。这是最大的思维陷阱之一。在定义状态转移时我们的约束判断x j k 10正是基于这种理解j和k可能是0。4.2 陷阱二起始与结束的边界处理在我们的DP状态设计中我们引入了虚拟的“第-1天”和“第-2天”并假设其里程为0。这巧妙地处理了开头两天的约束问题。对于第1天它的“前两天”和“前一天”都是虚拟的0因此只需满足x 0 0 10这总是成立。对于第2天它的“前两天”是虚拟的0“前一天”是第1天的里程j约束为x j 0 10。这完全符合题意。如果不这样处理就需要单独为第1天和第2天写特殊的转移逻辑代码会变得复杂且容易出错。这种“增加虚拟状态以统一处理”的技巧在DP中非常实用。4.3 陷阱三答案取模的时机题目要求输出答案对1000000007取模。这里有两个关键点必须在计算过程中取模而不是最后才取模。因为中间累加的结果可能已经远超64位整数范围虽然在Python中无所谓但在C/Java中会溢出。养成在每次加法、乘法后立即取模的习惯。最终答案取模后可能为0。如果答案是1000000007的倍数取模后就是0。如果你得到0不要立刻以为自己做错了要检查逻辑。当然更常见的是题目设计的答案通常不会恰好是模数的倍数。4.4 陷阱四盲目相信样例或直觉有些填空题会提供样例输入输出。但请注意填空题的样例可能非常具有误导性出题人有时会用一个简单的、特殊的样例其计算路径可能掩盖了真正的复杂情况。例如样例可能总天数很短如3天使得某些约束根本不起作用。因此在通过样例后一定要自己设计几个更复杂、更能体现约束条件的测试用例比如测试连续三天约束的边界构造[4,4,4]总和1210是否被正确排除测试总里程约束总里程超过目标或不足目标时方案数是否为0测试极值每天跑0公里总里程0是否只有1种方案如果目标里程是0只有通过了这些针对性测试你才能对算法的正确性有足够的信心。5. 从解题到备赛如何高效利用真题训练最后我想分享一下如何将这类填空题的练习价值最大化。刷题不是目的通过题目训练思维模式才是。第一步严格模拟考试环境找一道陌生的填空题设定一个合理的时间比如20-30分钟准备纸笔。不要打开编译器先完全用脑和纸笔分析。写出关键的状态定义、转移方程、初始化条件和最终答案表达式。这个过程能极大锻炼你的抽象建模能力。很多同学离开IDE就不会思考了这是大忌。第二步实现与验证时间到后再用电脑实现代码。此时你会发现自己纸上推导的漏洞可能是边界条件可能是循环顺序也可能是某个细节理解偏差。将这些错误记录下来形成一个专属的“易错点清单”。例如“DP状态设计时经常忘记记录总重量/总里程等累加约束”、“日期计算题总是搞不清第N天是否包含起始日”。第三步举一反三解完一道“跑步计划”主动去寻找同类型题目。例如蓝桥杯真题中可能有“砝码称重”、“数字三角形”、“礼物采购”等问题它们的内核都是约束条件下的计数或优化。尝试用今天总结的“四大套路”去套用看它们分别属于哪一类并比较状态设计上的异同。这样就能将一道题的经验扩散到一类题。第四步总结模板与技巧将一些通用的技巧固化下来。比如DP状态设计口诀“当前阶段 对后续决策有影响的过去信息 累积量”。日期周期问题“先算偏移量再取模注意边界天”。组合计数问题“正难则反善用容斥”。填空题验证“小数据暴力枚举对拍”。把这些心得记在笔记里每次练习前看一遍形成肌肉记忆。回到“跑步计划”这道题它更像一个载体承载的是对动态规划、状态压缩、边界处理、问题建模等综合能力的考察。国赛的填空题从来不会考你记忆模板它考的是你在陌生问题面前能否快速拆解、准确建模、严谨实现。希望这篇长文拆解的思路和陷阱能帮助你下次面对任何“计划”、“安排”、“方案数”问题时都能有条不紊地找到那把关键的钥匙。真正的提升就来自于这种从一道题到一类题的深度思考和反复锤炼。