CVBB ACM Team

用户工具

站点工具

您在这里: front_page » 2020-2021 » teams » i_dont_know_png » neerc2016
2020-2021:teams:i_dont_know_png:neerc2016

差别

这里会显示出您选择的修订版和当前版本之间的差别。

到此差别页面的链接

两侧同时换到之前的修订记录 前一修订版
后一修订版 		前一修订版
2020-2021:teams:i_dont_know_png:neerc2016 [2020/05/23 22:38]
nikkukun add some contents 		2020-2021:teams:i_dont_know_png:neerc2016 [2020/05/24 18:52] (当前版本)
potassium D
行 2: 行 2:
  
 [[https://​codeforces.com/​gym/​281394|比赛链接]] [[https://​codeforces.com/​gym/​281394|比赛链接]]
 +
 +nikkukun qxforever 二人场
  
 ===== A - Abbreviation ===== ===== A - Abbreviation =====
行 24: 行 26:
 ===== B - Binary Code ===== ===== B - Binary Code =====
  
-idea from potassium, ​implemented ​by nikkukun+idea from potassium, ​upsolved ​by nikkukun
  
 ==== 题目描述 ==== ==== 题目描述 ====
行 47: 行 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|题解]]
  
  
行 67: 行 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}$ 可以用两次前缀和预处理求出。
 +
 +
 +===== G - Game on Graph =====
 +
 +upsolved by potassium
 +
 +==== 题目描述 ====
 +
 +给一个有向图，两个人 A B 在上面玩游戏。设初始节点为 $p$ ，两人轮流走，谁无路可走谁就输了。
 +
 +A 特别享受玩的过程，比起赢更想要平局。
 +
 +B DDL 特别多，平局还不如输掉。
 +
 +两人都采取最佳策略，求出任意先后手顺序、任意初始节点情况下，他们的胜负平情况。
 +
 +==== 解题思路 ====
 +
 +先判断能不能平。对于出度为 $0$ 的点，认为不能平。如果轮到 A 走且某个点的所有出点都不为平，那么这个点也不平；如果轮到 B 走且存在不平的出点，那么这个点也不平。进行 BFS 即可。
 +
 +再判断能不能胜。如果某个**不平**点的所有**不平**出点全为负，那么这个点负，否则胜。同样进行 BFS 。
 +
 +最后，如果还有无法判断胜负的节点，由于 A 会倾向平局，但 B 有选择负或平的机会，必然会选择负，那么 A 胜， B 负。
 +
 +===== H - Hard Refactoring =====
 +
 +solved by qxforever
 +
 +==== 题目描述 ====
 +
 +给一堆关于 $x$ 的逻辑表达式。求表达式真的解集。
 +
 +==== 解题思路 ====
 +
 +模拟即可。
  
  
行 87: 行 175:
  
  
 +
 +===== K - Kids Designing Kids =====
 +
 +upsolved by potassium
 +
 +==== 题目描述 ====
 +
 +给三个 $w_i,​h_i\in[1,​1000]$ 的 $01$ 矩阵，问能不能通过平移第二个矩阵，让前两个矩阵的异或中 $1$ 的位置和第三个矩阵能够一一对应。
 +
 +
 +
 +
 +==== 解题思路 ====
 +
 +题意可以转化为，是否可以让三个图通过平移，异或和为零矩阵。
 +
 +于是考虑找特殊点，不妨找左上角的 $1$ 。必然恰有两个矩阵左上角的点重合，否则显然三个矩阵无法异或和为零。枚举三种情况进行 check 即可。
 +
 +check 的时候，找出平移位置，再根据两个矩阵的异或和矩阵与第三个矩阵进行形状判断。
  
2020-2021/teams/i_dont_know_png/neerc2016.1590244698.txt.gz · 最后更改: 2020/05/23 22:38 由 nikkukun

页面工具

除额外注明的地方外，本维基上的内容按下列许可协议发布： CC Attribution-Share Alike 4.0 International
CC Attribution-Share Alike 4.0 International Donate Powered by PHP Valid HTML5 Valid CSS Driven by DokuWiki
京ICP备20018844号-3