第 9 章 部分分策略
本章定位：NOIP 的 T3、T4 是给前几名准备的，其他人比的是谁的部分分拿得多。CSP-S 2026 上，T3、T4 各有一档只要 BFS 和子集枚举就能拿的分（24 分和 15 分，已在官方数据上验证），这次都是 0。本章讲怎么把这种分稳稳拿到手，全部是【必会】。
9.1 部分分从哪来 【必会】
NOIP 每道题有 10～25 个测试点，每个点单独给分。题面最后的数据范围表把测试点分成几档，每一档要么规模小，要么带一条“特殊性质”。下面是本系统 E03（哨塔）的表，结构和真题一样：
| 测试点 | n ≤ | 特殊性质 | 这一档在考什么 |
|---|---|---|---|
| 1 ～ 6 | 18 | 无 | 枚举所有选法（2^18 种） |
| 7 ～ 10 | 2×10^5 | 链 | 树退化成序列，线性 DP |
| 11 ～ 12 | 2×10^5 | 菊花 | 只能选一个点，取最大值 |
| 13 ～ 14 | 1000 | 无 | 正解，但常数大也能过 |
| 15 ～ 20 | 2×10^5 | 无 | 正解 |
前三档合计 60 分，三段代码加起来不到 60 行，不需要想出正解。出题人把这 60 分明码标价放在表里，剩下的事情是把它们一档一档写出来。
9.2 读表三步 【必会】
读完题面先别想正解，先对着表做三件事，结果写在草稿纸上：
- 按规模定算法。 对照第 0 章 0.7 的复杂度表：n ≤ 10 是全排列，n ≤ 20 是子集枚举，n ≤ 500 是三重循环，n ≤ 5000 是两重循环。
- 把每条特殊性质翻译成“问题变成了什么”。 见 9.3。
- 给每一档标上“分值 / 要花的时间”。 先写最划算的。
草稿纸上应该出现这样的东西：
T3：1-6 子集枚举 30分 20分钟 ← 必写
7-10 链=序列DP 20分 15分钟 ← 必写
11-12 菊花 取max 10分 5分钟 ← 必写
其余 40分 树形DP 没把握 ← 最后再说
9.3 常见特殊性质怎么用 【必会】
| 表里写的 | 问题变成了什么 | 做法 |
|---|---|---|
| n ≤ 10 | 可以试遍所有顺序 | next_permutation（第 2 章） |
| n ≤ 20 | 可以试遍所有选法 | 二进制枚举子集（第 2 章） |
| 树是一条链 | 就是一个序列 | 树形 DP 变线性 DP；路径变区间；树上差分变一维差分；LCA 变成比较下标 |
| 树是菊花（所有点连着同一个中心） | 只有“中心”和“叶子”两种点 | 多数情况能直接推出公式，或者排序后贪心 |
| 所有 a_i 相等，或只有 0 和 1 | 只和个数有关 | 数一数个数，套组合数或公式 |
| k = 1、m = 0、q = 1 | 退化成最简单的情形 | 往往一两行；也是检验你有没有读懂题的机会 |
| 保证有解 / 保证连通 / 保证无环 | 不用处理特殊情况 | 省掉判断。反过来，没有这句话时一定要处理 |
| 数据随机生成 | 树的深度很小，极端情况不会出现 | 朴素做法往往不慢 |
| 输入有序 / 单调 | 不用排序，可以二分或双指针 | 第 1 章 |
链的两种说法要分清：“第 i 条边连接 i 和 i+1”时，点的编号就是它在序列里的位置，直接当数组用；只说“每个点的度数不超过 2”时，要先从一个端点（度数为 1 的点）出发走一遍，得到序列。
9.4 一份程序拿多档分 【必会】
每一档写成一个独立的函数，main 里按性质分流。性质要从输入里判断出来，不要假设。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 200005;
int n, deg[N];
bool is_chain() { // 链：第 i 条边连接 i 和 i+1。读边时顺手记下来更简单，这里用度数判断
for (int i = 1; i <= n; i++)
if (deg[i] > 2) return false;
return true;
}
bool is_star() { // 菊花：有一个点连着其他所有点
for (int i = 1; i <= n; i++)
if (deg[i] == n - 1) return true;
return false;
}
ll solve_brute() { return 0; } // n 小：枚举
ll solve_chain() { return 0; } // 链：线性 DP
ll solve_star() { return 0; } // 菊花：公式
int main() {
freopen("tower.in", "r", stdin);
freopen("tower.out", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for (int i = 1; i < n; i++) {
int u, v;
cin >> u >> v;
deg[u]++, deg[v]++;
}
ll ans;
if (n <= 18) ans = solve_brute();
else if (is_chain()) ans = solve_chain();
else if (is_star()) ans = solve_star();
else ans = 0; // 不会的档：输出一个格式合法的答案，不要让程序崩溃或超时
cout << ans << '\n';
return 0;
}
易错点
- 分流的顺序：先判规模小的（暴力最可靠），再判特殊性质。
- 每个函数用自己的变量，不要互相借用全局状态；多组数据时每个函数里用到的数组都要清空。
- 不会做的那一档也要输出一个格式正确的结果并正常结束，不要留下死循环或越界。
- 近两年的题常在输入第一行给出“测试点编号”。可以用它辅助判断，但直接检查性质更可靠。
练一练：本系统 E03（目标 60 分）、E06（60 分）、E07（70 分）、E10（70 分）、E15（60 分）。这几题的 solutions/<题>/partial.cpp 就是按本节的写法写的，做完再对照。
9.5 先写暴力，再想正解 【必会】
顺序很重要：
- 读懂题，先花 15～20 分钟把最小规模的暴力写出来，过样例，手造两组小数据。
- 把这份暴力另存一份（比如
brute.cpp）。从这一刻起这道题已经有分了。 - 然后才去想特殊性质和正解。想出来了，暴力正好拿来对拍；想不出来，分已经在手里。
反过来的顺序——先想正解，想了一个小时没想出来，再匆忙写暴力——是 0 分的主要来源。
暴力的写法见第 2 章 2.8，核心是五个字：最笨但一定对。
9.6 实在没有思路的时候 【常考】
- 打表找规律。 用暴力把 n = 1, 2, 3, …, 10 的答案全部打印出来，看有没有规律（等差、乘 2、组合数、斐波那契）。数学题和计数题经常能这样看出公式。NOIP2017 的“小凯的疑惑”答案就是 a·b − a − b，考场上很多人是打表看出来的。
- 写一个看起来合理的贪心。 排个序、每次取最大的。不保证对，但常能过掉一部分点。前提是暴力已经写好并保存。
- 不要指望“全部输出 0”或“全部输出 -1”。 现在的测试点大多一个文件里有多组数据，全猜对才给分，基本拿不到。别在这上面花时间。
9.7 四个半小时怎么分 【必会】
| 时间 | 做什么 | 目标 |
|---|---|---|
| 0:00 ～ 0:20 | 四道题全部读完，对每题做 9.2 的“读表三步” | 草稿纸上有每题的拿分计划 |
| 0:20 ～ 1:10 | T1：写、过全部样例、对拍 | 100 分，并且确信是 100 分 |
| 1:10 ～ 2:30 | T2：先暴力（20 分钟），再特殊性质，再正解 | 至少 40 分，争取 100 分 |
| 2:30 ～ 3:10 | T3：暴力 + 能写的特殊性质 | 20～40 分 |
| 3:10 ～ 3:50 | T4：暴力 + 能写的特殊性质 | 15～30 分 |
| 3:50 ～ 4:15 | 回到最有希望的那道题继续往上够 | 多拿一档 |
| 4:15 ～ 4:30 | 不写新代码，逐题过第 0 章的检查清单 | 不丢已经到手的分 |
两条纪律：
- 一道题连续 40 分钟没有新进展，就换题。 换之前把已经能得分的版本保存好。
- T1 没有确认满分之前，不碰后面的题。 T1 的 100 分比后面任何一档部分分都大。
本章必会清单
- 拿到任何一道题，5 分钟内说出数据范围表每一档打算怎么做
- 能把“链”“菊花”“n ≤ 20”“全相等”翻译成具体做法
- 能写出 9.4 那样按性质分流的程序
- 做题顺序固定为：暴力 → 保存 → 特殊性质 → 正解 → 对拍
- 背下 9.7 的时间表，模拟考时照着执行