当前位置:首页 >> 学科竞赛 >>

NOIP2014复赛提高组day2


全国信息学奥林匹克联赛(NOIP2014)复赛

提高组 day2

CCF 全国信息学奥林匹克联赛( NOIP2014)复赛

提高组 day2
(请选手务必仔细阅读本页内容)
一.题目概况
中文题目名称 英文题目与子目录名 可执行文件名 输入文件名 输出文件名 每个测试点时限 测试点数目

每个测试点分值 附加样例文件 结果比较方式 题目类型 运行内存上限 传统 128M 无线网路发射器选址 wireless wireless wireless.in wireless.out 1秒 10 10 有 寻找道路 road road road.in road.out 1秒 10 10 有 全文比较(过滤行末空格及文末回车) 传统 128M 传统 128M 解方程 equation equation equation.in equation.out 1秒 20 5 有

二.提交源程序文件名
对于 C++语言 对于 C 语言 对于 pascal 语言 wireless.cpp wireless.c wireless.pas road.cpp road.c road.pas equation.cpp equation.c equation.pas

三.编译命令(不包含任何优化开关)
对于 C++语言 对于 C 语言 对于 pascal 语言 g++ -o wireless wireless.cpp -lm gcc -o wireless wireless.c -lm fpc wireless.pas fpc road.pas g++ -o road road.cpp -lm gcc -o road road.c -lm g++ -o equation equation.cpp -lm gcc -o equation equation.c -lm fpc equation.pas

注意事项:
1、文件名(程序名和输入输出文件名)必须使用英文小写。 2、C/C++中函数 main()的返回值类型必须是 int,程序正常结束时的返回值必须是 0。 3、全国统一评测时采用的机器配置为:CPU AMD Athlon(tm) 64x2 Dual Core CPU 5200+, 2.71GHz,内存 2G,上述时限以此配置为准。 4、只提供 Linux 格式附加样例文件。 5、特 别 提 醒 :评 测 在 当 前 最 新 公 布 的 NOI Linux 下 进 行 ,各 语 言 的 编 译 器 版 本 以 其 为 准。
第 1 页共 6 页

全国信息学奥林匹克联赛(NOIP2014)复赛

提高组 day2

1.无线网络发射器选址
(wireless.cpp/c/pas) 【问题描述】 随着智能手机的日益普及, 人们对无线网的需求日益增大。 某城市决定对城市内的公共 场所覆盖无线网。 假设该城市的布局为由严格平行的 129 条东西向街道和 129 条南北向街道所形成的网格 状,并且相邻的平行街道之间的距离都是恒定值 1 。东西向街道从北到南依次编号为 0,1,2…128,南北向街道从西到东依次编号为 0,1,2…128。 东西向街道和南北向街道相交形成路口, 规定编号为 x 的南北向街道和编号为 y 的东西 向街道形成的路口的坐标是(x, y) 。在某些路口存在一定数量的公共场所。 由于政府财政问题, 只能安装一个大型无线网络发射器。 该无线网络发射器的传播范围 是一个以该点为中心,边长为 2*d 的正方形。传播范围包括正方形边界。 例如下图是一个 d = 1 的无线网络发射器的覆盖范围示意图。

现在政府有关部门准备安装一个传播参数为 d 的无线网络发射器, 希望你帮助他们在城 市内找出合适的安装地点,使得覆盖的公共场所最多。 【输入】 输入文件名为 wireless.in。 第一行包含一个整数 d,表示无线网络发射器的传播距离。 第二行包含一个整数 n,表示有公共场所的路口数目。 接下来 n 行, 每行给出三个整数 x, y, k, 中间用一个空格隔开, 分别代表路口的坐标(x, y) 以及该路口公共场所的数量。同一坐标只会给出一次。 【输出】 输出文件名为 wireless.out。 输出一行,包含两个整数,用一个空格隔开,分别表示能覆盖最多公共场所的安装地点 方案数,以及能覆盖的最多公共场所的数量。

第 2 页共 6 页

全国信息学奥林匹克联赛(NOIP2014)复赛

提高组 day2

【输入输出样例】 wireless.in 1 2 4 4 10 6 6 20

wireless.out 1 30

【数据说明】 对于 100%的数据, 1 ≤ d ≤ 20, 1 ≤ n ≤ 20, 0 ≤ x ≤ 128, 0 ≤ y ≤ 128, 0 < k ≤ 1,000,000。

2.寻找道路
(road.cpp/c/pas) 【问题描述】 在有向图 G 中,每条边的长度均为 1,现给定起点和终点,请你在图中找一条从起点到 终点的路径,该路径满足以下条件: 1.路径上的所有点的出边所指向的点都直接或间接与终点连通。 2.在满足条件 1 的情况下使路径最短。 注意:图 G 中可能存在重边和自环,题目保证终点没有出边。 请你输出符合条件的路径的长度。 【输入】 输入文件名为 road.in。 第一行有两个用一个空格隔开的整数 n 和 m,表示图有 n 个点和 m 条边。 接下来的 m 行每行 2 个整数 x、y,之间用一个空格隔开,表示有一条边从点 x 指向点 y。 最后一行有两个用一个空格隔开的整数 s、t,表示起点为 s,终点为 t。 【输出】 输出文件名为 road.out。 输出只有一行,包含一个整数,表示满足题目描述的最短路径的长度。如果这样的路 径不存在,输出-1。 【输入输出样例 1】 road.in 3 2 1 2 2 1 1 3

road.out -1

第 3 页共 6 页

全国信息学奥林匹克联赛(NOIP2014)复赛

提高组 day2

【输入输出样例说明】

如上图所示,箭头表示有向道路,圆点表示城市。起点 1 与终点 3 不连通,所以满足题 目描述的路径不存在,故输出-1。 【输入输出样例 2】 road.in 6 6 1 2 1 3 2 6 2 5 4 5 3 4 1 5

road.out 3

【输入输出样例说明】

如上图所示,满足条件的路径为 1->3->4->5。注意点 2 不能在答案路径中,因为点 2 连了一条边到点 6,而点 6 不与终点 5 连通。 【数据说明】 对于 30%的数据,0 < ≤ 10,0 < ≤ 20; 对于 60%的数据,0 < ≤ 100,0 < ≤ 2000; 对于 100%的数据,0 < ≤ 10,000,0 < ≤ 200,000,0 < ,y,s,t ≤ n,x ≠ t。

第 4 页共 6 页

全国信息学奥林匹克联赛(NOIP2014)复赛

提高组 day2

3.解方程
(equation.cpp/c/pas) 【问题描述】 已知多项式方程:

! + ! + ! ! + ? + ! ! = 0
求这个方程在[1, m]内的整数解(n 和 m 均为正整数) 。 【输入】 输入文件名为 equation.in。 输入共 n+2 行。 第一行包含 2 个整数 n、m,每两个整数之间用一个空格隔开。 接下来的 n+1 行每行包含一个整数,依次为! , ! , ! , … , ! 。 【输出】 输出文件名为 equation.out。 第一行输出方程在[1, m]内的整数解的个数。 接下来每行一个整数,按照从小到大的顺序依次输出方程在[1, m]内的一个整数解。 【输入输出样例 1】 equation.in 2 10 1 -2 1

equation.out 1 1

【输入输出样例 2】 equation.in 2 10 2 -3 1

equation.out 2 1 2

【输入输出样例 3】 equation.in 2 10 1 3 2

equation.out 0

第 5 页共 6 页

全国信息学奥林匹克联赛(NOIP2014)复赛

提高组 day2

【数据说明】 对于 30%的数据,0 < ≤ 2, ! ≤ 100,! ≠ 0, ? ≤ 100; 对于 50%的数据,0 < ≤ 100, ! ≤ 10!"" ,! ≠ 0, ≤ 100; 对于 70%的数据,0 < ≤ 100, ! ≤ 10!"""" ,! ≠ 0, ≤ 10000; 对于 100%的数据,0 < ≤ 100, ! ≤ 10!"""" ,! ≠ 0, ≤ 1000000。

第 6 页共 6 页


相关文章:
NOIP2014提高组复赛试题day1+day2
CCF 全国信息学奥林匹克联赛(NOIP2014)复赛 提高组 day1 1.生活大爆炸版石头剪刀布 (rps.cpp/c/pas) 【问题描述】 石头剪刀布是常见的猜拳游戏:石头胜剪刀,...
NOIP2014提高组复赛试题Day2
NOIP2014提高组复赛试题Day2_学科竞赛_高中教育_教育专区。CCF 全国信息学奥林匹克联赛(NOIP2014)复赛 提高组 day2 (请选手务必仔细阅读本页内容)一.题目概况 ...
NOIP2014提高组复赛试题
CCF 全国信息学奥林匹克联赛(NOIP2014)复赛 提高组 day2 (请选手务必仔细阅读本页内容)一.题目概况 中文题目名称 英文题目与子目录名 可执行文件名 输入文件名 ...
NOIP2014提高组复赛试题
CCF 全国信息学奥林匹克联赛(NOIP2014)复赛 提高组 day2 1.无线网络发射器选址 (wireless.cpp/c/pas) 【问题描述】 随着智能手机的日益普及,人们对无线网的...
NOIP2014提高组复赛试题(C语言版)
CCF 全国信息学奥林匹克联赛(NOIP2014)复赛 提高组 day2 (请选手务必仔细阅读本页内容)一.题目概况 中文题目名称 英文题目与子目录名 可执行文件名 输入文件名 ...
NOIP2014提高组第二试题解
{ mc++; } cout<<mc<<' '<<maxn<<endl; return 0; 2.寻找道路这道题...NOIP2014提高组C++试题 10页 3下载券 NOIP2014提高组复赛试题... 6页 1...
NOIP2016提高组复赛试题(Day1+Day2)
NOIP2016提高组复赛试题(Day1+Day2)_IT/计算机_专业资料。NOIP2016提高组复赛试题 第22 届全国青少年信息学奥林匹克联赛 CCF-NOIP-2016 提高组(复赛) 第一试...
NOIP2014提高组复赛试题Day1
NOIP2014提高组复赛试题Day1_学科竞赛_高中教育_教育专区。CCF 全国信息学奥林...【输入输出样例 1】 bird.in 10 10 6 3 9 9 9 1 2 1 3 1 2 1 1...
NOIP2015提高组复赛试题Day1+Day2纯Word版
NOIP2015提高组复赛试题Day1+Day2纯Word版_学科竞赛_高中教育_教育专区。NOIP2015提高组复赛试题Day1+Day2纯Word版 全国信息学奥林匹克联赛(NOIP2015)复赛 提高组...
NOIP2014复赛提高组模拟试题
(NOIP2014)复赛 提高组 day1 (请选手务必仔细阅读本页内容)一、题目概况 中文...(可以一个球也不拿) 【输入输出样例】 toy.in 5 1 2 1 3 2 4 2 5 ...
更多相关标签:
noip2015复赛试题day2 | noip2015提高组day2 | noip2016提高组day2 | noip2014提高组day2 | noip2012提高组day2 | noip2011提高组day2 | noip2016提高组day2t1 | noip2013提高组day2 |