Contest Info

date: 2019.03.10 13:15-18:15

practice link

Solutions

A. Mines

题目大意：一维数轴上有 \(n\le2\times10^5\) 个雷。第 \(i\) 个雷在位置 \(p_i\) 。花费 \(c_i\) 的代价可以引爆第 \(i\) 个雷，并将 \([p_i-r_i,p_i+r_i]\) 范围的雷全部引爆，引起连锁反应，而不需要额外的代价。现在有 \(Q\le2\times10^5\) 次修改，每次修改一个雷的花费，然后询问使得所有雷爆炸的最小花费是多少。

题解：建一棵线段树，每个父亲节点向左右儿子分别连一条有向边。然后枚举每一个雷，从 \(p_i\) 所在的叶子节点，向 \([p_i-r_i,p_i+r_i]\) 对应的节点连边，tarjan 求一次 scc。删掉所有可以从含有叶子节点的 scc 到达的 scc，剩下的每个包含叶子的 scc 的最小值之和就是答案。修改可以每个 scc 维护一个 multiset。时间复杂度 \(\mathcal{O}(n\log{n})\) 。

B. Balls

签到题。

C. Flip a Coin

题目大意：有两个人，他们分别拥有 0/1 串 \(s\) 和 \(t\)。现在不停地掷一枚均匀的硬币，正面为 \(1\)，反面为 \(0\)。如果某一时刻硬币组成的串中包含 \(x\)，那么第一个人赢；如果包含 \(y\)，那么第二个人赢；如果同时包含 \(x,y\)，那么平局。问这三种情况的概率。

题解：用两维分别记录 \(s\) 和 \(t\) 的 kmp 的 fail，高消即可。注意我们的状态的实际含义是该状态出现次数的期望，如果把它解释成出现的概率，个人感觉在概率论上是说不通的。由于终止状态只能出现 \(0\) 或 \(1\) 次，因此它出现次数的期望就是它出现的概率。

时间复杂度 \(\mathcal{O}((|s||t|)^{ 3})\)。

D. Octagons

题目大意：给出一个八边形的“分形”图案，中央的八边形边依次为 abababab，从 b 的边分形出去的八边形为 bcbcbcbc；a 同理。现在给出一条路径，问你是否是一个环（回到起点）。

题解：考虑两条规则，aa 可以缩减为空串，ababa 可以缩减为 bab。如果原路径可以被缩为空，那么就是一个环。

F. Very New York

题目大意：给出二维平面上的 \(n\le10^5\) 个整点。给出 \(q\le10^5\) 次询问，每次问到点 \((x_i,y_i)\) 的曼哈顿距离不超过 \(d_i\) 的点数。

题解：转切比雪夫距离之后二维数点，扫描线加树状数组即可，时间复杂度 \(\mathcal{O}(n\log{n})\)。

G. Sheep

题目大意：给你 \(n\) 个 \([0,T]\to\mathbb{R}\) 上的一次函数 \(f_{1},\cdots,f_{n}\)，定义两个一次函数 \(f,g\) 的距离为 \((\max_{x\in[0,T]}(f(x)-g(x)))^{2}+(\min_{x\in[0,T]}(f(x)-g(x)))^{2}\)。要你找一个一次函数 \(f\)，使得 \(f\) 到 \(f_{1},\cdots,f_{n}\) 距离的最大值最小。

题解：能不能先搞清楚平方在括号里面还是外面。。。

两个一次函数相减后还是一次函数，因此最大值和最小值显然分别在 \(0\) 和 \(T\) 处取到。因此距离即为 \((f(0)-g(0))^{2}+(f(T)-g(T))^{2}\)。设 \(f_{i}(x)=kx+b\)，那么我们要让 \((b_{i}-b)^{2}+((k_{i}T+b_{i})-(kT+b))^{2}\) 的最大值最小。如果我们将 \((b_{i},k_{i}T+b_{i})\) 和 \((b,kT+b)\) 分别看作平面上的点，那么显然我们就是要求 \((b_{i},k_{i}T+b_{i})\) 组成的点集的最小包围圆，而 \((b,kT+b)\) 则是最小包围圆的圆心。

时间复杂度 \(\mathcal{O}(n)\)。

H. Bin Packing

题目大意：给出 \(n(n\le 24)\) 个物品，每个物品有体积 \(w_i\)。让你把它们分成最少的组，使得每一组的体积之和都不超过 \(V\)。

题解：集合 dp。设 \(\text{dp}_S=(i, j)\) 表示选择了集合 \(S\) 中的所有物品，它们最少分成 \(i\) 组，最后一组的体积最少为 \(j\)。转移的时候，枚举一个不在集合中的物品，尝试把它加进最后一组。复杂度 \(\mathcal{O}(n\times 2^n)\)。

I. Statistics

题目大意：给出 \(n\le5000\) 个物品，第 \(i\) 个物品的体积为 \(v_i\) ，求所有体积和恰为 \(1\le V\le5000\) 且物品数量最小的集合中，最小的平均体积，最小的中位数（偶数的中位数是中间靠左的一个），最小的众数个数，最小的 \(\max-\min\)。

题解：先将物品按大小排序，对于同样体积的物品计算其是第几次出现。然后做若干次维护体积为 \(V\) 的最小物品数量的背包。

• 最小的平均体积就直接求出最小的物品数量即可。
• 最小的中位数，分别做前缀和后缀的背包，枚举中位数的位置，枚举中位数左边的体积和，然后检查其个数是否合法即可。
• 最小的众数个数，就枚举答案，然后每轮只把新增加的物品加入背包更新，当取到最小物品数量时停止枚举即可。
• 最小的最大体积减去最小体积之差，就 two pointer 枚举最小体积和最大体积，用两个栈来维护删除：每次新增的加入第一个栈，并在栈顶的基础上更新背包；删除时，若第二个栈为空，则清空第一个栈，按退栈的顺序加入第二个栈，同样的更新栈顶的背包，记录每个位置的背包状态，然后删除就踢掉第二个栈的栈顶即可；因为只需要一个位置的值，可以 \(\mathcal{O}(V)\) 合并两个栈顶的背包。

时间复杂度 \(\mathcal{O}(nV)\)。

J. Zigzag

题目大意：给定两个长度分别为 \(n\) 和 \(m\) 的序列 \(\{a_i\}, \{b_i\}\)。让你求一个最长的公共子序列 \(x_1, \dots, x_k\)，满足对 \(\forall i\in [2, k)\)，满足 \(x_{i-1}>x_i<x_{i+1}\) 或者 \(x_{i-1}<x_i>x_{i+1}\)。

题解：考虑 dp。假设 \(\text{dp}_{x, y, k}\) 表示考虑了第一个序列的前 \(x\) 项，第二个序列的前 \(y\) 项，且与答案序列的前一项满足条件 \(k=0/1\) （分别表示增大/减少）的最长公共子序列。且 \(a_x\) 和 \(b_y\) 一定要选。

状态是 \(\mathcal{O}(nm)\) 的，如果我们暴力转移，那么总复杂度是 \(\mathcal{O}(n^2m^2)\) 的。我们对决策也 dp。考虑 \(f_{i, y, k}\) 表示上一次决策点在 \((x, y, k\oplus 1)(x<i)\) 。\(g_{i, j, k}\) 表示上一次决策点在 \((x, y, k\oplus 1)(x<i, y<j)\)，\(i\) 满足条件 \(k\)。

那么我们只需要对 \(a_i=b_j\) 的时候，用 \(\max(0, g_{i,j,k})+1\) 来更新 \(\text{dp}_{i,j,k}\) 即可。此时，显然也可以用 \(\text{dp}_{i, j, k}\) 更新 \(f_{i+1,j,k\oplus 1}\)。

考虑 \(f, g\) 内部的转移，显然有 \(f_{i,j,k}\) 可以更新 \(f_{i+1,j,k}\)，同理 \(g_{i,j,k}\) 可以更新 \(g_{i,j+1,k}\)。我们假设 \(k=0\)，那么在 \(b_j<a_i\) 的时候，可以从 \(f_{i,j,k}\) 更新 \(g_{i,j+1,k}\)。

正确性的保证是因为我们转移 \(f\) 的时候，\(j\) 这一维始终等于上一次决策的 \(y\)。从 \(f\) 转移到 \(g\) 的时候，我们的 \(i\) 已经满足了条件 \(k\)，可以移动 \(j\)。\(g\) 内部转移的时候，也保证 \(i\) 这一维不变。所以最后用 \(g\) 转移 \(\text{dp}\) 的时候，\(a_i=b_j\)，那么都满足条件 \(k\)。转移现在是 \(\mathcal{O}(1)\)，总复杂度 \(\mathcal{O}(nm)\)。

K. Knapsack

题目大意：做一个 \(n\le500\)，\(W\le10^{17}\) 的背包，体积基本随机。

题目大意：对于两个状态如果有 \(W_{i}\ge W_{j},V_{i}\le V_{j}\)，那么显然状态 \(i\) 是没用的。可以证明体积随机的情况下有用的状态很少。归并维护这些状态即可。

时间复杂度 \(\mathcal{O}(nS)\)。