GESP 2024年6月 真题 黑白翻转 完整题解(动态规划)
- 2026-11-21 03:10:27
小杨有一棵包含 n 个节点的树,这棵树上的任意一个节点要么是白色,要么是黑色。小杨认为一棵树是美丽树当且仅当在删除所有白色节点之后,剩余节点仍然组成一棵树。
小杨每次操作可以选择一个白色节点将它的颜色变为黑色,他想知道自己最少要执行多少次操作可以使得这棵树变为美丽树。
0 1 0 1 0
1 2
1 3
3 4
3 5
这题光看代码容易绕进去,先找个生活里的比方,比方对了,代码就是照着抄。
今天刷 GESP 2024年6月 的这道动态规划题。先说结论:思路只有一句话,难的是把这句话不折不扣地落成代码。
题目:黑白翻转
场次:2024年6月 七级|难度:七级
知识点:树形动态规划 拓扑排序
链接:https://www.acgo.cn/problemset/info/81645
小杨有一棵包含 n 个节点的树,这棵树上的任意一个节点要么是白色,要么是黑色。小杨认为一棵树是美丽树当且仅当在删除所有白色节点之后,剩余节点仍然组成一棵树。 小杨每次操作可以选择一个白色节点将它的颜色变为黑色,他想知道自己最少要执行多少次操作可以使得这棵树变为美丽树。
一句话概括:用树形动态规划 拓扑排序把题目要求原样翻译成代码,属于考场上必须拿满分的题。
前提一,容器够不够大。题干没给明确范围,这类题的经验是:数据上千就用 long long,多占 4 个字节,换一个不出错。
前提二,两头有没有照顾到。最小规模先想一遍:n 等于 1 时程序会不会崩、答案是不是 0,这两种情况出题人最爱设陷阱。
前提三,交出去的样子对不对。第三件,最后注意输出格式。输出前先念一遍题目对输出的要求,换行、空格、顺序,三样都对齐了再提交。
先说这个比方。DP 像记流水账:每一笔都记下来,算下一笔的时候直接查前面记好的,不用从头重算。账本怎么设计(状态定义)决定了后面好不好算。
要保证”删除所有白色节点之后,剩余节点仍然组成一棵树“,那么就需要任意两黑色节点路径上的所有点都为黑色,所以答案就是所有两两黑色节点路径上不同白色节点的数量。 可以先假定任意一个黑色节点为根,将所有有黑色节点儿子的白色节点染黑,记录染黑的白色节点的个数即可。
比方和代码是一一对应的:比方里先说清「有几样东西」,对应代码里的变量;比方里「一个一个过」,对应那个循环。
建议先自己写二十分钟,卡住了再看。对着抄一遍的效果,比不上自己错一遍。
#include <cstdio>
#include <vector>
using namespace std;
vector<int> g[100005];
int col[100005];
bool need[100005];
int dfs(int u, int fa) { // 返回子树内是否有黑点
bool has = (col[u] == 1);
for (int v : g[u]) if (v != fa) { // 遍历
bool sub = dfs(v, u);
if (sub && col[u] == 0) need[u] = true; // 有黑点子树的白点需变黑
has = has || sub;
}
return has;
}
int main() {
int n; scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d", &col[i]); // 遍历
for (int i = 1; i < n; i++) { int u, v; scanf("%d%d", &u, &v); g[u].push_back(v); g[v].push_back(u); }
int root = 1;
for (int i = 1; i <= n; i++) if (col[i] == 1) { root = i; break; } // 遍历
dfs(root, 0);
int ans = 0; // 初始化
for (int i = 1; i <= n; i++) if (need[i]) ans++; // 遍历
printf("%d\n", ans);
return 0;
}
逐段过一遍会太啰嗦,我只讲决定对错的那两段。
第一段,把数据读进来。
读入这段只要盯一件事:变量类型装不装得下。其他都可以照抄。
第二段,核心处理。
bool sub = dfs(v, u);
if (sub && col[u] == 0) need[u] = true; // 有黑点子树的白点需变黑
has = has || sub;
}
这段是整道题唯一需要想的地方,也是动态规划的落点。看循环时只问三句:从哪开始、到哪结束、每次加几。三句都对,这段就没错。
验证不是随便点几下提交,按下面的清单走一遍。
样例输入
0 1 0 1 0
1 2
1 3
3 4
3 5
样例输出
按这个顺序走一遍,跟上面那个比方对上:
- 把第一组样例抄进去跑,一个字都不差,行尾空格也别多。
- 试最小的输入,只给一个数、只给一行,程序不崩也不越界。
- 看最后一行,结尾有换行,不多输出空行。
| 容易错的地方 | 错误写法 | 正确写法 |
|---|---|---|
| 递归层数爆栈 | 链状数据直接递归到 n 层 | 改显式栈,或把递归改成从底往上推 |
| 累加结果溢出 | int sum = 0; | 累加变量用 long long |
| 输出格式不符 | cout << ans; | cout << ans << "\n"; |
| 多组数据没清空 | 全局数组直接用 | 每组数据前 memset 或重新赋值 |
总结一下,下次遇到同类题你只需要回忆这三点。
- 这题考的:树形动态规划 拓扑排序——把题目条件一句一句翻译成代码,不添不减。
- 要记住的:升序还是降序、按哪个字段排,写反了答案就反了。
- 下一步:拿同场次另一道题练手,换题型不换节奏,手感就稳了。
系列按场次往前推,下一篇还在这个级别,难度会往上走一档。
- 本文属于《GESP 真题题解》系列,第 84 篇,真题按年份持续补齐,每篇都带完整可编译代码,题号可在 ACGO 直接提交验证。
- 还没动笔的话,先自己写一遍再回来看踩坑总结,比直接照抄代码收获大。
- 想跟完整系列的朋友点个关注,更新会第一时间推送。
- 本系列合集目录(按年份/组别排序)
GESP 的坑多半在边界和读题上。这道动态规划题把该注意的点都列在上面的表里了,提交前逐条过一遍。
今天想问你:如果让你给这题改一个数据,让暴力刚好过不了,你会怎么改?
觉得有收获就点个 赞 和 在看,让更多备考的同学刷到;关注本号,每天 8 道真题连更。
想要这题的可运行代码文件?后台回复 “资料” 直接拿。
本篇编号 GESP-069(公众号 MP-069)。完整目录与更多题解见博客专栏(公众号菜单「历史文章」)。