差别

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

--- 2020-2021:teams:i_dont_know_png:neerc2016 [2020/05/23 17:15]
qxforever 创建
+++ 2020-2021:teams:i_dont_know_png:neerc2016 [2020/05/24 18:52] (当前版本)
potassium D
@@ 行 2: / 行 2: @@
 [[https://codeforces.com/gym/281394|比赛链接]]
+nikkukun qxforever 二人场
+===== A - Abbreviation =====
+solved by nikkukun & qxforever
+==== 题目描述 ====
+给一些文本串，将其中需要缩写的单词串改为首字母缩写形式。需要缩写的串满足：
+  - 每个单词首字母大写，且之后有至少一个小写字母
+  - 每个单词之间仅有一个空格连接
+==== 解题思路 ====
+🐴力题。
+===== B - Binary Code =====
+idea from potassium, upsolved by nikkukun
+==== 题目描述 ====
+给一些 $01$ 串，每个串中最多有一个 ''?''，其中可以填 $0$ 或 $1$。指定一种填的方案，使得不存在一个串是另一个串的前缀，或说明无解。
+字符串总长度为 $5 \times 10^5$。
+==== 解题思路 ====
+把 Trie 建出来，将有问号的串分别考虑 $01$ 后都插入到树上，这样变成在树上选一些点，这些点两两之间要满足一些限制：
+  - 同一个串对应的两个点恰选一种
+  - 选中一个点后，其祖先不能有其他点被选
+  - Trie 树的一个节点中，只能有一个点被选
+这就是一个 2-SAT 问题。
+**限制 1 的建图**：基操。
+**限制 2 的建图**：额外设置一个辅助变量 $t_u$ 表示 $u$ 及其祖先是否有点被选，则某个点 $u$ 被选，当且仅当 $t_u$ 为真且 $t_{\mathrm{pa}(u)}$ 为假。显然 $t_i$ 变量是可以在相邻两个位置建立关系的，详见 //CF1215 - Radio Stations//。
+**限制 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|题解]]
+===== E - Expect to Wait =====
+solved by nikkukun
+==== 题目描述 ====
+一个共享单车停车场会在一些时刻有人借车或还车，且同一时刻只会发生其中一种事件，若某个时候无车可借时，就会排队等待到下一次有人还车。$10^5$ 次询问停车场初始有 $b_i$（$0 \leq b \leq 10^9$）辆车时，所有人的等待时间之和，或说明根本等不到车。
+时刻数不超过 $10^5$，单次借还数量不超过 $10^4$。
+==== 解题思路 ====
+先假设初始时没有车，把每个时刻的总借车人数（包括等待中的）减去总归还车辆数的差按时间在坐标轴 $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$ 的逻辑表达式。求表达式真的解集。
+==== 解题思路 ====
+模拟即可。
+===== J - Jenga Boom =====
+solved by nikkukun & qxforever
+==== 题目描述 ====
+给一个叠叠乐，每次抽掉其中的一块，如果有某一层之上的总重心投影超出了该层平面的凸包或在边界上，则积木倒塌。
+求哪次操作之后倒塌，或说明不会倒塌。
+==== 解题思路 ====
+注意到范围很小，因此对每层维护 $\sum_i m_i \times x_i$ 和 $\sum_i m_i$（$x_i$ 为某个方向的坐标轴），就可以计算出某一层之上的重心了。所有的变量都可以在一次抽掉积木后 $O(\max \{h, n\})$ 更新。
+===== K - Kids Designing Kids =====
+upsolved by potassium
+==== 题目描述 ====
+给三个 $w_i,h_i\in[1,1000]$ 的 $01$ 矩阵，问能不能通过平移第二个矩阵，让前两个矩阵的异或中 $1$ 的位置和第三个矩阵能够一一对应。
+==== 解题思路 ====
+题意可以转化为，是否可以让三个图通过平移，异或和为零矩阵。
+于是考虑找特殊点，不妨找左上角的 $1$ 。必然恰有两个矩阵左上角的点重合，否则显然三个矩阵无法异或和为零。枚举三种情况进行 check 即可。
+check 的时候，找出平移位置，再根据两个矩阵的异或和矩阵与第三个矩阵进行形状判断。

CVBB ACM Team

用户工具

站点工具

差别

页面工具