2020-2021:teams:i_dont_know_png:neerc2016
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:i_dont_know_png:neerc2016 [2020/05/24 01:10] potassium |
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|题解]] | ||
| 行 68: | 行 111: | ||
| 先假设初始时没有车，把每个时刻的总借车人数（包括等待中的）减去总归还车辆数的差按时间在坐标轴 $xOy$ 上画出，则所有人的等待时间为 $y \geq 0$ 部分的面积。而改变初始车辆数，等于一同变化整体高度，因此维护好每一个矩形块的高度和面积即可 $O(\log n)$ 计算答案。 | 先假设初始时没有车，把每个时刻的总借车人数（包括等待中的）减去总归还车辆数的差按时间在坐标轴 $xOy$ 上画出，则所有人的等待时间为 $y \geq 0$ 部分的面积。而改变初始车辆数，等于一同变化整体高度，因此维护好每一个矩形块的高度和面积即可 $O(\log n)$ 计算答案。 | ||
| + | ===== F - Foreign Postcards ===== | ||
| + | solved by qxforever | ||
| + | |||
| + | ==== 题目描述 ==== | ||
| + | |||
| + | 一个人手里有 $n$ 张牌，这些牌有的正面朝上有的反面朝上。 设当前手里有 $k$ 张牌，随机选择一个 $x\in[1,k]$ 。如果当前第一张牌是反的，就将这 $x$ 张牌全部翻过来。之后将这 $x$ 张牌移走。直到手里没有牌。问最后反面朝上的牌的数量的期望。$n\le 10^6$ | ||
| + | |||
| + | ==== 解题思路 ==== | ||
| + | |||
| + | 设 $f_i$ 为最上面的牌是第 $i$ 张牌的期望，$g_{ij}$ 表示 $[i,j]$ 中和 $i$ 状态相反的数量。那么有 $f_i=\frac{1}{n-i+1}(\sum_{j>i}f_j+\sum_{j>i}g_{ij})$ 。 从后往前 DP ，维护 $f$ 的后缀和，$\sum_{j>i}g_{ij}$ 可以用两次前缀和预处理求出。 | ||
| 行 93: | 行 146: | ||
| 最后，如果还有无法判断胜负的节点，由于 A 会倾向平局，但 B 有选择负或平的机会，必然会选择负，那么 A 胜， B 负。 | 最后，如果还有无法判断胜负的节点，由于 A 会倾向平局，但 B 有选择负或平的机会，必然会选择负，那么 A 胜， B 负。 | ||
| + | ===== H - Hard Refactoring ===== | ||
| + | |||
| + | solved by qxforever | ||
| + | |||
| + | ==== 题目描述 ==== | ||
| + | |||
| + | 给一堆关于 $x$ 的逻辑表达式。求表达式真的解集。 | ||
| + | |||
| + | ==== 解题思路 ==== | ||
| + | 模拟即可。 | ||
2020-2021/teams/i_dont_know_png/neerc2016.1590253833.txt.gz · 最后更改: 2020/05/24 01:10 由 potassium
