2021 MINIEYE杯大学生算法赛题解：区间和与素数策略

在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)。 这两道题目都需要参赛者具备良好的算法设计能力，包括区间和的分析、素数判定、函数优化以及决策策略的制定。解决这类问题时，理解并应用数学性质和数据结构优化是至关重要的。参赛者需灵活运用二分查找、预处理技术，以及对凸函数特性的认识，来高效地求解问题。