tceic.com
简单学习网 让学习变简单
当前位置:首页 >> 学科竞赛 >>

NOIP2014提高组复赛试题Day2


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

提高组 day2
(请选手务必仔细阅读本页内容)
一.题目概况 中文题目名称 英文题目与子目录名 可执行文件名 输入文件名 输出文件名 每个测试点时限 测试点数目 每个测试点分值 附加样例文件 结果比较方式 题目类型 运行内存上限 二.?交源程序文件名 对于 C++语言 对于 C 语

言 对于 pascal 语言 wireless.cpp wireless.c wireless.pas road.cpp road.c road.pas equation.cpp equation.c equation.pas 无线网路发射器选址 wireless wireless wireless.in wireless.out 1秒 10 10 有 寻找道路 road road road.in road.out 1秒 10 10 有 全文比较(过滤行末空格及文末回车) 传统 128M 传统 128M 传统 128M 解方程 equation equation equation.in equation.out 1秒 20 5 有

三.编译命令(不包含任何优化开关) 对于 C++语言 对于 C 语言 对于 pascal 语言 g++ -o wireless wireless.cpp–lm gcc -o wireless wireless.c –lm fpc wireless.pas g++ -o road road.cpp –lm gcc -o road road.c –lm fpc road.pas 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.无线网络发射器选址 (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。 输出一行,包含两个整数,用一个空格隔开,分别表示能覆盖最多公共场所的安装地点 方案数,以及能覆盖的最多公共场所的数量。 【输入输出样例】 wireless.in wireless.out

1 2 4 4 10 6 6 20

1 30

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

128,

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 1 2 1 2 2 1 3 -1 road.out

【输入输出样例说明】

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

【输入输出样例说明】

如上图所示,满足条件的路径为 1->3->4->5。注意点 2 不能在答案路径中,因为点 2 连了一条边到点 6,而点 6 不与终点 5 连通。

【数据说明】 对于 30%的数据,0< n ≤10,0< m ≤20; 对于 60%的数据,0< n ≤100,0< m ≤2000; 对于 100%的数据,0< n ≤10,000,0< m ≤200,000,0< x,y,s,t≤n,x≠t。

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

求这个方程在[1, m]内的整数解(n 和 m 均为正整数) 。 【输入】 输入文件名为 equation.in。 输入共 n+2 行。 第一行包含 2 个整数 n、m,每两个整数之间用一个空格隔开。 接下来的 n+1 行每行包含一个整数,依次为 a0,a1,a2,……,an。

【输出】 输出文件名为 equation.out。 第一行输出方程在[1, m]内的整数解的个数。 接下来每行一个整数,按照从小到大的顺序依次输出方程在[1, m]内的一个整数解。 【输入输出样例 1】 equation.in 2 10 1 -2 1 1 1 equation.out

【输入输出样例 2】 equation.in equation.out

2 10 2 -3 1

2 1 2

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

【数据说明】 对于 30%的数据,0<n≤2,|ai|≤100,an≠0,m≤100; 对于 50%的数据,0<n≤100,|ai|≤10 ,an≠0,m≤100;
100

对于 70%的数据,0<n≤100,|ai|≤10

10000

,an≠0,m≤10000; ,an≠0,m≤1000000。

对于 100%的数据,0<n≤100,|ai|≤10

10000


推荐相关:

NOIP2014提高组复赛试题Day2

NOIP2014提高组复赛试题Day2_学科竞赛_高中教育_教育专区。CCF 全国信息学奥林匹克联赛(NOIP2014)复赛 提高组 day2 (请选手务必仔细阅读本页内容)一.题目概况 ...


NOIP2014提高组复赛试题day1+day2

NOIP2014提高组复赛试题day1+day2_从业资格考试_资格考试/认证_教育专区。CCF 全国信息学奥林匹克联赛(NOIP2014)复赛 提高组 day1 1.生活大爆炸版石头剪刀布 (...


NOIP2013提高组复赛试题day2

NOIP2013提高组复赛试题day2_学科竞赛_高中教育_教育专区。全国信息学奥林匹克联赛...NOIP2014提高组复赛试题... NOIP2014提高组复赛试题...1/2 相关文档推荐 ...


NOIP2014提高组复赛试题

CCF 全国信息学奥林匹克联赛(NOIP2014)复赛 提高组 day2 1.无线网络发射器选址 (wireless.cpp/c/pas) 【问题描述】 随着智能手机的日益普及,人们对无线网的...


NOIP2014提高组复赛试题

CCF 全国信息学奥林匹克联赛(NOIP2014)复赛 提高组 day2 (请选手务必仔细阅读本页内容)一.题目概况 中文题目名称 英文题目与子目录名 可执行文件名 输入文件名 ...


NOIP2014提高组复赛试题(C语言版)

CCF 全国信息学奥林匹克联赛(NOIP2014)复赛 提高组 day2 (请选手务必仔细阅读本页内容)一.题目概况 中文题目名称 英文题目与子目录名 可执行文件名 输入文件名 ...


NOIP2013提高组复赛试题day1+day2

NOIP2013提高组复赛试题day1+day2_财会/金融考试_资格考试/认证_教育专区。今日推荐 68份文档 新市场营销法则 助推企业成长 999感冒灵市场营销方案 汽车品牌的足球...


NOIP2011复赛模拟题Day2

NOIP2011 提高组 Day2 4页 免费 冲刺NOIP2011长乐...NOIP2011 复赛模拟题 Day2 题目名称 时间限制 空间...2014年执业医师考试指导 口腔执业医师实践技能复习资料...


Noip 2013 提高组 Day2 解题报告

Noip 2013 提高组 Day2 解题报告_学科竞赛_高中教育_教育专区。Noip 2013 提高组 Day2 解题报告 Noip 2013 Day2 解题报告 --By GreenCloudS 第一题:积木大赛...


十七届信息学奥赛提高组复赛第二天(NOIP2011)解题报告

十七届信息学奥赛提高组复赛第二天(NOIP2011)解题报告...NOIP2011DAY2 解题报告 今天的题还蛮有意思的,虽然...2014全国高考状元联手分享状元笔记 衡水中学文科学霸...

网站首页 | 网站地图
All rights reserved Powered by 简单学习网 www.tceic.com
copyright ©right 2010-2021。
文档资料库内容来自网络,如有侵犯请联系客服。zhit325@126.com