C++ / ACM 自学笔记 · v5.0

(一) 先提取对象、变量、限制和目标

读题时可以先写下面四项:

项目 要回答的问题 示例
对象 要处理哪些东西? n 件物品、m 个区间、一个字符串
变量 哪些值已知,哪些值需要求? 已知高度 h[i],求符合条件的数量
限制 哪些操作或状态合法? 每件只能选一次、两人不能用同一个位置
目标 最终输出什么? 是否存在、方案数、最小花费、具体方案

不要把故事中的无关信息都存入程序。例如“仓库有不同颜色的盒子”,如果颜色不影响规则,通常就不需要颜色变量。

数据范围也是题意的一部分。 正数与任意整数会影响滑动窗口的单调性;边权是否非负会影响最短路算法;能否重复选择会影响背包转移方向。

把分成两个正偶数的题意转为等价条件

把原要求翻译成约束之后,还要分别证明必要性和充分性;后面会给出完整程序。

查阅笔记正文与全部题解 · Ctrl / ⌘ K