NOIP2019模拟赛：石子、内存与子集问题解法

"这份资源是一份关于2019年正睿NOIP模拟赛Contest2的题解，包含了三道题目——石子（T1）、内存（T2）和子集（T3）。每个题目都有相应的输入输出限制、时间限制和内存限制，并且都是传统型题目。" 1. **石子（T1）** 题目要求计算在一系列石子堆中，按照一定的规则取石子后，期望剩余石子的线性关系。解答的关键在于理解每堆石子被取走的概率只与该堆和第一堆有关，与其他堆无关。因此，可以独立计算每一对石子堆的概率，然后求和。公式为 E(t)=P2+P3+...+Pn+1，其中 Pi 是第 i 堆石子在第1堆之前被取走的概率，计算方法为 ai/(a1+ai)。最后的答案是所有这些概率的和，时间复杂度为 Θ(n)。 2. **内存（T2）** 这个问题涉及内存压缩的问题，寻找一个最优的内存分配策略。对于每个可能的压缩值 x，可以通过二分贪心算法在 Θ(nlog2n) 的时间复杂度内计算出最优解 F(x)。暴力方法会得到 Θ(nmlog2n) 的复杂度，这足以通过前两个子任务。优化策略是，以随机顺序遍历所有 x，期望需要计算的次数是 Θ(lnn)。因此，可以针对这些 x 使用二分贪心法，总时间复杂度为 Θ(nm+nlnnlog2n)。 3. **子集（T3）** 本题要求找出所有使得它们的最小公倍数等于 n 的子集。关键在于只选择 n 的约数作为子集的元素。问题可以转化为对 n 的质因数分解，然后利用容斥原理来确定不同质因数的幂次组合。原始的解决方案有 Θ(4ω(n)ω(n)) 的时间复杂度，其中 ω(n) 表示 n 的质因数个数，可以解决前两个子任务。优化方法包括分别枚举每个质因数对应四种情况（0 次方、1 次方、αi 次方和 αi+1 次方），然后计算对应的方案数。 总结来说，这份题解涵盖了概率计算、动态规划和数论算法等计算机科学中的核心概念，适合于提高参赛者在算法竞赛中的解题能力。