ACM-ICPC EC-Final 2015 简单题解

本篇简单描述一下 ACM/ICPC EC-Final 2015 的题解（非官方）。

A. Boxes and Balls

Tags: 数学

满足条件的球的数量一定是某个整数 $m$ 对应的 $\frac{m(m+1)}{2}$ ，所以我们要找到最大的值，使得

$$\frac{m(m+1)}{2} \leq N$$

第一种方法是直接解方程，直接解出以下方程的根

$$\frac{m(m+1)}{2} = N$$

然后在合适的精度范围内进行调整，得到正确的 $m$ 。

另外一种方法是直接二分，找到最大满足条件的 $m$ ，但是要注意二分检查的过程，不要超 long long 了。

B. Business Cycle

Tags: 杂题

二分答案，然后首先计算一圈的和的增量，如果增量是小于等于 $0$ 的，直接模拟即可。

如果和增量大于 $0$ ，模拟前两圈，然后计算循环节，然后检查最后一圈的答案。

细节比较多，需要仔细考虑。

C. Suffixes and Palindromes

Tags: 字符串 贪心 图论（伪）

将后缀排序和 Manacher 算法同时考虑，根据输入给的信息可以得到 $A_i$ 和 $A_j$ 的关系，是

$$A_i \geq A_j$$

或者

$$A_i > A_j$$

根据限制条件进行贪心或者差分约束。

D. Change

Tags: 搜索 暴力

这题网上大家表示很多人没注意到可以兑换多次（雾）。

对于每一个输入对 $(A, B)$ ，你只要兑换一次（ $0.01$ ）或者两次（ $0.02$ ）就可以得到想要的钱。

用搜索或者 DP 去检查有没有可能不通过 $B$ 或者任何和为 $B$ 的组合得到 $A - 0.01$ ，如果没有，说明 $B$ 是必需的，否则 $A$ 兑换 $B$ 就需要两次。

E. Colorful Floor

Tags: 组合数学

我们定义集合 $X$ 的环基 $C_n$ ，颜色的集合是 $K$ ，那么有

$$\left|K^X/C_n\right| = \frac{1}{n}\sum_{i \mid n}\phi(i)\left|K\right|^{n/i}$$

接下来，我们把集合从 $X$ 扩展到 $X \times Y$ ，那么有

$$\left|K^{X \times Y}/C_n \times C_m\right| = \frac{1}{nm}\sum_{i \mid n}\phi(i)\phi(j)\left|K\right|^{\frac{nm}{lcm(i, j)}}$$

我们考虑一个群 $G$ 的等价类，当一个等价类在一个置换 $p$ 下，满足 $\bar{x} \in K^X/G$ 时，我们有

$$p(\bar{x}) = \bar{x}$$

回忆下 Burnside 引理，

$$\left|K^X/G\right| = \frac{1}{|G|}\sum_{g \in G}\#\left\{x \in K^X \mid xg = x\right\}$$

扩展成我们二维的情况，就是：

$$\#\left\{\bar{x} \in K^X/G \mid p(\bar{x}) = \bar{x}\right\} = \frac{1}{|G|}\sum_{g \in G}\#\left\{x \in K^X \mid xg = px\right\}$$

我们假定 $g = (g_1 g_2 \cdots g_k)(\cdots)\cdots(\cdots)$ ， $x = (c_1 c_2 \cdots c_k)(\cdots)\cdots(\cdots)$ ，根据条件

$$xg = px$$

我们有

$$p(c_1) = c_2, p(c_2) = c_3, \cdots, p(c_k) = c_1$$

对于任意的在环里的颜色 $c$ 我们有 $p^k(c) = c$ 。

所以我们的答案是

$$\frac{1}{nm}\sum_{\substack{i \mid n \ j \mid m}}\phi(i)\phi(j)K(i, j)^{\frac{nm}{lcm(i, j)}}$$

其中

$$K(i, j) = \#\left\{x \in K \mid p^{lcm(i, j)}(c) = c\right\}$$

F. Hungry Game of Ants

Tags: 动态规划

我们考虑将蚂蚁按开始的方向分类，我们会发现，如果一个蚂蚁是向左走，那么它左边一整段向右走的都会被它吃掉，然后可以得到一个区间的和重量的蚂蚁，接下来，我们就考虑，再左边的那一整段的和，如果小于这一段的和，就会被这一整段吃掉。

我们直接定义状态 $dp[i]$ 表示考虑到第 $i$ 只蚂蚁，那么，对于 $i>k$ 的情况，我们需要它们被左边的吃掉，所以有

$$dp[i] = \sum_{\substack{j \\\ j(j+1) \geq i(i+1)/2}} dp[j]$$

对于 $i=k$ 的情况，由于我们是从左向右递推的，所以我们要求第 $k$ 只蚂蚁可以吃掉左边来的蚂蚁，所以有

$$dp[i] = \sum_{\substack{j \\\ j(j+1) < i(i+1)/2}} dp[j]$$

对于 $i<k$ 的情况，我们不需要考虑任何的条件，所以有

$$dp[i] = 2^i$$

最后的答案是 $dp[n]$ 。

G. Legacy of Void

Tags: 动态规划 树分治

看心情后面补（挖坑）。。。

H. Open Face Chinese Poker

Tags： 动态规划 模拟

我们定义状态 $dp[mask][i][j]$ 表示使用了 $mask$ 这些卡（这是一个二进制的 orbits），前三张卡的 rank 是 $i$ （我们可以定义 High Card 的值是 $0$ ，没有分数的值是 $1$ ，剩下的有分数的从 $2$ 递增，总共有 $24$ 种情况），中间 5 张卡的 rank 是 $j$ （除了没分数以为，剩下的递增，总共有 $8$ 种情况）。

然后我们可以用枚举处理出 $\binom{14}{5}$ 种 rank，然后转移就好了。

I. Champions League

Tags: 动态规划

直接将 $32$ 个国家做 orbits 定义状态 $dp[mask]$ 然后按国家进行 dp，用 hash 和 BFS 做记忆化和扩展。

比较重要的一点是，整个 DP 的过程是针对国家的，每一个 level 的队伍数量是固定的。

虽然状态看上去有 $2^{32}$ ，实际上的状态数量是 $\binom{8}{4}^4$ 。

J. Dome and Steles

Tags: 贪心

对于每个石碑，它可以放的最小的半径可以计算出来，是

$$r_i = \sqrt{\frac{max(a_i, b_i) ^ 2}{4} + min(a_i, b_j) ^ 2}$$

二分答案，对于每一个石碑我们可以得到它可以放的位置，比如说是区间 $[-p_i, p_i]$ ，其中 $p_i = \sqrt{R^2 - r_i^2}$ 。

然后我们按 $p_i$ 从大到小排序，贪心放在左边或者右边的位置。

K. Convex Polyhedron

Tags: 三维几何

首先，我们可以求出点集所表示的三维凸包对应的所有面，由于 $n \leq 50$ ，所以我们可以在 $O(n^4)$ 时间内得到。

然后，我们通过 $O(n^3)$ 枚举三个面，可以检查这三个面划分的 $8$ 个子空间（可以通过 $2^3$ 枚举法方向向量得到空间的指示向量），我们可以知道面 $C_1$ ， $C_2$ ， $\cdots$ ， $C_k$ 是通过这个子空间指示向量正面看，可以看见的，那么从这个方向看到的最大面积是

$$\sum^{k}_{i = 1}{S_i \cdot \vec{n_i}}$$

其中 $S_i$ 是面 $C_i$ 的面积， $\vec{n_i}$ 是这个面的单位法向量。

得到的向量的长度之中最大的就是答案。

总体复杂度 $O(n^4)$ 。

L. Multiplication Table

Tags: 数学

如果没有数字，答案是 Yes 。

如果只有一个数字，我们枚举这个数字的组合 $X \times Y$ ，然后看这个 table 能不能被包含在乘法表中。

如果有多个数字，那么我们可以通过解方程的方法唯一确定 table 的位置，然后检查是否满足。

M. November 11th

Tags: 杂题

对于每一行单独处理。

最大值是两个人隔着坐，如果有一段连续的区间长度是 $L$ ，那么最大值是 $\left\lfloor\frac{L}{2}\right\rfloor$ 。

最小值是一个人可以占连续的三个位置，那么最小值就是 $\left\lceil\frac{L}{3}\right\rceil$ 。