HBC16430[NOIP2016]蚯蚓题解

冷默言语 算法基础篇 54 0
题库丰富多样,涵盖各个领域,全网最全C++题库,让您在练习中不断成长!
本题中,我们将用符号 clfloor c rfloorc 表示对 c 向下取整,例如:3.0=3.1=3.9=3lfloor 3.0 rfloor = lfloor 3.1 rfloor = lfloor 3.9 rfloor = 33.0=3.1=3.9=3, 蛐蛐国最近蚯蚓成灾了!,ni = 1, 2, ldots , ni=1,2,… 蛐蛐国王希望知道这 m 秒内的战况,具体来说,他希望知道: ·m 秒内,每一秒被切断的蚯蚓被切断前的长度; ·m 秒后,所有蚯蚓的长度, 蛐蛐国王当然知道怎么做啦!但是他想考考你 ……

本题中,我们将用符号 ⌊c⌋lfloor c rfloor⌊c⌋ 表示对 c 向下取整,例如:⌊3.0⌋=⌊3.1⌋=⌊3.9⌋=3lfloor 3.0 rfloor = lfloor 3.1 rfloor = lfloor 3.9 rfloor = 3⌊3.0⌋=⌊3.1⌋=⌊3.9⌋=3。 蛐蛐国最近蚯蚓成灾了!隔壁跳蚤国的跳蚤也拿蚯蚓们没办法,蛐蛐国王只好去请神刀手来帮他们消灭蚯蚓。 蛐蛐国里现在共有 n 只蚯蚓(n 为正整数)。每只蚯蚓拥有长度,我们设第 i 只蚯蚓的长度为 ai(i=1,2,…,ni = 1, 2, ldots , ni=1,2,…,n),并保证所有的长度都是非负整数(即:可能存在长度为 0 的蚯蚓)。 每一秒,神刀手会在所有的蚯蚓中,准确地找到最长的那一只(如有多个则任选一个)将其切成两半。神刀手切开蚯蚓的位置由常数 p(是满足 0 < p < 1 的有理数)决定,设这只蚯蚓长度为 x,神刀手会将其切成两只长度分别为 ⌊px⌋lfloor px rfloor⌊px⌋ 和 x−⌊px⌋x - lfloor px rfloorx−⌊px⌋ 的蚯蚓。特殊地,如果这两个数的其中一个等于 0,则这个长度为 0 的蚯蚓也会被保留。此外,除了刚刚产生的两只新蚯蚓,其余蚯蚓的长度都会增加 q(是一个非负整常数)。 蛐蛐国王知道这样不是长久之计,因为蚯蚓不仅会越来越多,还会越来越长。蛐蛐国王决定求助于一位有着洪荒之力的神秘人物,但是救兵还需要 m 秒才能到来 ……(m 为非负整数) 蛐蛐国王希望知道这 m 秒内的战况。具体来说,他希望知道: ·m 秒内,每一秒被切断的蚯蚓被切断前的长度(有 m 个数); ·m 秒后,所有蚯蚓的长度(有 n + m 个数)。 蛐蛐国王当然知道怎么做啦!但是他想考考你 ……

HBC16430[NOIP2016]蚯蚓题解
-第1张图片-东莞河马信息技术
(图片来源网络,侵删)

标签: HBC16430[NOIP2016]蚯蚓题解