====== 2020.08.29-2020.09.04 周报 ======


===== 团队训练 =====

无

===== 团队会议 =====

无


===== 个人训练 - nikkukun =====

==== 专题 ====

无

==== 比赛 ====

无

==== 学习总结 ====

无



===== 个人训练 - qxforever =====

==== 专题 ====

==== 比赛 ====

**比赛名称**

无

==== 学习总结 ====

无



===== 个人训练 - Potassium =====

==== 专题 ====

无

==== 比赛 ====

无

==== 学习总结 ====

无






===== 本周推荐 =====

==== nikkukun ====

无。本周搬家中。

==== qxforever ====

[[https://codeforces.com/contest/1403/problem/B | CEOI2020 Day2 T2]]

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

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

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

==== Potassium ====

[[https://community.topcoder.com/stat?c=problem_statement&pm=16282 | TopCoder 16282 RoomPairs]]

  * **题意**：给一个 $R\times C$ 的空间，要求用墙分隔出房间，一个房间定义为可以互相到达的整块区域，两个房间相邻当且仅当隔一个墙。求构造使恰有 $N$ 对相邻房间。
 
  * **题解**：状态 $(R,C)$ 可以从 $(R,C-1)$ 或 $(R-1,C)$ 转移而来，后者可以通过添加一列/行全部由墙隔开的房间或延长原有房间进行转移。

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