Contest Info

date: 2017.07.29 12:00-17:00

practice link

Solutions

A. Hyperspace

题目大意：\(k\) 维空间中，每次出现一个点，或者删除一个点。问每次操作之后曼哈顿距离最远两点的距离。

题解：设最远的两点为 \(A, B\)，那么我们要求的便是 \(\sum_{i = 1}^k \mid A.x_i - B.x_i \mid\)。我们将绝对值展开，不妨为 \((A.x_1 + A.x_2 - A.x_3 + \cdots) - (B.x_1 + B.x_2 - B.x_3 + \cdots)\)。注意到前后括号中的形式是一样的。所以我们只需要用 \(2^{k-1}\) 个 multiset 来维护 \(x_1 \pm x_2 \pm \cdots \pm x_k\) 即可，每个 multiset 中取最大值减去最小值。所有的这些结果的最大值就是答案了。

B. Building Fence

题目大意：给你平面上的互不相交的圆和三角形，求覆盖它们的连通图形的最小周长。

题解：

法一：求出所有圆两两的公切线的切点、三角形的所有顶点和所有圆的切线的切点、三角形的所有顶点的凸包。凸包可能有些边在圆内，那么这个圆就会有一部分在凸包的外面，如果圆心在凸包的外面，则需要加上一段优弧，否则要加上一段劣弧。

法二：这题精度要求比较低，每个圆上取 \(2000\) 个点直接做也能过。

C. Finding string

题目大意：给你一个压缩之后的母串，和一个子串。求子串在母串中出现的次数。每个压缩是一个串加一个数字，表示这个串的出现次数。压缩不会嵌套。

题解：我们将压缩的前后都展开直到分别大于子串的长度。如果不够的话直接全部展开，否则中间还剩余一个更少的压缩，设还出现 \(t\) 次。这样发生在压缩前后边界的匹配，就能直接计算得到。如果发生了一次在中间剩余的压缩中的匹配，那么显然全部展开之后一共会发生 \(t\) 次。我们直接跑一次 kmp 算法即可。

D. Mutiples on a circle

题目大意：给你一个圆环，每个位置有一个整数。问你有多少种方案选择一段使得，按顺序排列成的大整数是 \(K\) 的倍数。

题解：动态规划。将数列翻倍后，f[i][j] 表示以位置 \(i\) 为结尾的有多少段大整数模 \(K\) 余 \(j\)。注意长度大于等于 \(n+1\) 的段是不符合要求的。于是我们预处理出 g[i] 表示以位置 \(i\) 为结尾的长度恰为 \(n+1\) 的大整数模 \(K\) 的余数。每次转移之后 f[i][g[i]] -= 1 即可。这道题卡空间，要用循环数组。

E. Cube number on a tree

题目大意：给出一棵 \(n\) 个节点的树，第 \(i\) 个节点上有一个数 \(P_i\) ，\(0 \leq P_i \leq 10^{15}\) ，给出 \(k \leq 40\) 个不同的质数，所有的 \(P_i\) 都能被可以表示为这 \(k\) 个质数的某个幂次的乘积。现在问这棵树上有多少个不同的路径满足，这条路径上的所有点的 \(P_i\) 之积是一个正的立方数。

题解：因为所有的数都能用这 \(k\) 个质数表示出来，而是否能表示为立方数只与每种质数的指数是否能被 \(3\) 整除有关，可以将状态表示为一个三进制数，然后就可以树分治了。注意需要特殊处理只有一个点的路径和包含有零的位置的路径。

F. Backup Plan

题目大意：有 \(n\) 台服务器和 \(m\) 个数据库，每个数据库在所有服务器上都有一份拷贝，查询的时候按照一定顺序查找直到找到一台可用的服务器。求一个顺序，使得服务器完好和任意一台服务器坏掉的时候负载均衡，也即 \(|A_i - A_j| \leq 1\)， \(A_i\) 表示使用服务器 \(i\) 的数据库个数。

题解：稍微观察发现只有顺位为 \(1\) 和 \(2\) 的服务器有意义。我们均匀分配第一顺位即可。第二顺位只有在第一顺位坏掉的时候才有意义，我们把坏掉的那台承载的所有数据库平均分给其他服务器即可，优先分给承载数据库较少的服务器。其余顺位随意设置。

G. Present Day, Present Time

题目大意：有 \(n\) 堆石子，第 \(i\) 堆有 \(a_{i}\) 个，然后给你 \(m\) 个整数，第 \(i\) 个整数是 \(b_{i}\) 。两个人轮流取石子，每次操作可以选取一堆石子，取走 \(b_{i}\) 个，可以取任意多次，但只能在选择的这堆中取。无法操作或者取完石子后有某堆石子不能取完（即不能被 \(b_{i}\) 表示）的人输，问先手胜还是后手胜。

题解：我们称能够被 \(b_{i}\) 表示的数为合法状态，否则称为非法状态。若 \(a_{i}\) 中有非法状态，则这堆石子要么不能取，要么能取并且取完后仍然是非法状态，显然这时后手胜。接下来我们用数学归纳法证明合法状态的 \(sg\) 值为它转移到 \(0\) 可取的最大次数：显然有 \(sg(0) = 0\) 。对于一个合法状态 \(n\) ，设这个最大次数为 \(x\) ，显然 \(x\) 存在且有限。由于存在一种方案使得它取 \(x\) 次后剩余 \(0\) 个石子，故对全部 \(0 \leq i < x\) ，我们只要按照上述方案取 \(x-i\) 次石子，剩余石子的 \(sg\) 值就为 \(i\) （证明略，显然）。我们假设 \(n\) 能转移到 \(sg\) 值为 \(x\) 的状态，则显然 \(n\) 可以经由这个状态，取 \(x+1\) 次才取完，与条件矛盾。故 \(sg(n)=x\) 。

由于题目中的 \(a_{i}\) 太大，需要加速 \(sg\) 的计算，易证 \(n \geq min\{b_{i}\}\cdot max\{b_{i}\}\) 时， \(sg(n)=sg(n-min\{b_{i}\})\) ，即可快速计算。

H. Pirate’s Chest

题目大意：有 \(n\) 个箱子，每个箱子可以用编号为 \(a_i\) 的钥匙，或者用编号为 \(b_i\) 的撬棍，或者消耗 \(D_i\) 的生命值打开。一座 \(m\) 层的塔中，每一层是一个 \(20\times 20\) 的矩阵，矩阵中恰有一个入口，和至多两件工具。走过非入口非工具点会消耗相应生命值，第二次走过不再消耗生命值。一层楼的工具是同一种类型，每种编号的工具最多出现一次，每个工具可以使用无限次。问你打开全部的 \(n\) 个箱子并且生命值不为 \(0\)，最少上多少层楼，在此基础上，最少消耗多少生命值。

题解：据说是很显然的网络流最小割模型。显然消耗的生命值，随着楼层变高单调不增，因为楼层变高只是多了一些选择。我们对楼层进行二分，然后网络流验证。

注意到每种钥匙/撬棍可以使用无限次，那么与之相关的代价应该定义在其上，对于宝箱来说，暴力打开的代价实际上可以看作是钥匙与撬棍之间的代价。我们大致可以得出一个 “源 -> 钥匙 -> 撬棍 -> 汇” 的模型，暴力的代价作为钥匙和撬棍之间的边权。每种编号的工具在塔中最多出现一次，同一层至多出现两个相同类型的道具，所以我们也要将楼层作为点，然后在楼层和相应的工具之间连边，边权为取得工具的代价。

取得一个工具的代价，可以直接从起点到它 spfa 求最短路。同时取得两个工具的代价，显然是一个三个点的斯坦纳树问题，我们枚举交界点即可。

综上所述，我们得到了如下的模型：

• 源向有钥匙的楼层连边，有一把钥匙边权为 inf，两把钥匙边权为斯坦纳树求得的费用
• 有撬棍的楼层向汇连边，边权同上
• 有钥匙的楼层，向自己的一把/两把钥匙连边，边权为直接走到该点的费用
• 有撬棍的楼层，从自己的一把/两把撬棍连边，边权同上
• 源点向没有在楼层中出现的钥匙连 inf 的边，没有在楼层中出现的撬棍向汇点连 inf 的边
• 每个箱子，从钥匙 \(a_i\) 对应的节点，向撬棍 \(b_i\) 对应的节点连边，边权为 \(D_i\)

那么一个可行的方案便对应一个割了。

I. Trip Advisor

题目大意：给出一个 \(n\) 个点 \(m\) 条边的连通无向图，图中每一个点最多属于一个环。现在有 \(q\) 次询问，每次询问图中是否存在一条从点 \(u\) 到点 \(v\) 并且经过点 \(x\) 的路径，并且不允许路径中任意一个点经过了两次。

题解：首先用 \(Tarjan\) 算法将图中所有的 \(bcc\) 缩点，这样就得到了一个新的图，且它是一棵树，我们在这棵树的每条边上记录这条边在原图中所连接的两个点，然后做一次 \(dfs\) 并记录每个点到它父亲的边的编号。之后对于每个询问我们进行分类讨论：

\(1.\) \(u\)，\(v\)，\(x\) 中存在相同的点：

  \(1.1.\) \(u\) 和 \(v\) 相同，如果 \(x\) 也和 \(u\) 相同，则存在，否则不存在；

  \(1.2.\) \(u\) 和 \(v\) 不同，\(x\) 和 \(u\) 相同或者 \(x\) 和 \(v\) 相同，存在；

\(2.\) \(u\)，\(v\) 和 \(x\) 中不存在相同的点，但是存在在同一个圈里的点：

  \(2.1.\) \(u\) 和 \(v\) 在同一个环中，若 \(x\) 也在这个环中，则存在，否则，不存在；

  \(2.2.\) \(u\) 和 \(v\) 不在同一个环中，\(x\) 与其中一个点在同一个环中，我们不失一般性地设 \(x\) 和 \(u\) 在同一个环中。

  则我们需要判断从 \(u\) 所在的环走到 \(v\) 所在的环时从哪一个点走出这个环的，设这个点为 \(p\)， 若 \(p=u\) ，则不存在，否则就存在。

  于是我们继续分类讨论 \(u\) 所在的环 \(fu\) 和 \(v\) 所在的环 \(fv\) 的位置关系：

    \(2.2.1.\) \(lca(fu,fv)=fu\)，如图所示，则我们需要通过倍增法找到 \(fv\) 到 \(fu\) 的路径上与 \(fu\) 直接相连的点，然后查询它到父亲的边得到 \(p\)；

    \(2.2.2.\) \(lca(fu,fv)=fv\)，如图所示，则我们直接查询 \(fu\) 到父亲的边得到 \(p\)；

    \(2.2.3.\) \(lca(fu,fv) \not= fu\) 且 \(lca(fu,fv) \not= fv\)，如图所示，则我们直接查询 \(fu\) 到父亲的边得到 \(p\).

\(3.\) \(u\)，\(v\) 和 \(x\) 中不存在同一个环中的点。

  则先判断 \(x\) 所在环 \(fx\) 是否存在于 \(u\) 所在环 \(fu\) 和 \(v\) 所在环 \(fv\) 在树上的路径之中，可以直接通过 \([dis(fu,fv)=dis(fu,fx)+dis(fv,fx)]\) 来判断，如果为真，则 \(fx\) 在 \(fu\) 到 \(fv\) 的路径上，否则就不存在。

  如果 \(fx\) 存在于 \(fu\) 到 \(fv\) 的路径，我们再去找 \(fx\) 走到 \(fu\) 的路径和 \(fx\) 走到 \(fv\) 的路径是从哪个点走出 \(fx\) 的，分别设其为 \(p_1\) 和 \(p_2\) ，则当且仅当 \(p_1 \not= p_2\) 或者 \(p_1 = p_2 = x\) 时存在要求的路径，否则不存在。

  我们再分类讨论 \(fu\)，\(fv\) 和 \(fx\) 之间的位置关系求解 \(p_1\) 和 \(p_2\)：

   \(3.1.\) \(lca(fu,fv)=fx\) ，如图所示，则通过倍增法分别找到 \(fu\) 和 \(fv\) 到 \(fx\) 的路径中与 \(fx\) 直接相连的点，查询它到父亲的边来求得 \(p_1\) 和 \(p_2\)；

   \(3.2.\) \(lca(fu,fv)=fu\) 或者 \(lca(fu,fv)=fv\)，我们不失一般性地设 \(lca(fu,fv)=fu\) ，如图所示，则我们查询 \(fx\) 到父亲的边求得 \(p_1\)，通过倍增法找到 \(fv\) 到 \(fx\) 的路径上与 \(fx\) 直接相连的点，查询它到父亲的边求得 \(p_2\)；

   \(3.3.\) \(lca(fu,fv) \not= fu\) 且 \(lca(fu,fv) \not= fv\) 且 \(lca(fu,fv) \not= fx\)，我们设与 \(fx\) 在 \(lca(fu,fv)\) 同一侧的点为 \(fu\) ，如图所示，我们通过倍增法找到 \(fu\) 到 \(fx\) 的路径上与 \(fx\) 直接相连的点，查询它到父亲的边求得 \(p_1\)，直接查询 \(fx\) 到父亲的边求得 \(p_2\).

J. GCD of Sequence

题目大意：给你一个长度为 \(n\) 的数列 \(a_{i}\) ，对全部 \(1 \leq d \leq m\) ，求满足以下条件的长度为 \(n\) 的数列 \(b_{i}\) 的个数：

• \(1 \leq b_{i} \leq m\)
• \(gcd(b_{1}, \cdots, b_{n}) = d\)
• 恰好有 \(k\) 个 \(b_{i}\) 满足 \(a_{i}\not=b_{i}\)

题解：设 \(f(d)\) 表示 \(\sum_{d|x,x \leq m}ans(x)\) ，\(a\) 中有 \(cnt_{d}\) 个数被 \(d\) 整除，则显然有 \[ f(d)=\left\{ \begin{aligned} &C_{cnt_{d}}^{n-k}\cdot(\lfloor\frac{m}{d}\rfloor-1)^{cnt_{d}-(n-k)}\cdot(\lfloor\frac{m}{d}\rfloor)^{k}&(cnt_{d}\ge n - k)\\ &0&(cnt_{d} < n-k)\\ \end{aligned}\\ \right. \]

又根据容斥原理有 \(ans(d)=\sum_{d|x,x \le m}f(x)\mu(\frac{x}{d})\) 。