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

(二) 把关键词翻译成条件

自然语言 形式化表达 对代码的影响
至少 k 个 count >= k 等于 k 也合法
至多 k 个 count <= k 不能错误地写成 < k
恰好 k 个 count == k 不能只检查上下界之一
A 且 B A && B 两个条件同时满足
A 或 B,至少一个成立 A || B 包括两个都成立
A、B 恰好一个成立 A != B,其中 A、B 是 bool 区别于普通“或”
不满足 A !A 对复杂条件注意括号
任意 / 所有元素满足 对每个元素检查 发现一个反例就失败
存在一个元素满足 找到一个即可 不能要求全部成立
两个不同的下标 i != j 排序后也不能重复使用同一元素

“至少一个满足”与“全部满足”是不同的量词。一个常见错误是看到某个元素不满足就返回失败,而题目实际只要求存在一个满足的元素。

德摩根律常用于改写不合法条件:

\[ \neg(A\land B)=(\neg A)\lor(\neg B),\qquad \neg(A\lor B)=(\neg A)\land(\neg B) \]

例如 !(x >= 0 && x < n) 等价于 x < 0 || x >= n。

存在一个与所有元素满足条件的区别

同一数组上,“存在一个正数”与“所有元素都是正数”会得到不同的真假结果。

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