CCPC2016 Hangzhou solutions

发表于 10月 30日, 2016 分类于 acm-icpc-solutions

本篇简单描述一下 CCPC 2016 杭州赛区的题解（非官方）。

ArcSoft’s Office Rearrangement

Tags: 数学

我们令每一块的长度是 $y$ ，则有

y = \frac{\sum_{i = 1}^{n} a_i}{K}

假设我们有 $\sum a$ 个人站成一排，那么他们一定是在 $p \mod y = 0$ 的位置 $p$ 上被分开，而对于 $p \mod y \neq 0$ 的位置，一定是合并的。对于每一个块 $j$ ，我们算出前缀和

s = \sum_{i=1}^{j} a_i \mod y

然后呢，对于这一块前面的不被整除的部分要合并到前面一块去，中间完整整除的一些块就分成，剩下的最后多余出来的和后面合并就可以了。

总体复杂度： $O(n)$

Bomb

Tags: 图论 , 几何

建一个有向图，如果 $d(u, v) \leq r_u$ 的话，就从 $u$ 向 $v$ 连条边。连完全部的边之后求出图的所有强连通分量，如果一个连通分量是有入边的，那么就说明这个分量中的所有点都是不需要点燃的（可以由入边的分量中任意一个爆炸来点燃它们），所以最后的答案就是对于每个入度为 $0$ 的分量中的最小代价点求和。

总体复杂度： $O(n^2)$

Car

Tags: 贪心

由于速度是不断变大的，所以最后一段的时间为 $1$ 的时候是最优的，对于相邻的两段，我们有

v_i \leq v_{i + 1}

稍稍做个转化，则变成了

\frac{l_i}{t_i} \leq \frac{l_{i + 1}}{t_{i + 1}}

然后做计算就可以了。

复杂度： $O(n)$

Difference

Tags: meet in middle

首先，我们有 $11 \times 9^9 < 10^{10}$ ，我们可以得到 $y$ 的范围是 $y < 10^{10}$ 。我们假设 $y = a \times 10^5 + b$ ，我们有

f(y, K) = f(a, K) + f(b, K)]

做个简单的转化

f(y, K) - y = f(a, K) - 10^5 \times a + f(b, K) - b

我们在 $a \in [0, 10^5)$ 范围内枚举 $f(a, K) - 10^5 \times a$ 的值，然后把它们扔进一个 hash 表里去，然后枚举 $b \in [0, 10^5)$ 计算 $x - (f(b, K) - b)$ 的值，然后去 hash 表里查下看看它们在不在就可以了。

总体复杂度： $O(5 \times 10^5)$

Equation

Tags: 分类讨论 , 搜索

把这些等式分成三个大类

形如 $1 + x = x + 1$ , 这里 $x \geq 1$ ， $x \leq 8$ , 总共有 $8$ 种不同的等式
形如 $x + x = 2 \cdot x$ , 这里 $x \geq 2$ ， $x \leq 4$ , 总共有 $3$ 种不同的等式
形如 $x + y = z$ , 这里 $x \neq 1$ ， $x < y$ , 总共有 $9$ 种不同的等式

对于第二类的每一种等式，我们有两种选择方法，不选这个等式，或者选了这个等式。而对于第三类的每一种等式，我们有三种选择，要么都不选，要么选了其中一种，要么两种都选了。对于第一类，我们可以暴力贪心计算出在选了第二类和第三类之后还可以最多构成多少种第一类的等式。

对于实现，可以搜索第二类和第三类，贪心第一类，或者状压之类的？

总体复杂度： $O(3^9 \times 2^3 \times 9)$

Four Operations

Tags: 暴力 , 表达式求值

假设这个式子可以写成

y = a + b - c \times d\ /\ e

对于式子中的后半部分 $c \times d\ /\ e$ , $c$ 和 $d$ 应该只保留一位，让最后的答案最小。而对于 $e$ ，它最多只会有两位，这是因为 $c \times d < 100$ 并且，如果你用了三位让后半部分从一个一位数变成了 $0$ ，还不如省下那一位让前半部分尽量大。

对于前半部分， $a$ 和 $b$ 一定是一个一位数加一个多位数。所以我们只要枚举加号和除号的位置就可以定下来最后式子长什么样了。

总体复杂度： $O(2 \times 2 \times n)$

Game of Eliminate

Tags: 动态规划

我们设 $a_i$ 为第 $i$ 列的最高的 * 的高度，注意这里我们从底下开始， $1$ 开始标高度。定义状态

dp[i][j]

表示我们已经把第 $i - 1$ 列和它之前的全部 * 部分消完，而第 $i$ 列的没有消去的高度还有 $j$ 的状态的最小开销，那么有状态转移方程

dp[i + 1][\max(0, a_i - k)] = \min(dp[i][j] + \frac{j + k}{3})

这里 $2 \times u + v = j$ 且 $2 \times v + u = k$

转化一下

dp[i + 1][a_i - k] = \min(dp[i][j] + (j + k)\ /\ 3)

3 \times dp[i + 1][a_i - k] + (a_i - k) = 3 \times dp[i][j] + j + a_i

边界限制： $(j + k) \mod 3 = 0$ 且 $\frac{j}{2} \leq k \leq 2 \times j$

用单调队列大概可以优化一波。

总体复杂度： $O(n \times m)$

Hazy String

Tags: 动态规划 , 矩阵

由于字符串不能包含超过 $1$ 长度的回文串，那么对于所有长度为 $2$ 和 $3$ 的子串，它们一定不是回文，而且这是个充要条件。那么对于一个位置 $p$ 的字符，它的选择只和 $p + k, -2 \leq k \leq 2$ 位置上的字符有关。

定义 $m$ 是出现过的字符的数量，将它们标号为 $0$ 到 $m - 1$ 。定义状态

dp[i][j]

表示我们现在在考虑位置 $p_i$ 并且 $p_i - 1$ 上的字符是 $j$ ，这里 $j \in [0, m]$ ， $m$ 表示那些没出现过的字符，可以统一考虑。

对于两个位置之间的部分，假设我们在考虑一个子串

j,\ v_i,\ \cdots,\ x,\ y

由于每一个位置上的字符只和它的前两位有关系，我们定义一个状态

w(a, b)

表示 $j,\ v_i$ 和 $x,\ y$ 的关系，其中 $a,\ b \in [0, 2]$ ， $a$ 表示 $j$ 和 $x$ 的关系， $b$ 表示 $v_i$ 和 $y$ 的关系。 $a=0$ 表示 $x=j$ ， $a=1$ 表示 $x=v_i$ ，而 $a=2$ 表示 $x$ 和前面两个都不一样， $b$ 也是对应的表示状态。

我们可以构建出一个矩阵来做 $p \cdot i$ 到 $p\cdot i + 1$ 之间的转移，而 $dp[i+1][k]$ 的值等价于 $x=k$ 且 $y = v_{i+1}$ 的时候的值。

总体复杂度： $O(n \times m + 7^3 \times n \lg L)$

Inequality

Tags: 数学

我们定义函数 $b(i) = \min \sum_{k=1}^{i} x_k$ ，通过观察可以发现，它是一个关于 $x_i$ 值的分段函数，而且每一段的值可以写成如下形式

u \times x + \frac{v}{x} + w

函数 $b(i)$ 只有一个全局极小值，可以递推出 $b(i)$ 关于 $x_i$ 的每一段分段函数长什么样子，然后算出全局的极小值。

总体复杂度： $O(n^2)$

Just a Math Problem

Tags: 数论

定义 $m = p_1^{r_1} \times p_2^{r_2} \times \cdots \times p_k^{r_k}$ 且 $f(m) = k$

$g(m)$ 可以成满足 $(x, y) = 1$ 和 $x \times y = m$ 的数对 $x$ , $y$ 的数量。那么 $\sum_{i}^{n} g(i)$ 就是满足 $(x, y) = 1$ 且 $x \times y \leq n$ 的数对的数量。

我们假设 $x<y$ ，我们可以枚举 $x$ ，容斥出 $y$ 的数量（假设是 $Y$ ）， $y$ 满足条件 $(x, y) = 1$ 且 $1 \leq y \leq n$ 。对于枚举的 $x$ ，答案是 $Y - \phi(x)$ 。

总体复杂度： $O(\sqrt{n} \lg n)$

Kingdom of Obsession

Tags: 匹配 , 数论

我们定义 $b_i = s + i$ ，如果 $b_i \leq n$ ，那么最优的做法一定是把它放在原来自己的位置上，这里可以反证一下，如果 $b_i$ 放在了 $p$ 上，而且 $p < b_i$ ，我们一定可以把 $b_i$ 和放在 $p$ 上的另外一个比 $b_i$ 大的数交换。

对于 $b_i > n$ 的情况，如果这样的 $b_i$ 中素数超过了 $1$ 个，那么一定是无解的，因为素数只能放在自己的位置或者 $1$ 上，而对于不超过一个素数的情况，这样的 $b_i$ 的数量会非常少（姑且认为是 $100$ 个最多了？），对于这些数，假设有 $m$ 个的话，我们就让它们和 $1$ 到 $m$ 这些位置做匹配就可以了。

另外，给个贪心的反例： $n = 5, s = 11$ 。

总体复杂度： $O(m^3)$