CSP-J - 复习 - 米缸
2026-09-05 11:25:42
发布于:上海
1.识别信号
贪心信号:
关键词:“最多”,“最少”,“最大”,“最小”。
特征:排序后有单调性。
验证:交换论证能证明贪心的正确性。
典型场景:按某个属性排序后遍历,每次只考虑当下的最优解且不影响后续的最优性。
时间复杂度:O(n log n) N < 1e6。时间开销主要在排序。
DP信号:
关键词:“最大 or 最小” , “恰好” , “方案数”。
特征:有约束导致选择冲突,贪心策略会找到反例,一个选择会影响另一个选择的可行性。
验证:举反例 ---- 尝试贪心看看能不能构造出“贪心选了A导致错过更好的B的情况”。
典型场景:序列选择(前面的数字选或不选会影响后面),背包(容量有限,每个物品要考虑拿或者不拿,每个决策都会影响后续的选择),区间问题(只能操作相邻的区间元素)
时间复杂度:一般大于O(n^2) , N <= 1e4。
二分信号:
关键词:“最大值最小”,“最小值最小”。
套路:二分答案 + check 函数。
典型场景:“最短路最大化”,“最大段和最小化”。
时间复杂度:O(n log n) , N <= 1e6。
总结:
看到最值问题 -> 先猜贪心 -> 交换论证一下 -> 验证通过选贪心 -> 否则转DP,二分。‘
2.交换论证法
这里空空如也






















有帮助,赞一个