2020-2021:teams:i_dont_know_png:week_summary_18
| 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:i_dont_know_png:week_summary_18 [2020/09/04 00:17] potassium 创建 |
2020-2021:teams:i_dont_know_png:week_summary_18 [2020/09/04 18:04] (当前版本) nikkukun |
||
|---|---|---|---|
| 行 4: | 行 4: | ||
| ===== 团队训练 ===== | ===== 团队训练 ===== | ||
| - | ^ 比赛时间 ^ 比赛名称 ^ | + | 无 |
| - | | 2020.xx.xx | [[比赛链接 | 比赛名称]] | | + | |
| ===== 团队会议 ===== | ===== 团队会议 ===== | ||
| + | 无 | ||
| 行 16: | 行 14: | ||
| ==== 专题 ==== | ==== 专题 ==== | ||
| + | |||
| + | 无 | ||
| ==== 比赛 ==== | ==== 比赛 ==== | ||
| - | **比赛名称** | + | 无 |
| - | + | ||
| - | ^ 题目 ^ A ^ B ^ C ^ D ^ E ^ F ^ | + | |
| - | | 通过 | √ | | | | | | | + | |
| - | | 补题 | | | | | | | | + | |
| ==== 学习总结 ==== | ==== 学习总结 ==== | ||
| + | 无 | ||
| 行 39: | 行 35: | ||
| **比赛名称** | **比赛名称** | ||
| - | ^ 题目 ^ A ^ B ^ C ^ D ^ E ^ F ^ | + | 无 |
| - | | 通过 | √ | | | | | | | + | |
| - | | 补题 | | | | | | | | + | |
| ==== 学习总结 ==== | ==== 学习总结 ==== | ||
| + | 无 | ||
| 行 52: | 行 46: | ||
| ==== 专题 ==== | ==== 专题 ==== | ||
| + | |||
| + | 无 | ||
| ==== 比赛 ==== | ==== 比赛 ==== | ||
| - | **比赛名称** | + | 无 |
| - | + | ||
| - | ^ 题目 ^ A ^ B ^ C ^ D ^ E ^ F ^ | + | |
| - | | 通过 | √ | | | | | | | + | |
| - | | 补题 | | | | | | | | + | |
| ==== 学习总结 ==== | ==== 学习总结 ==== | ||
| + | 无 | ||
| 行 74: | 行 66: | ||
| ==== nikkukun ==== | ==== nikkukun ==== | ||
| - | [[题目链接 | 题目名称]] | + | 无。本周搬家中。 |
| - | + | ||
| - | * **题意**： | + | |
| - | * **题解**： | + | |
| - | * **备注**： | + | |
| ==== qxforever ==== | ==== 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 ==== | ==== 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)$ 转移而来，后者可以通过添加一列/行全部由墙隔开的房间或延长原有房间进行转移。 | ||
| - | * **题意**： | + | * **备注**：刚开始只想到添加一个长条的空房间，没有想到添加一行全部由墙隔开的房间，卡了很久。 |
| - | * **题解**： | + | |
| - | * **备注**： | + | |
2020-2021/teams/i_dont_know_png/week_summary_18.1599149837.txt.gz · 最后更改: 2020/09/04 00:17 由 potassium
