2021 MINIEYE杯大学生算法赛题解：区间和与素数策略
需积分: 0 135 浏览量
更新于2024-08-05
收藏 679KB PDF 举报
在2021年的"MINIEYE杯"中国大学生算法设计超级联赛（6）的在线竞赛中，两道问题分别是"YES, Prime Minister"和"Might and Magic"。这些问题涉及了算法设计中的不同技巧和策略。
首先，"YES, Prime Minister"的问题围绕区间和的素性性质展开。题目指出，任何非空区间[l, r]的和可以通过调整l和r使其对应一个正的子区间[l', r']，其和保持不变。关键在于理解区间和的分解特性：当区间的长度(r - l + 1)大于或等于2时，区间和可以被分解为两个因数的乘积，除非这个区间长度不超过2，否则其和不可能是质数。因此，预处理小于2乘以10^7的质数可以用埃拉托斯特尼筛法或线性筛法来完成。对于x≤0的情况，答案取决于找到符合条件的最小质数或2z-1为质数的区间；而对于x>0，直接给出了一些可能的区间。这个问题采用二分查找，时间复杂度为O(Tlog(|x|) + |x|)。
第二题"Might and Magic"关注的是决策制定策略，特别是对角色伤害的计算。目标是在有限的生命值情况下最大化伤害。通过确定敌人剩余的生存轮数t（向上取整H0/Damage），可以将问题分解为枚举t和防御力D0。问题的关键在于分析伤害函数：物理伤害P(x)和魔法伤害M(x)都是下凸函数。总伤害函数F(x)作为这两个函数的和，同样具有下凸性，这意味着最大值将在函数的端点或局部极值点处取得。全加物理的情况下，最优选择是全加A0；全加法术则需要计算特定条件下D(K0)的最大值，其中K0表示分配给法术的点数。这个问题的时间复杂度为O(T)。
这两道题目都需要参赛者具备良好的算法设计能力，包括区间和的分析、素数判定、函数优化以及决策策略的制定。解决这类问题时，理解并应用数学性质和数据结构优化是至关重要的。参赛者需灵活运用二分查找、预处理技术，以及对凸函数特性的认识，来高效地求解问题。
2021“MINIEYE 杯”中国大学生算法设计超级联赛（6）
Online, 2021 年 8 月 5 日, 星期四
Problem Tutorial: “Yes, Prime Minister”
显然 r > 0, r ≥ l，如果 l ≤ 0，此时 [l, r] 区间和 = [−l + 1, r] 的区间和，且 r ≥ −l + 1 > 0。
故对于任意一个区间，都可以找到一个对应的 r ≥ l > 0 的区间与之对应，区间和相同。
对于下式
r
i=l
i =
(l + r)(r − l + 1)
2
当 l > 0 时，若 r − l ≥ 2，则
l+r
2
和
r−l +1
2
之中必有一个是大于 1 的整数。区间和必然能被拆分成两个因数的乘
积。所以这样的满足和为素数的区间长度必然不长于 2。
预处理出比 [2, 2 ×10
7
] 略大范围内的质数，埃氏筛或者线筛均可。
如果 x ≤ 0，则候选答案为：
• 最小的 y(y ≥ 1 − x)，满足 y 是质数，区间为 [−y + 1, y]。
• 最小的 z(z ≥ 2 − x)，满足 2z −1 是质数，区间为 [−z + 2, z]。
如果 x > 0，则候选答案为：
• [x, x]。
• [x, x + 1]。
• [x − 1, x]。
• 最小的 y(y ≥ x)，满足 y 是质数，区间为 [−y + 1, y]。
• 最小的 z(z ≥ x)，满足 2z −1 是质数，区间为 [−z + 2, z]。
二分查找即可，时间复杂度为 O(T log(|x|) + |x|)。
Problem Tutorial: “Might and Magic”
答案等于对手生命无限时所能造成的最大伤害。注意到存活轮数 t = ⌈
H0
Damage
⌉，可以整除分块以 O(
√
H
0
) 复杂度
枚举 t 和所需付出的防御力 D
0
。
接下来有结论，要么全点 A
0
，要么全点 P
0
, K
0
。证明如下：
固定进行物攻和魔攻的次数 a, b(a + b = t)，如果 K
0
不足视为跳过回合，假设物/法加点为 x 点，则：
物伤函数 P (x) =
aC
p
x <= D
1
aC
p
(x − D
1
) x > D
1
是一个下凸函数。
法伤函数 M(x) =
C
m
(x − ⌊
x
2
⌋)⌊
x
2
⌋ 2x <= b
C
m
(x − b)b 2x > b
也是一个下凸函数。
所以总伤函数 F (x) = P (x) + M(N − D
0
− x) 关于物理加点 x 也是一个下凸函数。故最大值必然至少在两端点之
一处可以取到。
全加物理的情况全加 A
0
即可。
全加法术的情况需要对 D(K
0
) = C
m
K
0
(N − D
0
− K
0
) + C
p
(t − K
0
)(0 ≤ K
0
≤ min(t, N − D
0
)) 求一下最值。
时间复杂度 O(T
√
H
0
)
Page 1 of 6
下载后可阅读完整内容，剩余5页未读，立即下载
2022-08-03 上传
2022-08-03 上传
点击了解资源详情
2022-08-03 上传
2022-08-03 上传
2022-08-03 上传
2022-08-03 上传
2021-07-29 上传
点击了解资源详情
