全国信息学奥林匹克联赛（NOIP2012）复赛模拟
6
200
16
7
1000
17
8
2010
18
9
2011
19
10
2012
20
提高组第二试
148888 188888 199999 199999 200000
第5页共5页
1秒 20 5 有 传统
二．
提交源程序文件名
对于 pascal 语言 station.pas
对于 C 语言
station.c
对于 C++语言 station.cpp
murder.pas murder.c murder.cpp
compile.pas compile.c compile.cpp
三． 编译命令（不包含任何优化开关） 对于 pascal 语言 fpc station.pas
现在伊斯兰革命卫队打算以最小伤害代价进入迷阵，打开全部机关，显然，他们可以选 择任意多的人从任意的门进入，但必须到达第 n 行的每个房间。一个士兵受到的伤害值为他 到达某个机关的路径上所有房间的伤害值中的最大值，整个部队受到的伤害值为所有士兵的 伤害值中的最大值。现在，这个恐怖组织掌握了迷阵的情况，他们需要提前知道怎么安排士 兵的行进路线可以使得整个部队的伤害值最小。
g++ -o compile compile.cpp -lm
四．
运行内存限制 内存上限
128M
128M
128M
五． 注意事项 1、 文件名（程序名和输入输出文件名）必须使用小写。 2、 C/C++中函数 main()的返回值类型必须是 int，程序正常结束时的返回值必须是 0。 3、 全国统一评测时采用的机器配置为：CPU 1.9GHz，内存 1G，上述时限示接收最多能量的发射站接收到的能量值，答案不超过 longint。
【输入输出样例】 station.in 3 42 35 6 10
station.out 7
【样例解释】 第 3 个发射站可接收第 1 和第 2 个发射的能量：2+5=7。
【数据范围】 对于 40%的数据，1<=N<=5000；1<=Hi<=100000；1<=Vi<=10000; 对于 70%的数据，1<=N<=100000；1<=Hi<=2,000,000,000；1<=Vi<=10000; 对于 100%的数据，1<=N<=1000000;1<=Hi<=2,000,000,000；1<=Vi<=10000。
【输入格式】 第一行有两个整数 n，m，表示迷阵的大小。 接下来 n 行，每行 m 个数，第 i 行第 j 列的数表示 p[i][j]。
【输出格式】 输出一个数，表示最小伤害代价。
【输入输出样例】 murder.in 42 00 35 24 00
murder.out 3
【数据范围】 50%的数据，n，m<=100； 100%的数据，n,m<=1000，p[i][j]<=1000。
题目类型
发射站 station station station.in station.out
2秒 10 10 有 传统
刺杀大使 murder murder murder.in murder.out
2秒 10 10 有 传统
编译优化 compile compile compile.in compile.out
迷阵由 n*m 个相同的小房间组成，每个房间与相邻四个房间之间有门可通行。在第 n 行的 m 个房间里有 m 个机关，这些机关必须全部打开才可以进入大使馆。而第 1 行的 m 个 房间有 m 扇向外打开的门，是迷阵的入口。除了第 1 行和第 n 行的房间外，每个房间都被 使馆的安保人员安装了激光杀伤装置，将会对进入房间的人造成一定的伤害。第 i 行第 j 列 造成的伤害值为 p[i][j](第 1 行和第 n 行的 p 值全部为 0)。
74
1234567
compile.out Error!
【数据范围】
对于全部数据：m<=n；-1000<=Ai<=1000
N 的大小对于不同数据有所不同：
数据编号
N 的大小
数据编号
1
40
11
2
45
12
3
50
13
4
55
14
5
200
15
第4页共5页
N 的大小 2013 5000 10000 49999 111111
显然，每个发射站发来的能量有可能被 0 或 1 或 2 个其他发射站所接受，特别是为了安 全，每个发射站接收到的能量总和是我们很关心的问题。由于数据很多，现只需要你帮忙计 算出接收最多能量的发射站接收的能量是多少。
【输入格式】 第 1 行：一个整数 N; 第 2 到 N+1 行：第 i+1 行有两个整数 Hi 和 Vi，表示第 i 个人发射站的高度和发射的能量
全国信息学奥林匹克联赛（NOIP2012）复赛模拟
提高组第二试
全国信息学奥林匹克联赛（NOIP2012）复赛模拟
提高组第二试
2012 年 10 月 25 日 14:20-17:20
（请选手务必仔细阅读本页内容）
一．
题目概况 中文题目名称 英文题目名称 可执行文件名
输入文件名 输出文件名 每个测试点时限 测试点数目 每个测试点分值 附加样例文件
【输入格式】
输入文件的第一行包含两个正整数 n、m。 第二行为 n 个整数 Ai。
【输出格式】 输出文件仅一个整数，表示最后对该程序进行优化后的最大效果值。如果无解输出
“Error!”，不包含引号。
【输入输出样例一】 compile.in
73
1234567
compile.out 15
【输入输出样例二】 compile.in
第3页共5页
全国信息学奥林匹克联赛（NOIP2012）复赛模拟
提高组第二试
编译优化
(compile.pas/c/cpp)
【问题描述】 众所周知，衡量一个编译器是否优秀的标准，除了它的编译速度和正确性以外，编译出
的代码的质量也很重要。最近，作为 XCC 系列编译器作者的 Dr. X 发明了一种跨时代的优化 算法：“NanGe 不等式优化”。一个程序可以看成是由若干个连续的函数构成的，NanGe 不 等式算法能针对某一个函数进行优化，得到一个优化效果值, 不同的函数的效果值可能是不 同的。但这个算法还有一个很大的 Bug：
该算法不能同时优化相邻的两个函数，否则就会直接 Compile Error，值得注意的是，一 个程序的第一个函数和最后一个函数也算是相邻的 。
现在给你一个程序从头到尾每个函数的优化效果值，Dr. X 想用 NanGe 不等式对该程序 的 M 个函数进行优化，他该怎么选择才能使总的优化效果值最大（前提是不能出现错误）？ 如果错误不能避免，请输出“Error!”
第2页共5页
全国信息学奥林匹克联赛（NOIP2012）复赛模拟
提高组第二试
刺杀大使
(murder.pas/c/cpp)
【问题描述】 伊朗伊斯兰革命卫队（某恐怖组织）正在策划一起刺杀行动，他们的目标是沙特驻美大
使朱拜尔。他们来到了沙特驻美使馆，准备完成此次刺杀，要进入使馆首先必须通过使馆前 的防御迷阵。
省在自测时可根据具体配置调整时限。
第1页共5页
全国信息学奥林匹克联赛（NOIP2012）复赛模拟
提高组第二试
发射站
(station.pas/c/cpp)
【问题描述】 某地有 N 个能量发射站排成一行，每个发射站 i 都有不相同的高度 Hi，并能向两边（当
然两端的只能向一边）同时发射能量值为 Vi 的能量，并且发出的能量只被两边最近的且比 它高的发射站接收。
对于 C 语言
gcc –o station station.c -lm
fpc murder.pas gcc –o murder murder.c -lm
对于 C++语言
g++ -o station station.cpp -lm
g++ -o murder murder.cpp -lm
fpc compile.pas gcc –o compile compile.c -lm