当前位置:首页 >> 学科竞赛 >> 山东NOIP提高组模拟day1

山东NOIP提高组模拟day1


山东多校联合模拟赛 day1
一.题目概况
中文题目名称 英文题目名 可执行文件名 输入文件名 输出文件名 每个测试点时限 测试点数目 每个测试点分值 附加样例文件 结果比较方式 题目类型 矩形计数 rect rect rect.in rect.out 1秒 10 10 有 传统 祖先 ancestor ancestor ancestor.in ancesto

r.out 1秒 10 10 有 全文比较(过滤行末空格及文末回车) 传统 传统 Formula 1 f1 f1 f1.in f1.out 1秒 10 10 有

二.提交源程序文件名
对于 C++语言 对于 C 语言 对于 pascal 语言 rect.cpp rect.c rect.pas ancestor cpp ancestor.c ancestor. pas f1.cpp f1.c f1. pas

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

四.运行内存限制
内存上限 128M 128M 128M

注意事项:
1、文件名(程序名和输入输出文件名)必须使用英文小写。 2、C/C++中函数 main()的返回值类型必须是 int,程序正常结束时的返回值必须是 0。 3、C/C++使用 printf 函数输出 64 位有符号整数变量,请使用 printf(“%lld”) 4、请各学校自己负责强调比赛纪律,避免讨论算法、搜题解、粘模板等行为,维护公平的 比赛环境。 5、评测机 fpc 版本:2.4.4,gcc、g++版本:4.7.0。对于 pascal 选手,可以使用 math 库。对 于 C++选手,可以使用 STL。

第 1 页 共 7 页

1.矩形计数
(rect.cpp/c/pas) 【问题描述】 给出圆周上的 N 个点,请你计算出以这些点中的任意四个为四个角,能构成多少个矩 形。 点的坐标是这样描述的,给定一个数组 v[1..N],假设圆心为(0,0),圆的周长 C=∑ v[1..N] ,第一个点坐标为(0,C/(2π))。从第一个点开始,顺时针沿圆周走 v1 个单位长度, 此时坐标为第二个点的坐标, 再走 v2 个单位长度, 此时为第三个点的坐标, 当走完 v1, v2..vi 个距离后,为第 i+1 个点的坐标(全过程都是沿圆周顺时针) 。特别的,走完 v1,v2..vn 个 距离后,就会回到第一个点。 【输入】 输入文件名为 rect.in。 输入共 N+1 行。 第一行为正整数 N。 接下来 N 行每行一个正整数。其中第 i+1 行表示的是 v[i]。 【输出】 输出文件名为 rect.out。 输出共 1 行,一个整数,表示能构成的矩形的个数。 【输入输出样例 1】 rect.in 8 1 2 2 3 1 1 3 3

rect.out 3

第 2 页 共 7 页

【输入输出样例说明】

如上图。 【数据范围】 对于 100%的数据,有 N<=20,V 数组中的所有元素的值<=100。

第 3 页 共 7 页

2.祖先
(ancestor.cpp/c/pas) 【问题描述】 任何一种生物的 DNA 都可以表示为一个由小写英文字母组成的非空字符串。科学家发 现,所有的生物都有可能发生变异。所谓变异,就是子代的 DNA 串与父代的 DNA 串有差 异。每次变异,DNA 串中恰好有一个字符会变成两个任意的字符。一共有 n 种可能的变异。 变异 ai->bici 表示字符 ai 有可能变异为两个字符 bici。详细来说,就是删掉一个字符 ai,之 后在原来 ai 的位置处,插入 bi,ci 两个字符(注意字符 bi 必须在 ci 的前面) 。每种变异都 有可能发生任意多次。可以发现,每变异一次,DNA 串的长度会加 1。 如果有一种生物 a,他的 DNA 串是 s1,另外存在一种生物 b,他的 DNA 串是 s2。如 果 s2 可以通过若干次变异变为 s1,那么生物 b 就被叫做生物 a 的祖先。 现在,给定一种生物,他的 DNA 串是 s。请找出他的一个祖先,且这个祖先的 DNA 串 尽量短。 【输入】 输入文件 ancestor.in,共 n+2 行。 第一行包含一个非空字符串 s。 第二行含有一个整数 n,表示所有可能的变异。 接下来 n 行,每行描述一种可能的变异,按照 ai->bici 的格式。 s,ai,bi,ci 仅包含小写英文字母。 请注意:一种变异可能出现多次。 【输出】 输出文件名为 ancestor.out。 输出只有一行,一个整数,表示祖先 DNA 串的最短长度。 【输入输出样例 1】 ancestor.in ancestor.out ababa 2 c->ba c->cc 【输入输出样例 2】 ancestor.in ababa 7 c->ba c->cc e->ab z->ea b->ba d->dd d->ab 2

ancestor.out 1

第 4 页 共 7 页

【数据范围】 对于 30%的数据,s 的长度<=5, N <= 3; 对于 100%的数据,s 的长度<=50, N <= 50

第 5 页 共 7 页

3.Formula 1
(f1.cpp/c/pas) 【问题描述】 F1,中文全称为一级方程式锦标赛,是最高级的方程式赛车比赛,现在你作为一名选 手参加了一场 F1 的比赛,比较特殊地,本次比赛是在一个 N 个点 M 条边的无向图上举行 的。 起点是 S,终点是 T,每条边长度为 1 公里,赛车每行驶 1 公里耗油 1 个单位,途中共 有 k 个加油站,每经过加油站时,可以把油加满,但你的赛车设计顾问告诉你,油箱容量越 大,赛车跑的就越慢。为了追求最快的速度,在能顺利到达终点,不会中途没油的前提下, 你希望最小化油箱的容量(注意,虽然油箱变小可能导致路径变长,但我们只关心最小化的 油箱) 。 【输入】 输入文件 f1.in。 第一行一个正整数 T 表示测试数据组数,每组数据格式如下: 第一行三个整数,N,M,K,表示无向图的点数,边数,加油站数。 第二行 K 个正整数 i1,i2..ik 表示这些点上有加油站(可能重复,保证至少一个加油站在 S 点) 。 接下来 M 行,每行两个正整数 Bi,Ei 表示有一条连接(Bi,Ei)的双向边(可能有重边和自 环) 。 最后一行两个正整数 S,T 表示起点、终点。 【输出】 输出文件名为 f1.out。 对于每组数据,如果没法到达终点,输出-1,否则输出最小化的油箱容量。 【输入输出样例 1】 f1.in f1.out 2 663 136 12 23 42 56 45 34 16 7 10 3 134 12 42 3 -1

第 6 页 共 7 页

75 45 71 25 72 37 32 51 46 【数据范围】 对于 30%的数据,N<=200,M<=2000。 对于 60%的数据,N<=1000,M<=10000。 对于 100%的数据,1<=K,S,T<=N<=100000,1<=M<=150000,1<=T<=5。

第 7 页 共 7 页


更多相关文档:

NOIP2015提高组复赛试题Day1

全国信息学奥林匹克联赛(NOIP2015)复赛 提高组 day1 CCF 全国信息学奥林匹克联赛(NOIP2015)复赛 提高组day1 (请选手务必仔细阅读本页内容)一.题目概况 中文题目...

NOIP2015提高组day1第二题解题报告

NOIP2015提高组day1第二题解题报告_学科竞赛_高中教育_教育专区。NOIP2015提高组...老师王老师经常说的一件事情就 是数形结合) ,多画图,多模拟,就很容易找到...

NOIP2015提高组解题报告

NOIP2015提高组解题报告_学科竞赛_高中教育_教育专区...【解题说明】 直接模拟即可 【代码】 #include<...NOIP2015提高组day1第二... 8页 免费 NOIP2015...

NOIP2014提高组复赛试题day1+day2

CCF 全国信息学奥林匹克联赛(NOIP2014)复赛 提高组 day1 1.生活大爆炸版石头剪刀布 (rps.cpp/c/pas) 【问题描述】 石头剪刀布是常见的猜拳游戏:石头胜剪刀,...

NOIP2011提高组解题报告day1

NOIP2011提高组解题报告day1_学科竞赛_高中教育_教育专区。NOIP2011提高组解题报告day1NOIP2011 提高组解题报告 day1 (2011-12-13 09:29:54) 标签: 杂谈 铺地...

学军中学NOIP2013提高组原创模拟题day1

学军中学NOIP2013提高组原创模拟day1 测试时间:2.5小时 中文题目名称 输入文件名 输出文件名 每个测试点时限 测试点数目 每个测试点分值 运行内存上限 装果子 ...

NOIP2014复赛提高组模拟试题

NOIP2014复赛提高组模拟试题_学科竞赛_高中教育_教育专区。CCF 全国信息学奥林匹克...(NOIP2014)复赛 day1 3.跑步 (running.cpp/c/pas)【问题描述】 某校开展了...

NOIP2015山东赛区初赛预备通知

NOIP2015山东赛区初赛预备通知_行政公文_工作范文_实用文档。NOIP2015 山东赛区初赛 预备通知各市科协、教育局(处) 、计算机学会、联赛有关单位(学校) : 全国青少年...

NOIP2015提高组复赛试题Day1+Day2纯Word版

全国信息学奥林匹克联赛(NOIP2015)复赛 提高组 day1 CCF 全国信息学奥林匹克联赛(NOIP2015)复赛 提高组 day1 (请选手务必仔细阅读本页内容)一.题目概况 中文...

NOIP 2016 提高组 复赛 Day1

NOIP 2016 提高组 复赛 Day1_学科竞赛_高中教育_教育专区。第二十二届全国...山东NOIP提高组模拟day1 7页 免费 NOIP 2011 提高组 day1 ... 1页 5下载...
更多相关标签:
noip2016提高组day1 | noip2015提高组day1 | noip2014提高组day1 | noip2012提高组day1 | noip2013提高组day1 | noip2011提高组day1 | noip2015day1模拟题 | noip2016 day1 |
网站地图

文档资料共享网 nexoncn.com copyright ©right 2010-2020。
文档资料共享网内容来自网络,如有侵犯请联系客服。email:zhit325@126.com