贪心与图论并列第一，各 8 题，合计 16/30 = 53%。 CSP-S 复赛一半以上的题目，关键技术是贪心或图论。

本讲回答"考场上看到什么就该想到贪心，以及 S 组的贪心有哪几种长相"

---

1. 贪心和图论：

三条推论：

1. 图论在 CSP-S 复赛七年里，一次都没有当过 S 层的送分题。 它全部是 S⭐ 或 S⭐⭐。
2. 贪心有一半是 S 层，而且 T1 位置出现 3 次——2021 廊桥分配、2024 决斗、2025 社团招新。
3. 所以：

贪心是拿分线，图论是拉分线。

对冲 S 一等的人：那 100 分的主体在贪心里，不在图论里。 图论只需要拿部分分。

这一个月，贪心要练到"不出错"，图论只要练到"认得出、写得动暴力"

---

2. 三道 S 层的 T1 贪心：S 一等的 100 分

每道题的推理链和代码骨架。

三道题的共同形态：

题面给一个看起来复杂的过程
      ↓
有一个"看起来多余"的条件
      ↓
这个条件把问题塌缩成一句话
      ↓
代码 20~40 行

那个"看起来多余"的条件就是解法。 读 S 组 T1 时，看到任何一个不参与题意描述的限制（"$n$ 为偶数"、"上限 $n/2$"、"互不相同"、"保证 $k$ 固定"），先问一句：它是干什么用的。

2.1 2024 T1 决斗（P11231）· 众数即答案

题意：$n$ 个怪兽各有攻击力，每轮攻击力最大的可以吃掉攻击力最小的（同攻击力不能互吃），问最后最少剩几只。

那个条件：「同攻击力不能互吃」。

推理链：

1. 攻击力相同的一组（设有 $c$ 只）内部谁也吃不掉谁 → 它们只能被更大的吃。
2. 一只大的一轮吃一只 → 要把这 $c$ 只消到只剩 1 只，需要足够多的"外部"来吃 → 答案下界 = 众数出现次数。
3. 构造：每轮让最大的去吃当前人数最多那一组里的一只 → 下界可以取到。

骨架：

读入 a[1..n]
统计每个值的出现次数（桶 / 排序 / map）
答案 = 最大出现次数

失分点：值域大时忘了离散化；推出结论后不敢写（见 §5.1）。

2.2 2025 T1 社团招新（P14361）· 抽屉原理

题意：$n$ 名新生（$n$ 为偶数）各有首选社团，每个社团人数不能超过 $n/2$，把所有人分配掉。

那个条件：「$n$ 为偶数」+「上限 $n/2$」。

推理链：

1. 统计每个社团的首选人数 $c_i$，有 $\sum c_i = n$。
2. 若两个社团都有 $c_i > n/2$，则 $\sum c_i > n$，矛盾 → 最多只有一个社团超限。这就是抽屉。
3. 没有超限 → 全按首选分配，收工。
4. 有一个超限 → 只处理这一个，把多出的人分给别处。

骨架：

统计 c[1..m]
找出是否存在 c[i] > n/2
  否 → 全按首选输出
  是 → 对这一个社团保留 n/2 人，其余改派

失分点：没看出抽屉，去写匹配 / 网络流（本题最高频的失败模式）。

2.3 2021 T1 廊桥分配（P7913）· 枚举分界点

题意：机场有国内、国际两类航班共用 $m$ 个廊桥，要把廊桥分给两类，最大化能停靠的航班总数。

那个条件：「廊桥数一旦确定，分配规则就固定了」。

推理链：

1. 给定廊桥数 $k$ 时，"谁先来谁先用空闲廊桥"的贪心是最优的——这一步要用交换论证说服自己（basic-series/03 §4）。
2. 于是国内和国际可以独立算：$f(k)$ = 国内用 $k$ 个廊桥能停多少架，$g(k)$ 同理，各 $O(n\log n)$。
3. 枚举分界点：答案 $=\max_{k=0}^{m}\big(f(k)+g(m-k)\big)$。

这个结构值得单独记住：

"两个部分共享一个总量，求最优划分" → 各自算出前缀函数，再枚举分界点。

S 组反复出现这个套路。

失分点：优先队列比较器写反；$f$ 的递推没利用单调性导致 $O(nm)$ 超时。

2.4 2022 T2 策略游戏（P8818）· 分类讨论正负

这是第四道 S 层贪心，位置在 T2（对应本系列模拟卷的 T4，卷三的 T3）。

题意：数组 $A$（长 $n$）、$B$（长 $m$），小 L 先从给定区间里选 $A$ 的一个数，小 Q 再从区间里选 $B$ 的一个数，小 L 要最大化乘积、小 Q 要最小化。

推理链：

1. 乘积的极值只可能在两边各自的极值处取到 → 只需要区间的 最大正、最小正、最大负、最小负（或直接最大值/最小值）。
2. 用前缀极值或 ST 表 $O(1)$ 查区间极值。
3. 剩下全是正负号的分类讨论：小 L 选正数时希望 $B$ 的正数小、负数不存在；选负数时反过来……

这道题没有算法门槛，全是分类。 丢分的人几乎全都是漏了某一种正负组合，不是不会 ST 表。

做法：写之前在草稿纸上把所有正负组合编号列全（$A$ 正/负 × $B$ 全正/全负/有正有负），写完逐条对。

---

3. S 组贪心的五种形态

把八道题归类，S 组的贪心一共就这几种长相：

形态	题	识别信号
① 统计即答案	决斗、社团招新	题面有一个"多余"的限制条件；数据范围只允许 $O(n)$
② 枚举分界点	廊桥分配	两部分共享一个总量，各自可独立计算
③ 区间覆盖 / 点覆盖	超速检测	"最少选几个点覆盖所有区间"、"最少几次操作"
④ 两端决策	回文	从序列两头往中间取，每步选左或右
⑤ 带数据结构的贪心	贪吃蛇、种树	贪心的每一步需要"当前最大/最小"，要用堆、双端队列或线段树维护

形态 ①②④ 属于 S / S⭐，是要拿的；形态 ⑤ 的两道都是 S⭐⭐，只拿部分分。

3.1 形态③：区间点覆盖（2024 T2 超速检测 P11232）

这是 S⭐ 里最该拿下的一道，因为它的套路是纯经典的。

档	做法
低	$O(nm)$ 暴力：对每辆车枚举每个检测点
中	先算出每辆车会被哪一段区间内的检测点抓到
满分	区间点覆盖：按右端点排序，贪心选右端点，二分定位

关键转化：先把"车 $i$ 在哪一段路程上超速"算成一个区间，问题就变成课本上的「最少选多少个点覆盖所有区间」。

经典结论（basic-series/03 §3 有证明）：按右端点排序，每次选当前未被覆盖区间的右端点，是最优的。

失分点：区间端点开闭搞错；二分边界；忘了处理"这辆车根本不超速"。

3.2 形态④：两端决策（2021 T3 回文 P7915）

识别信号：从序列两头往中间取，每一步只能取左端或右端。

做法：贪心地每步比较左右哪个"更该先取"，但 S 组这类题通常需要额外的验证——2021 回文就是贪心决定大方向后，再模拟验证一遍是否可行。

两端决策的贪心最容易"看起来对"。 basic-series/03 §4 的实测里，"按区间长度排序"那种只错 0.81% 的贪心最危险——正因为它几乎总是对。两端决策同理，必须构造反例试一试。

3.3 形态⑤：带数据结构的贪心（只拿部分分）

2020 T4 贪吃蛇（S⭐⭐）、2023 T4 种树（S⭐⭐）——两道都在 T4 位置。

对 131 分的目标，这两道只需要低档：

题	低档做法
贪吃蛇	小数据直接模拟每一轮"最强吃最弱"的决策
种树	小数据 $O(n^2)$ 暴力枚举

⚠️ 不要在这类题上投入超过 30 分钟

---

4. 考场上十分钟判断一个贪心对不对

考场上没有时间做严格证明，要的是十分钟的可操作流程：

步骤	时长	动作
1	2′	手算最小样例：$n=1,2,3$ 各试一遍，和题面样例对得上吗
2	3′	主动构造反例：故意造"全相等"、"严格递减"、"有负数"、"有零"的输入，心算结果
3		交换论证一句话：如果把最优解里相邻两个决策交换，会不会变差？说不出这句话就是没想清楚
4	2′	数据范围确认：我这个贪心是 $O(n\log n)$，题目给 $n\le10^5$ —— 对得上

四步都过 → 写。任何一步卡住，转写暴力对拍。

4.1 有暴力就对拍，别猜

考场上验证贪心最硬的手段是对拍：写一个 $O(2^n)$ 或 $O(n!)$ 的暴力，用 tools/duipai.sh 跑几百轮。

./duipai.sh ./greedy ./brute "python3 gen.py" 500

造数据必须包含三类（tools/gen-template.py 已内置）：三档规模、前提被破坏（负数/零/相等）、极端形态（全相同/严格单调）。

0/1 背包按性价比贪心的最小反例只要 2 件物品；找零钱贪心的最小反例是币值 $\{1,3,4\}$ 凑 6。反例通常很小 —— 所以对拍用小数据就能抓到，几分钟的事。

---

5. 贪心丢分丢在哪

八道题里最重的数据结构是线段树（2023 种树），其余七道最重只到优先队列 / ST 表。所以贪心丢分主要不是数据结构不会。

5.1 六个真实原因

#	原因	对策
1	推出了正确结论但不敢写（决斗、社团招新）	§4 步骤 4：用数据范围确认。$n\le10^5$ 只允许 $O(n\log n)$，你的简单结论就是答案
2	没看出那个"多余"的条件是解法（社团招新的 $n/2$）	§2 开头：读 T1 时逐条问每个限制是干什么用的
3	分类讨论漏情况（策略游戏的正负）	写之前在草稿纸上把组合编号列全，写完逐条对
4	贪心"看起来对"实际错了（两端决策类）	§4 的四步 + 对拍
5	比较器写错	basic-series/03 §2：写成 <= 是未定义行为，$n\ge17$ 就可能崩
6	边界：$n=1$、全相等、负数、零	交卷前手输三组

5.2 一条来自 basic-03 的实测，考前必须再看一眼

区间调度三种排序策略：按结束时间（正确）全档 0.00% 错误率；按开始时间错 3.50% / 15.70% / 31.87%；按区间长度只错 0.81% / 2.00% / 3.33%——正因为它"几乎总是对"，才最危险。

"几乎总是对"的贪心是 S 组最常见的陷阱。 随机数据对拍两百轮都过，考场上照样挂——因为反例在极端形态里。

---

6. 识别信号：看到什么想到贪心

考场上看到	立刻想到
T1 题面里有一个"不参与题意"的限制条件	那个条件就是解法。抽屉、奇偶、上界
"每轮最大的对最小的做某事"	形态①：统计类，答案可能就是某个计数
两部分共享一个总量，求最优划分	形态②：各算前缀函数 + 枚举分界点
"最少选几个点/几次操作覆盖全部"	形态③：区间点覆盖，按右端点排序
从序列两头往中间取	形态④：两端决策。必须构造反例验一下
贪心每步需要"当前最大/最小"	形态⑤：堆 / 双端队列 / 线段树。若在 T4 位置，只拿低档
数据范围只允许 $O(n)$ 而我想到了 $O(n)$ 结论	§4 步骤 4：数据范围在确认你。动手
贪心想不出来 / 不确定对不对	写暴力对拍（tools/duipai.sh），或转部分分

---

7. 常见错误与考点分析

错误 1：把贪心和图论一样对待。 次数都是 8/30，但贪心 50% 是送分盘、图论 0%。贪心要练到不出错，图论只要能拿部分分（§1.2）。

错误 2：在 T1 的贪心上不敢相信简单结论。 S 一等 131 分的 100 分就在这里。§4 的四步 10 分钟能定。

错误 3：漏掉题面里"多余"的条件。 2025 社团招新的 $n/2$ 就是抽屉；漏了就会去写网络流。

错误 4：分类讨论不列清单直接写。 2022 策略游戏的正负组合，漏一种就是几十分。

错误 5：相信"随机数据对拍两百轮都过"。 反例在极端形态里（§5.2）。造数据必须含三档规模 + 前提被破坏 + 极端形态。

错误 6：在 S⭐⭐ 的贪心（贪吃蛇、种树）上死磕。 它们在 T4 位置，01-contest-strategy.md §5 规则四：上限 30 分钟。

---

8. 小结

1. 贪心与图论各 8/30 并列第一，但角色相反：贪心 50% 是 S 层送分盘、T1 位置出现 3 次；图论 0% 是 S 层、50% 是 S⭐⭐、T3/T4 占 6/8。
2. 贪心是拿分线，图论是拉分线。 S 一等那 100 分的主体在贪心里。
3. 三道 T1 贪心的结构完全一样：题面里有一个"看起来多余"的条件，它把问题塌缩成一句话。那个条件就是解法。
4. S 组贪心五种形态：① 统计即答案 ② 枚举分界点 ③ 区间点覆盖 ④ 两端决策 ⑤ 带数据结构（后者只拿低档）。
5. 考场上十分钟判断贪心对不对：手算小样例 → 主动构造反例 → 交换论证一句话 → 数据范围确认。四步都过才写。
6. 贪心丢分不是数据结构不会（八题最重只到线段树，七题最重到优先队列），而是 §5.1 那六条。
7. "几乎总是对"的贪心最危险（按区间长度排序只错 0.81%）。随机数据对拍不够，必须造极端形态。