Petrozavodsk Winter-2018. Carnegie Mellon U Contest

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 的边分形出去的八边形为 bcbcbcbca 同理。现在给出一条路径,问你是否是一个环(回到起点)。

题解:考虑两条规则,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)\)