0%

ACM/ICPC EC-Final 2015 简单题解

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了。

Business Cycle

Tags: 杂题

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

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

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

Suffixes and Palindromes

Tags: 字符串 贪心 图论(伪)

将后缀排序和 Manacher 算法同时考虑,根据输入给的信息可以得到$A_i$和$A_j$的关系,是
$$A_i \geq A_j$$或者$$A_i > A_j$$
根据限制条件进行贪心或者差分约束。

Change

Tags: 搜索 暴力

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

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

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

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\}$$

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]$。

Legacy of Void

Tags: 动态规划 树分治

看心情后面补(挖坑)。。。

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,然后转移就好了。

Champions League

Tags: 动态规划

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

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

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

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$从大到小排序,贪心放在左边或者右边的位置。

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)$。

Multiplication Table

Tags: 数学

如果没有数字,答案是 Yes

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

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

November 11th

Tags: 杂题

对于每一行单独处理。

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

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