HBC20336[SDOI2010]外星千足虫题解

水水月牙 算法基础篇 58 0
题库丰富多样,涵盖各个领域,全网最全C++题库,让您在练习中不断成长!
虽然从外观难以区分二者,但通过统计足的数目,科学家们就能根据奇偶性判断出千足虫所属的星球, 作为J国派去NASA的秘密间谍,你希望参加这次研究活动以掌握进一步的情报,而NASA选拔的研究人员都是最优秀的科学家,于是NASA局长Charles Bolden出了一道难题来检测你的实力: 现在你面前摆有1…

公元2089年6月4日,在经历了17年零3个月的漫长旅行后,“格纳格鲁一号”载人火箭返回舱终于安全着陆。此枚火箭由美国国家航空航天局(NASA)研制发射,行经火星、金星、土卫六、木卫二、谷神星、“张衡星”等23颗太阳系星球,并最终在小行星“杰森星”探寻到了地外生命。宇航员在“杰森星”地表岩层下45.70米位置发现一批珍贵的活体生命样本,并将其带回检测。在带回的活体样本中,最吸引人的当属这些来自外星的千足虫了。这些虫子身躯纤长,身体分为若干节。受到触碰时,会将身体卷曲成圆环形,间隔一段时间后才会复原活动。 有趣的还不止如此。研究人员发现,这些虫子的足并不像地球千足虫成对出现、总共偶数条——它们每节身体下方都有着不定数量的足,但足的总数一定是奇数条!虽然从外观难以区分二者,但通过统计足的数目,科学家们就能根据奇偶性判断出千足虫所属的星球。 作为J国派去NASA的秘密间谍,你希望参加这次研究活动以掌握进一步的情报,而NASA选拔的研究人员都是最优秀的科学家。于是NASA局长Charles Bolden出了一道难题来检测你的实力: 现在你面前摆有1…N编号的N只千足虫,你的任务是鉴定每只虫子所属的星球,但不允许亲自去数它们的足。Charles每次会在这N只千足虫中选定若干只放入“昆虫点足机”(the Insect Feet Counter, IFC)中,“点足机”会自动统计出其内所有昆虫足数之和。Charles会将这个和数mod 2的结果反馈给你,同时告诉你一开始放入机器中的是哪几只虫子。他的这种统计操作总共进行M次,而你应当尽早得出鉴定结果。 假如在第K次统计结束后,现有数据就足以确定每只虫子的身份,你就还应将这个K反馈给Charles,此时若K<M,则表明那后M-K次统计并非必须的。 如果根据所有M次统计数据还是无法确定每只虫子身份,你也要跟Charles讲明:就目前数据会存在多个解。

HBC20336[SDOI2010]外星千足虫题解
-第1张图片-东莞河马信息技术
(图片来源网络,侵删)

标签: HBC20336[SDOI2010]外星千足虫题解