2020-2021:teams:i_dont_know_png:neerc2016
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:i_dont_know_png:neerc2016 [2020/05/24 01:27] qxforever |
2020-2021:teams:i_dont_know_png:neerc2016 [2020/05/24 18:52] (当前版本) potassium D |
||
|---|---|---|---|
| 行 3: | 行 3: | ||
| [[https://codeforces.com/gym/281394|比赛链接]] | [[https://codeforces.com/gym/281394|比赛链接]] | ||
| + | nikkukun qxforever 二人场 | ||
| ===== A - Abbreviation ===== | ===== A - Abbreviation ===== | ||
| 行 25: | 行 26: | ||
| ===== B - Binary Code ===== | ===== B - Binary Code ===== | ||
| - | idea from potassium, implemented by nikkukun | + | idea from potassium, upsolved by nikkukun |
| ==== 题目描述 ==== | ==== 题目描述 ==== | ||
| 行 48: | 行 49: | ||
| **限制 3 的建图**：可以类似情况 2 额外设置 $O(n)$ 个辅助变量，使得一个树的节点中最多选中一个节点。也可以通过观察发现，如果某个节点超过该节点的串长度 $+ 1$，则怎么赋值都会产生无解，这时暴力两两加限制的均摊复杂度是 $O(1)$ 的。 | **限制 3 的建图**：可以类似情况 2 额外设置 $O(n)$ 个辅助变量，使得一个树的节点中最多选中一个节点。也可以通过观察发现，如果某个节点超过该节点的串长度 $+ 1$，则怎么赋值都会产生无解，这时暴力两两加限制的均摊复杂度是 $O(1)$ 的。 | ||
| + | |||
| + | |||
| + | |||
| + | ===== C - Cactus Construction ===== | ||
| + | |||
| + | upsolved by nikkukun | ||
| + | |||
| + | ==== 题目描述 ==== | ||
| + | |||
| + | 有 $n \leq 5 \times 10^4$ 个点，一开始所有点不连通，每个点都是一个子图，颜色都是 $1$。有三种操作： | ||
| + | |||
| + | - ''j u v''：把 $u$ 和 $v$ 所在的子图合并（但不加边）； | ||
| + | - ''c u c1 c2''：把 $u$ 所在的子图中颜色为 $c_1$ 和 $c_2$ 的点之间都连一条边。该操作不产生自环，但可能产生重边； | ||
| + | - ''r u c1 c2''：把 $u$ 所在的子图中颜色为 $c_1$ 的点都改为 $c_2$。 | ||
| + | |||
| + | 给定一个仙人掌，用不超过 $10^6$ 次操作构造出来。 | ||
| + | |||
| + | |||
| + | ==== 解题思路 ==== | ||
| + | |||
| + | 像 DFS 树一样遍历每个点双连通分量，并在递归过程中将所有子仙人掌合并到当前所在的连通分量上。 | ||
| + | |||
| + | 我们钦定子仙人掌需要满足只有根节点颜色为 $2$，其他节点颜色为 $1$。假设现在要把 $u$ 的所有子仙人掌都合并到 $u$ 所在的连通分量上，并钦定 $u$ 的颜色为 $4$。按 $u$ 所在的连通分量讨论： | ||
| + | |||
| + | * 桥：子仙人掌加入连通分量，连接 $(2, 4)$ 后将子仙人掌的根节点颜色从 $2$ 改为 $1$ 即可。 | ||
| + | * 环：维护环上的颜色为 $4, 1, 1, \ldots, 3$，每次加入一个子仙人掌后，连接 $(3, 2)$ 并维护链为 $4, 1, 1, \ldots, 1, 3$，直到所有环上的点都添加完毕。最后连接 $(3, 4)$ 并修改 $3$ 为 $1$，让环闭合。 | ||
| + | |||
| + | 递归结束后将根节点的 $4$ 改回 $2$，即可维护性质。 | ||
| + | |||
| + | |||
| + | |||
| + | ===== D - Delight for a Cat ===== | ||
| + | |||
| + | upsolved by potassium | ||
| + | |||
| + | ==== 题目描述 ==== | ||
| + | |||
| + | 有一个人，在某一时刻可以睡觉也可以吃饭，要求连续 $k$ 时刻至少有 $m_s$ 时间在睡觉，至少有 $m_e$ 时刻在吃饭。给定特定时刻睡觉 / 吃饭的快乐值，求最大快乐值以及方案。 | ||
| + | |||
| + | ==== 解题思路 ==== | ||
| + | |||
| + | [[.:potassium:linear_programming#%E7%BB%83%E4%B9%A0%E9%A2%98|题解]] | ||
2020-2021/teams/i_dont_know_png/neerc2016.1590254866.txt.gz · 最后更改: 2020/05/24 01:27 由 qxforever
