Contest Info

date: 2018.08.03 09:00-14:00

practice link

Solutions

A. Donut

题目大意：平面上有 \(n\) 个点，每个点有一个权值。现在要求你在平面上选取一个整点，使得到该点切比雪夫距离在 \([l,r]\) 中的点的权值和最大。

题解：注意到对于每个点，距离它 \([l,r]\) 的范围是一个边长为 \(2r\) 的正方形里面套着一个边长为 \(2l\) 的正方形。这个图形可以拆成若干个矩形，之后就变成一个经典的扫描线题了。但是在拆分的时候一定要注意不要重叠，尤其是交界处的点要特别小心。

B. Circular Arrangement

题目大意：有 \(n\) 种颜色，每种有 \(a_{i}\) 个。定义它们的一个排列的价值是每一段连续相同的颜色长度的乘积，并且开头和结尾算做连续。求所有排列的价值之和。

题解：我们先不考虑头尾连续。考虑枚举每种颜色被分为了多少段，设为 \(t_{i}\)。记 \(g_{i,j}\) 表示 \(j\) 个某种颜色分为 \(i\) 段的所有分法每段长度的乘积的和，那么可以递推求出： \[ g_{i,j}=\begin{cases} &1&(i=j=0)\\ &0&(ij=0,i+j\neq0)\\ &\sum_{k=0}^{j}g_{i-1,j-k}&(i>0,j>0) \end{cases} \] 对于一个固定的 \(t_{1},\cdots,t_{n}\)，根据容斥原理，答案为： \[ \prod_{i=1}^{n}g_{t_{i},a_{i}}\sum_{1\le k_{1}\le t_{1},\cdots.1\le k_{n}\le t_{n}}\left((-1)^{\sum_{i=1}^{n}t_{i}-\sum_{i=1}^{n}k_{i}}\left(\prod_{i=1}^{n}{t_{i}-1\choose k_{i}-1}\right){\sum_{i=1}^{n}k_{i}\choose k_{1},\cdots,k_{n}}\right) \] 那么最终答案为： \[ \begin{aligned} &\sum_{1\le t_{1}\le a_{1},\cdots,1\le t_{n}\le a_{n}}\left(\prod_{i=1}^{n}g_{t_{i},a_{i}}\sum_{1\le k_{1}\le t_{1},\cdots.1\le k_{n}\le t_{n}}\left((-1)^{\sum_{i=1}^{n}t_{i}-\sum_{i=1}^{n}k_{i}}\left(\prod_{i=1}^{n}{t_{i}-1\choose k_{i}-1}\right){\sum_{i=1}^{n}k_{i}\choose k_{1},\cdots,k_{n}}\right)\right)\\ =&\sum_{1\le k_{1}\le a_{1},\cdots,1\le k_{n}\le a_{n}}\left((\sum_{i=1}^{n}k_{i})!\prod_{i=1}^{n}\left(\sum_{k_{i}\le t_{i}\le a_{i}}\left((-1)^{t_{i}-k_{i}}{t_{i}-1\choose k_{i}-1}\frac{g_{t_{i},a_{i}}}{k_{i}!}\right)\right)\right)\\ \end{aligned} \] 记 \(\sum_{k_{i}\le t_{i}\le a_{i}}\left((-1)^{t_{i}-k_{i}}{t_{i}-1\choose k_{i}-1}\frac{g_{t_{i},a_{i}}}{k_{i}!}\right)=c_{k_{i},a_{i}}\)，那么有 \[ \begin{aligned} =&\sum_{j=n}^{\sum_{i=1}^{n}a_{i}}j!\sum_{\sum_{i=1}^{n}k_{i}=j}\prod_{i=1}^{n}c_{k_{i},a_{i}} \end{aligned} \] 容易发现这里我们可以写成多项式的形式。设 \(f_{a_{i}}(x)=\sum_{i=1}^{n}c_{i,a_{i}}x^{i}\)，那么答案为： \[ \sum_{j=n}^{\sum_{i=1}^{n}a_{i}}j![x^{j}]\prod_{i=1}^{n}f_{a_{i}}(x) \] 这部分的复杂度为 \(\mathcal{O}(n^{2}a^{2})\)。

接下来考虑头尾如何处理。\(n=1\) 时特判一下。\(n\ge2\) 时，我们考虑把尾部所有跟头部相同的颜色循环移动到头部，例如 \(12321\rightarrow11232\)。那么我们的问题就转化成了，求出所有头部与尾部颜色不同的排列的价值之和，其中头部那一段的贡献为它长度的平方。接下来枚举头部的颜色和它的长度，利用容斥可以很容易地求出答案。

总复杂度 \(\mathcal{O}(n^{2}a^{2})\)。

C. Earthquake

题目大意：有 \(n\) 条道路，第 \(i\) 条道路由 \(k_{i}\) 座桥组成。地震过后，每座桥有 \(p_{ij}\) 的概率被毁。现在可以用 \(1\) 的代价检查一座桥是否被毁，问最优策略下检查出一条道路可以通过或判断所有道路都不能通过的最小期望。

题解：显然在检查某条道路时应当从被毁概率最高的桥开始检查。假设我们现在已经确定了一个检查道路的顺序 \(c_{1},\cdots,c_{n}\)，那么我们可以用 \(dp\) 来计算期望。记 \(dp[i]\) 表示检查 \(c_{i}\) 之后所有道路的期望，那么有： \[ dp[i]=(1+p_{c_{i}1}dp[i+1])+(1-p_{c_{i}1})(1+p_{c_{i}2}dp[i+1])+\cdots \] 容易发现 \(dp[i]\) 是一个关于 \(dp[i+1]\) 的一次函数，且系数仅由道路 \(c_{i}\) 决定。于是现在问题变为了：有 \(n\) 个一次函数，如何安排它们嵌套的顺序使得最后的值最小。设有两个一次函数 \(y=a_{1}x+b_{1}\) 和 \(y=a_{2}x+b_{2}\)，要使 \(a_{1}(a_{2}x+b_{2})+b_{1}\le a_{2}(a_{1}x+b_{1})+b_{2}\)，可以解得 \(\frac{a_{1}-1}{b_{1}}\le\frac{a_{2}-1}{b_{2}}\)。因此按照 \(\frac{a_{i}-1}{b_{i}}\) 从小到大的顺序嵌套最优。

D. Dynamic Input Tool

题目大意：给定一个目标字符串 \(t\)，初始你手上是一个空串 \(s\)。你每次可以在 \(s\) 后面增加一个字符，或者增加一个 \(s\) 的非空子序列，问最少操作步数。

题解：贪心，每次增加最长的串。可以预处理每个位置的每种字母的下一个位置，以及每种字母第一次出现的位置，然后直接模拟。

E. Central Lake

题目大意：给你两个同心圆，半径分别为 \(r\) 和 \(R(r<R)\)。圆周上有一些点，会有一些增删操作。每次问两点间最远距离，其中距离是指不穿过小圆的最短路径长度。

题解：显然两点间的距离与两点间的弧长成正比，并且这个距离可以简单地和小圆切一下来计算。现在我们需要处理的就是圆上两点间最长的弧。我们可以按时间在线段树上分治，预处理出每个点存在的时间区间，将它插入线段树中，之后遍历一遍线段树即可计算出所有答案。

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

F. Computing MDSST

题目大意：

给出一个\(n\le15\)个点的无向完全图，求一个最小路径和生成树，即最小化生成树上两两之间路径长度的和。

题解：

用dp[x][s]表示以\(x\)为根，子树中点集为\(s\)的最优值，转移时枚举子集即可。

时间复杂度\(O(n^2\cdot3^n)\).

G. MST with Metropolis

题目大意：

给出一个\(n\)个点\(m\)条边的简单无向连通图，对于每一个点\(i\)，求必须选与\(i\)相连的所有边的条件下的最小生成树。

题解：

先求一个全局最小生成树，之后对于每个点用LCT维护破圈法来找包含给定边的最小生成树，每次询问后撤消即可，时间复杂度\(((n + m)\log{m})\).

H. Number of Cycles

题目大意：给定\(1\le N\le1000\)，要求构造不超过\(12\)条线段，使得线段端点和交点作为顶点的平面图中，简单环的数量恰好为\(N\).

题解：

用下面六条两两相交的主线段进行构造：

搜索每条线段激活的区间，暴力求出简单环的数量，并统计方案。

如果搜到了\(N\)则直接输出方案，否则，我们在第三象限构造类似的图，用两部分的和拼出答案。

I. Sum of Squares of Occurrence Counts

题目大意：

给定字符串\(S\)，对于\(S\)的每个前缀\(S_i\)，求\(S_i\)所有本质不同子串在\(S_i\)中出现次数的平方和。

题解：

先建出\(S\)的sam和parent树，之后转化为\(n\)次操作，每次给一条到根的路径出现次数都+1，之后统计答案。

把+1从平方中拿出来维护增量即可，把parent树轻重链剖分之后线段树维护。

时间复杂度\(O(n\log^2{n})\).

J. push wjj

K. Subsequence Queries

题目大意：给你一个字符串 \(S\) 和 \(Q\) 个询问，每次问一个区间中本质不同的子序列有多少。

题解：设 \(dp[i]\) 表示以 \(i\) 结尾的子序列数量，\(\text{sum}=\sum_{i\in\Sigma}dp[i]\)，则答案为最后的 \(\text{sum}\)。设现在要转移到字符 \(x\)，则有： \[ \begin{cases} dp[x]&=\text{sum}\\ dp[j]&=dp[j](j\neq x)\\ \text{sum}&=2\text{sum}-dp[x] \end{cases} \] 这个 \(dp\) 也很容易写成矩阵。于是我们的区间查询可以通过预处理转移矩阵和逆矩阵的前缀积来计算。注意到这个矩阵和单位矩阵只有 \(4\) 个地方不同，逆矩阵也是这样，因此我们可以 \(\mathcal{O}(\Sigma)\) 计算矩阵乘法。同时注意到初始列向量只有最后一个元素为 \(1\)，其它都为 \(0\)，最后所需结果也同样是列向量的最后一个元素。设转移为 \(P^{-1}_{l-1}P_{r}X\)，那么我们只需要知道 \(P^{-1}_{l-1}\) 的最后一行，和 \(P_{r}\) 的最后一列即可。

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

L. XOR Transformation

题目大意：给你一个长度为 \(n\) 的数列和一个正整数 \(k\)，每次操作后 \(x_{i}\) 变为 \(\bigoplus_{j=0}^{k-1}x_{(i+j)\%n}\)。问 \(t\) 次操作后数列是什么。

题解：容易证明，经过 \(2^{u}\) 次操作后，\(x_{i}\) 会变为 \(\bigoplus_{j=0}^{k-1}x_{(i+j\times2^{u})\%n}\)。因此我们可以把 \(t\) 按 \(2\) 的幂拆分，每次操作则可以用一个前缀异或和来维护。

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