2006年NOIP信息学奥赛提高组复赛C++真题

NOIP 2006复赛试题 (提高组) © 中国计算机学会， 2006 1 第十二届全国青少年信息学奥林匹克 联赛复赛试题 （NOIP2006提高组） 竞赛时间： 2006年11月18日上午8：30—11：30 试题名称 energy budget jsp digital 目录 energy budget jsp digital 输入文件名 energy.in budget.in jsp.in digital.in 输出文件名 energy.out budget.out jsp.out digital.out 试题类型 非交互式程序题 非交互式程序题 非交互式程序题 非交互式程序题 附加文件 无 无 无 无 时限 1秒 1秒 1秒 1秒 关于竞赛中不同语言使用限制的说明 一．关于使用 Pascal语言与编译结果的说明 1．对于Pascal语言的程序，当使用 IDE和fpc编译结果不一致时，以 fpc的编译结果为准。 2．允许使用数学库 (uses math子句)，以及ansistring。但不允许使用编译开关（ 最后测试时 pascal 的范围检查开关默认关闭： {$R-,Q-,S-}），也不支持与优化相 关的选项 。 二．关于C++语言中模板使用的限制说明 1．允许使用的部分 ： 标准容器中的布尔集合，迭代器，串，流。 相关的头文件： <bitset > <iterator > <string > <iostream > 2．禁止使用的部分 ： 序列：vector，list，deque 序列适配器： stack, queue, priority_queue 关联容器： map, multimap, set, multiset 拟容器： valarray 散列容器： hash_map, hash_set, hash_multimap, hash_multiset 所有的标准 库算法 相关头文件： <vector > <list > <deque > <stack > <map > <set > <algorithm > NOIP 2006复赛试题 (提高组) © 中国计算机学会， 2006 2 1．能量项链 (energy.pas/c/cpp) 【问题描述】 在Mars星球上，每个 Mars人都随身佩带着一串能量项链。在项链上有 N颗能量珠。能量珠 是一颗有头标记与尾标记的珠子，这些标记对应着某个正整数。并且，对于相邻的两颗珠子，前一 颗珠子的尾标记一定等于后一颗珠子的头标记。因为只有这样，通过吸盘（吸盘是 Mars人吸收能 量的一种器官）的作用，这 两颗珠子才能聚合成一颗珠子，同时释放出可以被吸盘吸收的能量。如 果前一颗能量珠的头标记为 m，尾标记为 r，后一颗能量珠的头标记为 r，尾标记为 n，则聚合后 释放的能量为nrm （Mars单位），新产生的珠子的头标记为 m，尾标记为 n。 需要时， Mars人就用吸盘夹住相邻的两颗珠子，通过聚合得到能量，直到项链上只剩下一颗 珠子为止。显然，不同的聚合顺序得到的总能量是不同