今天看 CSP-S 2023 的这道题考点是二分答案。题目来源ACGO A7095 洛谷 P9755难度定位提高/省选- 通过率50.00%一、题目信息题目名称种树所属赛事2023 年 CSP-S 组复赛官方难度提高/省选-涉及知识点二分答案题目链接https://www.acgo.cn/problemset/info/7095洛谷编号P9755同一道题两个平台均可提交代码通用易错点很多人栽在这左右边界的更新要成对写边界写错容易死循环判断函数必须是单调的否则二分不成立高难度题的暴力分很关键先写一版能过的部分分再想正解题意简述题意其实很直白你是一个森林养护员有一天你接到了一个任务在一片森林内的地块上种树并养护至树木长到指定的高度。森林的地图有 n 片地块其中 1 号地块连接森林的入口。共有 n-1 条道路连接这些地块使得每片地块都能通过道路互相到达。最开始每片地块上都没有树木。你的目标是在每片地块上均种植一棵树木并使得 i 号地块上的树的高度生长到不低于 a_i 米。你每天可以选择一个未种树且与某个已种树的地块直接邻接即通过单条道路相连的地块种一棵高度为 0 米的树。如果所有地块均已种过树则你当天不进行任何操作。特别地第 1 天你只能在 1 号空地种树。对每个地块而言从该地块被种下树的当天开始该地块上的树每天都会生长一定的高度。由于气候和土壤条件不同在第 x 天i 号地块上的树会长高 max(b_i x × c_i, 1) 米。注意这里的 x 是从整个任务的第一天而非种下这棵树的第一天开始计算。你想知道最少需要多少天能够完成你的任务前置知识这题要用到的工具不多但有一个容易忘先过一遍。在有序区间里折半二分本身简单难在判断「答案是否单调」。只要满足「x 可行则 x1 也可行」就能二分答案。二、思路分析这题官方难度提高/省选-中场先拿暴力分比较稳妥。思路的入口在哪里题意解析我们首先来考虑链的部分分。不难发现这部分的关键是实现一个形如check(x,l,r)的函数表示 x 结点在 [l,r] 这段时间的生长高度能否达成目标。同时这也是正解的一个关键函数。不妨列出 x 结点高度的表达式先考虑c_x0的情况则可以化简接着我们思考特殊性质。不难发现此时每个结点生长到目标高度所需时间与种下的时间无关即有{t_x}a_x/b_x向上取整。将结点{t_x}按从大到小排序。考虑这样一个贪心我们顺次考虑所有结点若该结点已被种树就跳过否则将根到该结点这条链按顺序把未种树的结点种树。显然这样做会得到一个种树顺序的序列显然由于{t_x} 更小的结点不是时间的瓶颈我们这样做是最优的。实际实现过程中我们标记一下每个结点是否种过树。当考虑当前结点 x 时暴力跳到最后一个未被标记的祖先结点然后倒序再给每个结点赋上开始种树的时间s_x。取 s_xt_x-1 的最大值即可。想明白了前两个部分正解就是容易的。考虑一般情况与特殊性质的区别不难发现我们无法得到上述的 t_x了究其根本是因为树种下的时间会影响种树需要的时间。我们考虑二分答案并修改t_x 的定义为要使该结点合法的最晚种树时间。显然在该前提下t_x 可以用二分答案加上链部分所实现的函数求出。而这时我们按照t_x 从小到大考虑不难发现问题就转化为了特殊性 时的问题套用以上做法即可解决。时间复杂度O(nlognlogv)。用桶排并上二次函数相关知识应该能将logn 去掉不过没必要。三、完整代码#include cstdio #include algorithm #include vector using namespace std; // CSP-S 2023 种树 // // 题意n 个地块构成一棵以 1 为根的树。每天可以选一个「未种树、且与已种树的 // 地块相邻」的地块种一棵高度为 0 的树。第 x 天i 号地块的树长高 // max(b_i x*c_i, 1) 米x 从整个任务第 1 天算起不是种下的那天。 // 要求最终每片地块的树高 ≥ a_i求最少天数。 // // 思路二分答案 D判定 D 天是否可行。 // // 1. 对每个地块 i求出「最晚可以第几天种下」lim[i] // 若第 t 天种下则到第 D 天累计长高 G(i,t) Σ_{xt..D} max(b_i x*c_i, 1)。 // G(i,t) 随 t 增大单调不增因此 lim[i] 就是满足 G(i,t) ≥ a_i 的最大 t。 // 求 lim[i] 用二分对 t 二分G 用等差数列公式 O(1) 计算。 // 因为 max(...,1) 的存在把 [t,D] 分成两段b_i x*c_i 1 的部分按 1 累加 // 其余按 b_i x*c_i 累加用等差数列求和即可。 // 2. 树上「父必须先于子」把 lim 自底向上收紧 lim[fa] min(lim[fa], lim[child] - 1)。 // 3. 若所有 lim[i] ≥ 1把 n 个地块按 lim 升序排列第 k 个必须安排在第 ≤ lim 的天 // 只需检查第 k 个的 lim ≥ kk 从 1 开始。全部满足则 D 可行。 // // 复杂度二分 O(log(1e9)) × 判定 O(n log D)n ≤ 1e5 时总计约 O(n log²)可过。 const int MAXN 100005; const long long INF (long long)4e18; int n; long long a[MAXN], b[MAXN], c[MAXN]; int head_[MAXN], nxt_[2 * MAXN], to_[2 * MAXN], ecnt; int par[MAXN], ord_[MAXN], ordn; inline void addEdge(int u, int v) { to_[ecnt] v; nxt_[ecnt] head_[u]; head_[u] ecnt; } void buildTree() { static int stk[MAXN], state[MAXN]; for (int i 1; i n; i) { par[i] 0; state[i] 0; } int sp 0; par[1] 0; stk[sp] 1; state[sp] 0; ordn 0; while (sp 0) { int u stk[sp]; if (state[sp] 0) { state[sp] 1; ord_[ordn] u; for (int e head_[u]; e; e nxt_[e]) { int v to_[e]; if (v par[u]) continue; par[v] u; stk[sp] v; state[sp] 0; } } else --sp; } } // 计算若在第 t 天种下、到第 D 天累计长高等差数列 O(1) 求和 // 生长量 g(x) max(b_i x*c_i, 1)随 x 单调c_i0 递增、c_i0 递减。 // 把 [t,D] 按 g(x) ≥ 1 与否分成两段一段用等差数列精确求和另一段按 1 累加。 static long long grow(int i, long long t, long long D) { if (t D) return 0; long long bi b[i], ci c[i]; long long res 0; if (ci 0) { long long g bi 1 ? 1 : bi; return (D - t 1) * g; } if (ci 0) { // b x*c 1 x ceil((1-b)/c) long long num 1 - bi; long long x0 (num 0) ? 0 : (num ci - 1) / ci; long long lo max(t, x0), hi D; // 真实值段 if (lo hi) { long long cnt hi - lo 1; res bi * cnt ci * ((lo hi) * cnt / 2); } long long lo2 t, hi2 min(D, x0 - 1); // 取 1 的段 if (lo2 hi2) res (hi2 - lo2 1); } else { // b x*c 1 x (b-1)/(-c) long long den -ci; long long x0 (bi - 1) / den; long long lo t, hi min(D, x0); // 真实值段 if (lo hi) { long long cnt hi - lo 1; res bi * cnt ci * ((lo hi) * cnt / 2); } long long lo2 max(t, x0 1), hi2 D; // 取 1 的段 if (lo2 hi2) res (hi2 - lo2 1); } return res; } // 判定 D 是否可行D 至少为 n否则种不完 static bool feasible(long long D) { if (D n) return false; static long long lim[MAXN]; for (int i 1; i n; i) { // 二分数出最大的 t ∈ [1,D] 使 grow(i,t,D) a[i]grow 随 t 减而增 long long lo 1, hi D, best 0; while (lo hi) { long long mid lo (hi - lo) / 2; if (grow(i, mid, D) a[i]) { best mid; lo mid 1; } else hi mid - 1; } lim[i] best; if (best 0) return false; } // 自底向上收紧父约束 for (int k ordn - 1; k 0; --k) { int u ord_[k]; if (par[u] lim[par[u]] lim[u] - 1) lim[par[u]] lim[u] - 1; } for (int i 1; i n; i) if (lim[i] 1) return false; // 贪心按 lim 升序第 k 个1-based需 lim k static int idx[MAXN]; for (int i 1; i n; i) idx[i] i; sort(idx 1, idx n 1, [](int x, int y) { return lim[x] lim[y]; }); for (int k 1; k n; k) if (lim[idx[k]] k) return false; return true; } int main() { scanf(%d, n); for (int i 1; i n; i) scanf(%lld %lld %lld, a[i], b[i], c[i]); ecnt 0; for (int i 1; i n; i) head_[i] 0; for (int i 1; i n; i) { int u, v; scanf(%d %d, u, v); addEdge(u, v); addEdge(v, u); } buildTree(); long long lo n, hi (long long)2e9, ans hi; // 上界保证可行取一个足够大的天数题目保证 1e9 天内可行用 1e9 hi (long long)1e9; lo n; while (lo hi) { long long mid lo (hi - lo) / 2; if (feasible(mid)) { ans mid; hi mid - 1; } else lo mid 1; } printf(%lld\n, ans); return 0; }四、代码分段拆解完整代码在上面下面按功能分块解释。头文件与全局变量先把用到的头文件和全局变量放上来。全局变量在竞赛里很常用好处是函数之间共享方便代价是要小心初始化和被意外改写。#include cstdio #include algorithm #include vectorusing namespace std; const int MAXN 100005; const long long INF (long long)4e18; int n; long long a[MAXN], b[MAXN], c[MAXN]; int head_[MAXN], nxt_[2 * MAXN], to_[2 * MAXN], ecnt; int par[MAXN], ord_[MAXN], ordn; int sp 0; int u stk[sp]; int v to_[e]; long long bi b[i], ci c[i]; long long res 0; long long g bi 1 ? 1 : bi; long主体逻辑主体部分按顺序完成读入、计算、输出。main函数尽量保持线性把复杂的逻辑拆成独立函数出问题时更容易定位。五、实例模拟光看代码容易虚用样例实测一遍最踏实。样例 1输入4 12 1 1 2 4 -1 10 3 0 7 10 -2 1 2 1 3 3 4输出5以第一组样例为例输入是4、12 1 1、2 4 -1、10 3 0、7 10 -2、1 2、1 3、3 4正确输出是5。建议把这两行数据抄在纸上用上面的代码手动走一遍重点看循环变量怎么变化、答案在哪一步被更新。能自己推出来的东西比看懂代码印象深得多。六、踩坑总结最后总结几个要点。左右边界的更新要成对写边界写错容易死循环判断函数必须是单调的否则二分不成立高难度题的暴力分很关键先写一版能过的部分分再想正解另外提醒一句这题在 CSP-S 2023 里是提高/省选-难度考场上如果没有把握拿满分先把暴力写法交上去拿到部分分再回头优化。CSP 是打分制空着不写才是最亏的。七、知识点拓展这题的核心是二分。二分答案的适用信号是「答案有单调性」。典型问法是「最小/最大是多少」并且验证一个候选答案比直接求解容易。建议的练习路径先把本题独立写一遍不看代码遇到卡壳再看提示换个平台提交ACGO 和洛谷都试试确保代码在两个平台都能过找两到三道同类型的题练手巩固这类问题的识别能力八、适用人群这道题的适用面目标是 CSP-S 高分或省选的同学想通过真题理解高难度题如何从暴力优化到正解的同学想弄明白二分类问题标准解法的同学代码有任何问题欢迎指正我会及时更新。关于这个系列这是「CSP 真题逐题精讲」的第 40 篇。我会按年份从 2019 一路刷到 2025CSP-J 和 CSP-S 全覆盖。每篇都给双平台题号ACGO 洛谷 逐行代码拆解 真实样例模拟。跟着刷完这一套CSP 第一轮的选择题和基础题基本就稳了。下一篇CSP-S 2023 消消乐提高/省选- 关注我不错过后续更新。评论区告诉我你现在刷到哪一年了我看看能不能按大家的进度调整更新节奏。
