Contest Info

date: 2018.09.23 12:00-17:00

practice link

Solutions

A. Domains

题目大意：

给出若干个ss的规则，包括匹配的域名和vpn，给出格式要求和规则冲突的描述，将不符合格式要求的和与前面的合法规则冲突的规则都删去（域名开头可以有一个通配符），之后多次询问，给出一个可能开头含一个通配符的域名，问有多少合法规则可以匹配它。

题解：

因为通配符都在开头一个，我们把域名翻转，用三个对应的字典树维护，这样冲突和询问都能处理了。字典树需要支持查询子树和与前缀和。

B. K-Dimensional Foil

题目大意：给你 \(n\) 个 \(k\)（未知）向量，给出每个向量的前三维坐标及它们两两的欧氏距离，求满足要求的最小的 \(k\)。

题解：显然我们可以把前三维事先去掉。首先注意到任意解都可以平移到 \(\vec{v}_{1}=0\) 的位置。假设 \(k\) 维的时候有解，按照 Gram-Schmidt 正交化的过程，对于 \(\vec{v}_{2},\cdots,\vec{v}_{n}\) 一定存在一个“下三角”的解。这里 \(n\) 不一定等于 \(k\)，下三角的定义参考下面的求解过程。

考虑求解第 \(i\) 个向量。不妨设 \(\vec{v}_{2},\cdots,\vec{v}_{i-1}\) 中最高维的非零元素下标为 \(m\)。那么我们有 \[ \begin{aligned} (\vec{v}_{i}-\vec{v}_{j})^{2}&=d_{ij}\\ \vec{v}^{2}_{i}-2\vec{v}_{i}\cdot\vec{v}_{j}+\vec{v}^{2}_{j}&=d_{ij}\\ \vec{v}_{i}\cdot\vec{v}_{j}&=\frac{d_{ij}-d_{i0}-d_{j0}}{2} \end{aligned} \] 由于这是一个下三角矩阵，我们很容易解这个方程。但是 \(\vec{v}^{2}_{i}\) 是已知的，前 \(m\) 维的平方和可能不等于 \(\vec{v}^{2}_{i}\)。若大于，则显然无解；若小于，那么我们需要补充第 \(m+1\) 维。

C. Graph

题目大意：若干次询问，每次询问 \([L, R]\)，输出无向简单图 \(G\) 在点集 \([L, R]\) 上的导出子图两两可达点对个数。

题解：把点按标号顺序排列之后按照度数 \(B\) 分块。设每一块的区间为 \([l_i,r_i]\)，那么满足 \([l_i,r_i)\) 的度数之和 \(<B\)，而 \([l_i,r_i]\) 的度数之和 \(\geq B\)。枚举块的右端点 \(r_i\)，计算 \(r_{i-1}<L\leq r_i\) 的询问的答案。

把这些询问的右端点排序，然后右端点依次向右扩展，这里可以用启发式合并+路径压缩的并查集维护（合并的时候贡献 \(\text{sz}_u\times \text{sz}_v\)）。然后左端点从 \(r_i\) 扩展过去，这里用可撤销的启发式合并的并查集，求出答案之后撤销左边。对于不跨 \(r_i\) 的询问，直接暴力计算即可。

时间复杂度： \(\mathcal{O}(\frac{2m}{B}\times n+q\times B\times \log n)\)，取 \(B=\sqrt{(2m)/\log n}\)。

细节：

• 每个点 \(u\) 的出边按照出点 \(v\) 和 \(u\) 的标号大小关系分两类，然后排序。

• 向左扩展的时候，直接跳过度为 \(0\) 的点，先预处理。

D. Chinese Checkers

题解：从最上面的点开始，向左下，右下，左下，右下… 这些点视为每一行的原点，建立坐标系。然后按照题意模拟。

E. Cats and Fish

签到题

F. Secret Poems

签到题

G. Liaoning Ship’s Voyage

计算几何。注意边界情况。

H. Puzzle Game

题目大意：给定 \(n\times m\) 的矩形，和一个整数 \(P\)，你可以最多把一个位置改成 \(P\)。要求最小化最大子矩形和。

题解：预处理出前若干行、后若干行、前若干列、后若干列的最大子矩形和。枚举一个位置 \((i,j)\)，如果它的上部、下部、左部、右部的最大子矩形和 \(a\) 可以取到全局最大 \(b\)，那么说明最大子矩形不一定包括位置 \((i,j)\)。否则一定包含 \((i,j)\)，我们用 \(\max(a, b - v[i][j] + P)\) 更新答案。

I. Colored Nodes

题目大意：给你一个 \(n\) 个点 \(m\) 条边的无向图。点 \(i\) 开始时的颜色是 \(i\)。第 \(kn+i(k\in\mathbb{N},1\le i\le n)\) 秒，点 \(i\) 会将所有与它相邻的点染成它当前的颜色。设 \(f(i)=\lim\limits_{t\to+\infty}\frac{S(i,t)}{t}\)，其中 \(S(i,t)\) 表示颜色 \(i\) 在前 \(t\) 秒出现的总次数。求所有的 \(f(i)\)。

题解：首先我们暴力从 \(1\) 到 \(n\) 跑一遍，设点 \(i\) 的颜色为 \(c(i)\)，那么显然经过 \(t\) 个周期后，点 \(i\) 的颜色会变为 \(\overbrace{c(c(\cdots c}^{t个}(i)))\)。我们从 \(c(i)\) 向 \(i\) 连边，那么显然这个图的每个连通块是一个有向环加上一些外向树。容易发现，经过足够长的时间后，某个连通块上的每个点的颜色都是环上的颜色一直循环，这很容易处理。之后再暴力从 \(1\) 到 \(n\) 跑一遍计算一个周期内部的答案即可。

J. Pangu and Stones

签到题。

Dirt Replay

D: -1 题意

E: -2 读错题；multiset

G: -1 边界case（精度）

H: -3 访问到了未初始化边界