Contest Info

date: 2017.10.06 13:00-18:00

practice link

Solutions

A. ABBA

题目大意：设 \(\alpha = (a_{1}, \cdots, a_{n}),\beta=(b_{1},\cdots,b_{m})\) 是两个向量，定义两个向量的乘积 \(\alpha\times\beta\) 为一个 \(n\times m\) 的矩阵，它的第 \(i\) 行第 \(j\) 列是 \(a_{i}b_{j}\) 。现在给你一个矩阵，问你它最少能写成几个矩阵的和，其中每个矩阵是两个向量的乘积。

题解：等价于用向量 \(\alpha\) 乘上 \(\beta\) 的每一项作为系数，去消去相应的列。所以答案是该矩阵的秩。

B. Black Sabbath

题目大意：给你一个长方形，内部有 \(n\) 个圆，圆之间两两相离，圆和矩形的边界也相离。现在要你把长方形分成 \(n\) 块，每块要正好完整地包含一个圆，并且是一个凸包。

题解：半平面交。对于每个圆，我们在它和其它圆中间画一条直线将他们分开，令这个半平面指向这个圆这一侧，再加上长方形的四个边界定义的四个半平面，这些半平面的交就是这个圆所在的凸包。这题有些吃精度，由标程得到启发，我们在两圆（设为 \(i,j\)）圆心连线的 \(\displaystyle{\frac{d^{2}+r_{i}^{2}-r_{j}^{2}}{2d}}\) 处画线，能取得比较好的精度。

C. Mr. Credo

题目大意：平面上有一些灯塔，每个灯塔可以照亮一个无穷大的扇形，求一个平面上没有被照亮的、半径为 \(1\) 的圆。保证如果将所有灯塔移动到一点，那么不论它们怎么旋转都不能照亮整个平面。

题解：根据题目的保证容易知道一定是有解的。同时我们注意到，输入坐标的绝对值在 \(50\) 以内，比答案要求的范围 \(10^{9}\) 小得多。于是我们可以忽略掉输入的灯塔的坐标，将它们看作都摆放在原点。由于输入扇形的角度是整数，我们容易找到一个整的角秒没有被照亮，我们只需要在它的角平分线并且离原点非常远的地方找一个圆就好了。

D. Deep Purple

unsolved

E. Elvis Presley

题目大意：给出两个整数 \(a\) 和 \(b\) （\(1\le a,b\le10^9,a\not=b\) ）。求一个最小的极大集合，要求包含 \(a\) 和 \(b\) ，且集合内任意两个数转成二进制（不含前导零）后都不是彼此的前缀。

题解：将 \(a\) 和 \(b\) 的二进制串求出，如果 \(a\) 和 \(b\) 就不满足条件则无解。否则，建出 \(a\) 和 \(b\) 的 trie，则最少的方案就是把，在 trie 的每个分支处，将不能走的那个儿子表示的串加入集合。复杂度 \(\mathcal{O}(\log{a}+\log{b})\)。

F. Frank Sinatra

题目大意 ：给定一棵边上带权的树，每次询问两个点，求两点路径上的权值集合的 \(\text{mex}\) 。

题解 ：树上莫队。然后对权值分块求 \(\text{mex}\)， 注意大于 \(n\) 的权值可以令其为 \(n\) 。

G. Green Day

题目大意 ：给定整数 \(n\geq 2\) ，要求你构造一个 \(n\) 个点的无自环无重边的无向图。并且每条边被染成 \(k\) 种颜色中的一种，每种颜色的所有边构成一棵原图的生成树。设颜色 \(c\) 的生成树为 \(T_c\) 。还要满足：对任意两种颜色 \(c,d\) ，对任意两个不同的点 \(u,v\) ，有 \(\text{path}_{T_c}(u,v)\cap \text{path}_{T_d}(u,v)=\{u,v\}\) 。

题解 ：一开始很容易想到对每种颜色 \(c\) ，\(T_c\) 构成一个菊花图。那么对特定的一种颜色，我们设菊花为点 \(w\)， 那么显然对于该种颜色来说，任意两点 \(u,v\) 的路径上除了 \(u,v\) 最多再包含点 \(w\) 。但是这样显然是不行的，因为菊花点的度数为 \(n-1\) ，不能连出其他颜色的边，不满足题意。

我们再考虑 \(T_c\) 中有两个菊花点。我们将其余点平均分成两部分，各连一个菊花，然后两个菊花点之间连一条边。对于其他的颜色来说，我们选取没被选过的点作为菊花即可。这样我们一共需要 \(2k\) 个点。稍一验证就可以发现满足题意，任意两点 \(u,v\) 之间的路径最多包含四个点 \(\{u,v,w_1,w_2\}\) ，其中 \(w_1,w_2\) 是菊花点。在另一种颜色的生成树上，\(u,v\) 之间的路径最多为 \(\{u,v,w_1',w_2'\}\) ，因为我们选取的菊花不同，所以交点只会为 \(\{u,v\}\) 。

具体实现的时候，可以在正 \(2k\) 边形上连边，写代码方便一点。

H. Hans Zimmer

题目大意：给你一个 \(w\times h\) 的矩形，要对它切 \(n\) 刀，每刀等概率地选择横/竖切，再等概率地选择下刀位置。问切完之后最小的矩形面积的期望。

题解：首先 \(wh\) 可以最后乘。注意到横竖互不影响，于是我们可以枚举横切有多少刀，设为 \(i\) 。那么这种情况对答案的贡献就是 \({n \choose i}/2^n \cdot E_i\) 。再考虑 \(E_i\) 的计算，稍微积一下分可以发现切 \(i\) 刀在一维下的期望长度是 \(L_i=\frac{1}{(i+1)^{2}}\) 。另外一边切了 \(n-i\) 刀，于是 \(E_i=L_i\cdot L_{n-i}=\frac{1}{(i+1)^{2}(n-i+1)^{2}}\) 。注意用 log 控制精度，并且输出使用 %lg。

coldwater’s comment

\(L_n\) 的具体计算过程：设随机变量 \(X\) 表示最小面积，先计算 \(P(X\ge x)\)。设随机变量 \(X_{i}\) 表示右边 \((i+1)\) 个区域的最小面积，随机变量 \(Y_{i}\) 表示倒数第 \(i\) 次切割的位置，显然有 \(Y_{i}\sim U(0,1)\)。设 \(P(X_{i}\ge x|Y_{i+1}=l)\) 表示在 \(Y_{i+1}=l\) 的条件下，\(X_{i}\ge x\) 且每次切割都在上一次切割右边的概率，则所求为 \(n!P(X_{n}\ge x|Y_{n+1}=0)\) 。我们用数学归纳法证明 \(P(X_{i}\ge x|Y_{i+1}=l)=\frac{1}{i!}[1-l-(i+1)x]^{i}\)。根据全概率公式有 \(P(X_{1}\ge x|Y_{2}=l)=\int_{l+x}^{1-x}1\cdot f(y_{1})\mathbb{d}y_{1}=1-l-2x\) 满足要求。 \[ \begin{aligned} &P(X_{i}\ge x|Y_{i+1}=l)\\ =&\int_{l+x}^{1-ix}P(X_{i-1}\ge x|Y_{i}=y_{i})f(y_{i})\mathbb{d}y_{i}\\ =&\frac{1}{(i-1)!}\int_{l+x}^{1-ix}(1-y_{i}-ix)^{i-1}\mathbb{d}y_{i}\\ =&\frac{1}{(i-1)!}\int_{0}^{1-l-(i+1)x}t^{i-1}\mathbb{d}t\\ =&\frac{1}{i!}t^{i}|_{0}^{1-l-(i+1)x}\\ =&\frac{1}{i!}[1-l-(i+1)x]^{i} \end{aligned} \] 故 \(P(X\ge x)=[1-(n+1)x]^{n}\)，故最终答案为 \(\int_{0}^{\frac{1}{n+1}}x(1-P(X\ge x))'\mathbb{d}x=\frac{1}{(i+1)^{2}}\)

I. Ivan Dorn

题目大意：有一个长度为 \(n\le5\times10^5\) 的数列 \(\{a_n\}(-10^9\le a_i\le10^9\))。 \(m\le5\times10^5\) 次询问，每次询问给出一个区间 \([ql,qr]\) ，问这个区间中满足 \((a_l=a_r)\land \big(a_l\ge a_i(l<i<r)\big)\) 的子区间 \([l,r]\) 的 \(r-l\) 最大是多少。

题解：先将所有询问按右端点升序排序，离线处理这个问题。

我们使用一个类似单调栈的数据结构，按 \(a_i\) 的值单调递减来维护一个位置的栈。栈的每一个元素用一个 vector 表示 \(a_i\) 相等的位置的组（vector 中位置递增）。

我们从左往右考虑每个 \(a_i\) ，对于当前的 \(a_i\) ，我们先将栈中比当前的 \(a_i\) 小的组都弹出去，并且用一个线段树 \(A\) 来维护这些出栈的位置对询问的贡献。每弹出一个位置 \(j\) ，我们在线段树 \(A\) 中用 \(k-j\) 去更新询问的左端点在区间 \([1,j]\) 的答案，其中 \(k\) 是与 \(j\) 同组中最大的位置。每个位置最多出栈一次，因此这一部分的时间复杂度是 \(\mathcal{O}(n\log{n})\)。处理完出栈操作之后，再将位置 \(i\) 入栈，并且更新栈中与 \(i\) 同组的答案为 \(i-k\) ，其中 \(k\) 是该组中最小的位置。我们用线段树 \(B\) 来维护栈中每个元素的答案，这一部分的时间复杂度也是 \(\mathcal{O}(n\log{n})\)。

维护好栈和线段树 \(A\)， \(B\) 后，我们就可以来回答 \(qr=i\) 的询问了。先在线段树 \(A\) 中询问左端点 \(ql\) 的答案，这一部分是已出栈的位置对这次询问的贡献。然后二分找到当前栈中所有位置都不小于 \(ql\) 的组，去线段树 \(B\) 中询问栈中组的后缀的最大值。然后，再对夹着 \(ql\) 的那个组，在其内部进行二分，找到满足条件的最小的位置，用这组中最大的位置减去它，来更新答案。这一部分是在当前栈中的位置对这次询问的贡献。每次回答的时间复杂度 \(\mathcal{O}(\log{n})\)。

综上所述，整个算法的时间复杂度为 \(\mathcal{O}((n+m)\log{n})\)。

J. Jimi Hendrix

题目大意：给出一棵 \(n\) 个节点的树，每条边上有一个英文小写字母。再给出一个长度为\(m\le n-1\) 的只由英文小写字母组成的字符串 \(S\) ，问是否存在两点 \(u\) 和 \(v\) ，满足 \(S\) 是从 \(u\) 走到 \(v\) 的路径形成的字符串的子序列。

题解：

法一：考虑用树分治来枚举所有路径，每一层分治时记录每个子树自底向上匹配，最多能让 \(S\) 多长的前缀成为子序列，以及最多能让 \(S\) 多长的后缀成为子序列，如果两个不同子树的答案可以覆盖完 \(S\) ，那么就有答案。复杂度\(\mathcal{O}(n\log{n})\)。

法二：直接树 dp 记录往下最长的前缀和后缀形成的子序列。因为前缀和后缀要来自不同的子树才可以，所以记录一下最大和次大。

K. Korn

题目大意 ：给定一个连通无向图，无自环和重边。定义从点 \(v\) 开始的极长路径为一个顶点序列 \(v=p_0,p_1,\dots,p_k=u\) ，且满足下列条件：

• 相邻两点之间有边连接，且每条边只能访问一次，点可以多次访问。
• 不存在点 \(p_{k+1}\) ，使得将该点接在上述序列之后，仍然满足第一个条件。

其中，点 \(u\) 称为终止结点。如果任何从点 \(v\) 开始的极长路径都访问了原图的每条边，且终止结点也是 \(v\) ，那么称点 \(v\) 是合法的。求出所有的合法结点。

题解 ：首先原图要是一个欧拉图，否则显然一定没有合法结点。点 \(u\) 是合法结点，当且仅当点 \(u\) 在任意一个简单环（无重点）中都出现。

法一：上述条件等价于，如果删掉点 \(u\) ，那么原图不存在任何环。那么我们对点进行分治，要递归进入 \([l,r]\) 时，我们将所有不以 \(u\in [l,r]\) 为端点的边都连上。如果当前存在环，那么显然 \([l,r]\) 都不会作为答案。否则，递归进入到最后一层的时候，\(l=r\) 就是一个答案了。判断环可以用按秩合并的并查集来做，恢复现场也很方便。

法二：我们对图进行 dfs，显然无向图的 dfs 搜索树中，只有树边和前后向边（没有横叉边）。每条非树边都可以对应一个简单环，这样的环有 \(m-(n-1)\) 个。我们再用类似 tarjan 求 scc 的算法，求出每个点的 dfn 和 low 值。

我们来考虑点 \(u\) 是否合法，那么就是要判断对于上述的只含一条非树边的简单环， 是否每一个都包含了 \(u\) 。对于 \(u\) 的儿子节点 \(v\) ，显然有 \(\text{low}(v)\leq \text{dfn}(u)\) ，否则 \((u,v)\) 这条边是桥边，原图不可能为欧拉图。如果 \(\text{low}(v)= \text{dfn}(u)\) ，那么说明这一个简单环给 \(\deg(u)\) 贡献了 \(2\) ，我们需要减掉 \(1\) 。如果\(\text{low}(v)<\text{dfn}(u)\) ，那么给 \(\text{deg}(u)\) 贡献了 \(1\) 。\(u\) 的父亲节点（如果有的话），以及每条后向边也给 \(\text{deg}(u)\) 贡献了 \(1\) 。所以我们只要通过 \(\text{deg}(u)\) 算出 \(u\) 所在的简单环个数，跟 \(m-(n-1)\) 比较就可以了。