UESTC 第十届 ICPC 趣味程序设计竞赛第三场（正式赛）题解

4/5 Penalty: 09:23:54 Rank 20

罚时爆炸，代码调不对，概率论不会，整段垮掉。

A. 秦皇炒饭

题目大意：将 1 ∼ n 分成最少的组，使得组内元素两两互质。求这个组数。

第一眼就和 Codeforces Round #400 B. Sherlock and his girlfiend 混了，然后 XJB 调都不对，然后自闭了。

最后打了个暴搜，找到了规律，交上去过了……

结论：当 n > 1 时，分成最小组数为 ，当 n = 1 的时候输出 1 次。

证明：因为 2k 与 2k + 1 互质，一定能放到一组，偶数不满足两两互质不能放在一组，编号为 1 的可以放在任意组。

时间复杂度：𝒪(n)，空间复杂度：𝒪(1)

代码见这里。

B. 摩天乐

题目大意：一栋楼的左边和右边都有电梯，上下移动只能坐电梯，求一点到另一点的最小距离。

这题 WA 了 5 遍真是没救了……

只需要做出从左边电梯下楼和从右边电梯下楼的答案，然后输出小的即可。

注意同层情况……

时间复杂度：𝒪(T)，空间复杂度：𝒪(1)。

代码见这里。

C. Akane

题目大意：给定长度为 n 的序列 A，重新排列 A，使有尽可能多的相邻数对，满足 (A_i+A_i + 1) mod  m ≡ 0。

把式子拆开：(A_i mod  m+A_i + 1 mod  m) mod  m ≡ 0

于是，我们对于每一对 (i,j), i + j = m 进行配对即可。注意个数相等和个数等于 0 情况的判断。

时间复杂度：𝒪(n+m)，空间复杂度：𝒪(m)。

代码见这里。

D. 强哥打电话

题目大意：两个人会在一些时间段内打电话，另一个人给这两个中的一个打电话，他从一个时刻开始打，每次打会保持一段时间，如果没打通他会在挂断之后的一段时间后再打，求什么时候能打通。

把时间转化成秒数做，然后暴力……

时间复杂度：𝒪(Tn)，其中 T = 86400，空间复杂度：𝒪(T)。

代码见这里。

E. 永远的X日之都—暴击猫

题目大意：打出暴击的概率是 p，无 buff 加成的普通暴击伤害倍率是 k，一层 buff 提供的暴击伤害倍率提高 a，buff 最多叠加层数 n。求攻击无限次，装备与不装备该装备的总期望伤害之比。

不会概率论直接自闭了。

其实可以取攻击次数为 10⁷ 等等大数，然后计算。

分析如下：

设 f_i 为无限次攻击后，某一次攻击时 buff 有 i 层的概率。那么：

对于 f₀，因为无论有多少层 buff，一旦暴击 buff 都清零。对于 f₁，是由 buff 为 0 层的状态再加上上一次不是得来。

f_n 不能由这个式子计算。因为 buff 的上限是 n，此时再不暴击 buff 层数也不会增加。

可以列方程：

(f_n − 1+f_n) × (1−p) = f_n

解得 f_n = (1−p)ⁿ。

所以一次攻击的期望计算方式是：

可得答案为 。

时间复杂度：𝒪(n)，空间复杂度：𝒪(1)。

代码见这里。