2020-2021:teams:i_dont_know_png:week_summary_18
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:i_dont_know_png:week_summary_18 [2020/09/04 02:42] qxforever |
2020-2021:teams:i_dont_know_png:week_summary_18 [2020/09/04 18:04] (当前版本) nikkukun |
||
|---|---|---|---|
| 行 14: | 行 14: | ||
| ==== 专题 ==== | ==== 专题 ==== | ||
| + | |||
| + | 无 | ||
| ==== 比赛 ==== | ==== 比赛 ==== | ||
| - | **比赛名称** | + | 无 |
| - | + | ||
| - | ^ 题目 ^ A ^ B ^ C ^ D ^ E ^ F ^ | + | |
| - | | 通过 | √ | | | | | | | + | |
| - | | 补题 | | | | | | | | + | |
| ==== 学习总结 ==== | ==== 学习总结 ==== | ||
| + | 无 | ||
| 行 68: | 行 66: | ||
| ==== nikkukun ==== | ==== nikkukun ==== | ||
| - | [[题目链接 | 题目名称]] | + | 无。本周搬家中。 |
| - | + | ||
| - | * **题意**： | + | |
| - | * **题解**： | + | |
| - | * **备注**： | + | |
| ==== qxforever ==== | ==== qxforever ==== | ||
| 行 80: | 行 74: | ||
| * **题意**：核心题意是，给一个 $n$ 个点的树，每次选两个叶子，将两个叶子之间的最短路染为黑色，花费为路径长度。每个叶子只能选一次。问将整棵树染为黑色的最小花费。 | * **题意**：核心题意是，给一个 $n$ 个点的树，每次选两个叶子，将两个叶子之间的最短路染为黑色，花费为路径长度。每个叶子只能选一次。问将整棵树染为黑色的最小花费。 | ||
| - | * **题解**：建议先想一想。显然树有偶数个叶子。任选一个不是叶子的节点为根 ，设 $S$ 为子树内有偶数个叶子的节点的集合，那么答案为 $\vert S \vert + n -2$ 。对于节点 $p$ 和其父节点 $f$ ，若 $p$ 的子树内有奇数个叶子，则无论怎么选，$pf$ 这条边总会被覆盖；若有偶数个叶子，则需要至少 $2$ 个叶子与子树外的叶子配对，即 $pf$ 被覆盖两次。 | + | * **题解**：显然树有偶数个叶子。任选一个不是叶子的节点为根 ，设 $S$ 为子树内有偶数个叶子的节点的集合，那么答案为 $\vert S \vert + n -2$ 。对于节点 $p$ 和其父节点 $f$ ，若 $p$ 的子树内有奇数个叶子，则无论怎么选，$pf$ 这条边总会被覆盖；若有偶数个叶子，则需要至少 $2$ 个叶子与子树外的叶子配对，即 $pf$ 被覆盖两次。 |
| - | * **备注**：可能 (?) 是经典题，然而看题解之前想了好久也没想到，非常巧妙的将所求的东西转化为了边的覆盖次数。 | + | * **备注**：可能 (?) 是经典题，然而看题解之前想了好久也没想到，思维僵化。 |
| ==== Potassium ==== | ==== Potassium ==== | ||
2020-2021/teams/i_dont_know_png/week_summary_18.1599158531.txt.gz · 最后更改: 2020/09/04 02:42 由 qxforever
