NOIP2019模拟赛：取石子游戏与内存管理

"该资源是一份来自2019年NOIP(National Olympiad in Informatics, 信息学奥赛)模拟赛的竞赛题目合集，包含三道题目：石子(stone)、内存(memory)和子集(subset)。每道题目都有详细的问题陈述、输入输出格式、示例及约束条件。" 1. **石子问题** (T1 - stone) - **问题描述**: 小D正在进行一个取石子的游戏，他有n堆石子，每堆有不同数量的石子。每次他随机选取一颗石子并取走该堆的所有石子。问题在于求解第1堆石子被取走的期望时间。 - **输入格式**: 第一行包含石子堆数n，第二行包含n个整数，表示每堆石子的数量。 - **输出格式**: 输出一个浮点数，表示第1堆石子被取走的期望时间，要求相对误差或绝对误差不超过10^(-6)。 - **样例**: 提供了两个样例输入和输出。 - **子任务分数分配**: 子任务1(20分): n≤20；子任务2(20分): n≤1000；子任务3(30分): 每堆石子数量ai=1；子任务4(30分): 无特殊限制。 - **约束**: 对所有测试数据，1≤n≤10^5，1≤ai≤10^9。 2. **内存问题** (T2 - memory) - **问题陈述**: 小D研究内存存储，有n条信息，每条信息有不同的大小ai。目标是将信息分到k组，每组存入连续的内存区域。 - **详细内容**: 未提供完整的题目细节，但可以推断，问题可能涉及如何最优分配内存来存放这些信息，可能需要考虑内存碎片最小化或内存利用率最大化等问题。 - **输入/输出格式**和**约束**：未给出，可能需要查看题目文件中的详细说明。 3. **子集问题** (T3 - subset) - 题目详细信息未在摘要中给出，但通常这类问题可能涉及到集合论或图论，例如找一个集合的子集满足特定条件，或者计算子集的数量等。 - 输入输出格式、样例和子任务信息同样需要查看题目文件获取完整信息。 这三道题目覆盖了算法设计和计算概率等多个信息学竞赛的关键领域，适合参赛者提升解决问题和编程的能力。解答这些题目时，参赛者需要熟悉动态规划、概率计算、数据结构以及可能的搜索或贪心策略。