Warning: session_start(): open(/tmp/sess_c5e470db0d9e897ce621f8b5ccdd8831, O_RDWR) failed: No space left on device (28) in /data/wiki/inc/init.php on line 239
Warning: session_start(): Failed to read session data: files (path: ) in /data/wiki/inc/init.php on line 239
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/auth.php on line 430
Writing /data/wiki/data/cache/d/de2edb2fcb553ea79b79c722a4e13dbc.captchaip failed
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
====== 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)$ 转移而来，后者可以通过添加一列/行全部由墙隔开的房间或延长原有房间进行转移。
* **备注**：刚开始只想到添加一个长条的空房间，没有想到添加一行全部由墙隔开的房间，卡了很久。