====== 2016-2017 Northeastern European Regional Contest (NEERC 2016) ====== [[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 的时候，找出平移位置，再根据两个矩阵的异或和矩阵与第三个矩阵进行形状判断。