2020.08.29-2020.09.04 周报

无

无

无

无

无

比赛名称

无

无

无

无

无

无。本周搬家中。

CEOI2020 Day2 T2

• 题意：核心题意是，给一个 $n$ 个点的树，每次选两个叶子，将两个叶子之间的最短路染为黑色，花费为路径长度。每个叶子只能选一次。问将整棵树染为黑色的最小花费。

• 题解：显然树有偶数个叶子。任选一个不是叶子的节点为根 ，设 $S$ 为子树内有偶数个叶子的节点的集合，那么答案为 $\vert S \vert + n -2$ 。对于节点 $p$ 和其父节点 $f$ ，若 $p$ 的子树内有奇数个叶子，则无论怎么选，$pf$ 这条边总会被覆盖；若有偶数个叶子，则需要至少 $2$ 个叶子与子树外的叶子配对，即 $pf$ 被覆盖两次。

• 备注：可能 (?) 是经典题，然而看题解之前想了好久也没想到，思维僵化。

TopCoder 16282 RoomPairs

• 题意：给一个 $R\times C$ 的空间，要求用墙分隔出房间，一个房间定义为可以互相到达的整块区域，两个房间相邻当且仅当隔一个墙。求构造使恰有 $N$ 对相邻房间。

• 题解：状态 $(R,C)$ 可以从 $(R,C-1)$ 或 $(R-1,C)$ 转移而来，后者可以通过添加一列/行全部由墙隔开的房间或延长原有房间进行转移。

• 备注：刚开始只想到添加一个长条的空房间，没有想到添加一行全部由墙隔开的房间，卡了很久。