从读懂题目到独立完成一道题
学到这里,C++ 语法、容器和算法已经能连成一条解题过程:把题目中的对象和规则写清楚,用具体数据手算,提出模型,证明计算方法,再把它写成程序。程序得到答案后,还要核对输出、工作量和每一步留下的状态。
回看各章,可以把这条过程记成几件具体的事:
- 先明确要计算什么。 “存在一组”“统计所有组”“求最优值”“输出方案”需要的信息不同。相同取值、不同位置、连续片段这些词,也会改变合法方案。
- 从能解释的做法出发。 先枚举小数据,再找重复计算、可以排除的候选或可以共享的状态。优化前后的程序应该回答同一个问题。
- 给每个状态写一句含义。 频次只包含过去的位置,BFS 的距离来自首次发现,DP 的一个格子对应某个子问题。状态含义清楚,更新次序就有了依据。
- 把公式接回实际方案。 状态转移方程中的每一项,都要能说出从哪里来、做了什么动作、为什么可以合并;数值算对之后,还可以沿记录恢复具体方案。
- 用差异定位错误。 WA 时找第一处与手算不同的状态,缩小输入,再对照题面的句子和程序的更新次序。修正后留下这个输入,供下一次检查。
理解一种方法,可以用一个小任务检验:合上代码,给别人讲清变量的含义,拿一组数据走完过程,然后自己写出实现。卡在某一步,就回到那一步对应的图、推导和例题。