2019年USSTSIW ICPC & CCPC暑期集训队练习赛8-Problems1

【问题A. Wiki with Horses】 这是一道与优化策略和贪心算法相关的编程问题。问题背景设定在Wiki和她的马儿们的故事中。Wiki需要将n匹马从玉米田转移到草地，每匹马有不同的牵引时间和每分钟吃玉米的数量。目标是找到最优的牵引顺序，使得玉米损失最小。 解决这个问题的关键在于贪心策略。每匹马的损失是它在玉米田中停留的时间乘以每分钟吃掉的玉米量。因此，应该优先牵引那些牵引时间短且吃玉米多的马，这样可以迅速减少马儿在玉米田中的数量，从而降低总的损失。在实际实现时，可以构建一个结构（如优先队列）来存储马的信息，按照损失速率（牵引时间除以每分钟吃掉的玉米量）排序，每次都处理损失速率最大的马。 算法步骤如下： 1. 读取马的数量n和每匹马的牵引时间ti和吃玉米量ai。 2. 初始化一个结构（如优先队列）并按照损失速率排序。 3. 遍历队列，每次取出损失速率最大的马，将其从玉米田转移到草地，更新总的损失。 4. 重复步骤3，直到所有马都被转移。 5. 输出最少损失的玉米数量。 【问题B. Wiki with Card Game】 这是一个概率论和数学期望的问题。Wiki需要在不断添加相同名片的情况下，计算收集完整套名片的平均抽取次数。当只有n张不同的名片时，每次抽取后，期望的剩余抽取次数会根据当前已有的名片数量变化。这实际上是一个几何分布的期望问题。 解决方案涉及计算几何分布的期望，公式为E(X) = 1/p，其中X是随机变量（抽取次数），p是单次抽取成功（即抽到新名片）的概率。在每次抽取后，成功概率会因为已知名片的增加而下降。具体计算时，需要累加每次新增名片时的期望值。 算法步骤如下： 1. 读取测试案例数T和每组案例的名片数量n。 2. 对于每个案例，初始时成功的概率为1/n，每次抽取后成功概率会变为(n-1)/(2n-1)。 3. 计算并累加每个阶段的期望值E(X) = 1/p，直到达到n个不同的名片。 4. 输出每个案例的期望抽取次数，保留三位小数。 【问题C. Wiki with A|||B】 这是一个涉及位操作的计算问题。题目要求计算两个整数A和B进行按位或操作(A|||B)，但这里的操作有特殊的定义：每次将B除以2并向下取整，直到B为0。由于常规的位操作可能导致位数不一致，这里规定如果位数不同，则将位数多的一方高位截断。 解决此问题，首先需要将A和B转换为二进制表示，然后按照题目描述的规则进行按位或操作。由于A和B可能非常大，结果也可能超出常规整数范围，所以需要在二进制操作后将结果转换回十进制，并对998244353取模。 算法步骤如下： 1. 读取A和B的二进制长度n和m，以及它们的二进制表示。 2. 初始化answer为0，进行按位或操作，直到B为0。 3. 在每次操作中，将answer加上A和B进行按位或的结果，并将B除以2并向下取整。 4. 当B为0时，将answer转换为十进制并对其取模998244353。 5. 输出取模后的结果。 这三道问题涵盖了优化策略、概率论和位操作等多个IT领域的知识点，对于提升算法设计和问题解决能力有很大帮助。