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

NOIP2018联赛测试题衡阳市第八中学

NOIP2018 联赛测试题衡阳市第八中学

题目名称

GCD

题目类型

传统型

目录

gcd

可执行文件名

gcd

输入文件名

gcd.in

输出文件名

gcd.out

每个测试点时限 1.0 秒

内存限制

512MB

测试点数目

20

每个测试点分数 5

最短路 传统型 route route route.in route.out 1.0 秒 512MB 20 5

数列 传统型 seq Seq seq.in seq.out 1.0 秒 512MB 20 5

提交源程序文件名

对于 C++语言 gcd.cpp

对于 C 语言

gcd.c

对于 Pascal 语言 gcd.pas

route.cpp route.c route.pas

seq.cpp seq.c seq.pas

最大公约数(gcd)

时间限制:1s

空间限制:512MB

题目描述

最大公 约数 GCD(a,b)是 指 a,b 共有 的因子中最大的那一个。比如说,

GCD(12,18)=6,因为 6 既是 12 的因子,也是 18 的因子,而且不存在其他比 6

大的而且也是 12,18 的因子的数。

小明想知道如果给定 n,m,对于 1<= i <=n,GCD( i , m )的最大值是多少。

输入格式 从文件 gcd.in 中读入数据 第一行有两个用空格隔开的正整数 n,m,含义见题目描述

输出格式 输出到文件 gcd.out 中 一行,只有一个整数,表示对于 1<= i <= n , GCD( i , m )的最大值。

样例 1 输入 46

输出 3

样例 1 说明 可以按照 GCD 的定义求得 GCD(1,6)=1 ;GCD(2,6)=2;GCD(3,6)=3;GCD(4,6)=2; 所以答案为 3

样例 2 输入 5 10

输出 5

样例 2 说明 可以按照 GCD 的定义求得 GCD(1,10)=1;GCD(2,10)=2;GCD(3,10)=1; GCD(4,10)=2;GCD(5,10)=5,所以答案为 5
数据范围 对于 60%的数据, 1<=n<=1000,1<=m<=1000 对于 100%的数据,1<=n<=1e9,1<=m<=1e9

最短路(route)

时间限制:1s

空间限制:512MB

题目描述

给出一个包含 n 个点,m 条有向边的图,每个点都有独特的标号,点的标号

范围为 1 到 n。对于每条边做一次询问,询问将该条边的方向取反,长度不变,

其他边都保持不变是否会使得从 1 号点到 2 号点的最短路径长度相比原始的图变

长,变短或者不变。可能存在重边,即两条边的起点和终点都对应相同;但不存

在自环,即不存在某一条边的起点和终点是同一个点。保证原图中存在从 1 号点

到 2 号点的路径。

注意,每次只做询问,不对原图产生任何影响。

输入格式
从文件 route.in 中读入数据 第一行包括 2 个用空格隔开的整数,n,m,表示图中有 n(n>=2)个点,m 条边。 接下来有 m 行,描述了原始图中的每条边。 每行有 3 个用空格隔开的正整数,ai,bi,ci(1<=i<=m)。表示原始的图中有一条 从 ai 号点到 bi 号点的有向边,长度为 ci。(保证 ai 不等于 bi)
输出格式
输出到文件 route.out 中 共 m 行,每行 1 个整数,其中第 i 行的整数 ansi 表示如果将第 i 条边的方向 变成相反的方向,长度不变,其他边都保持不变使得从 1 号点到 2 号点的最 短距离相对于原图变化的结果。ansi 的含义如下:
1.ansi 为 1 时表示最短距离相对于原图变长或者不存在从 1 号点到 2 号

点的路径;

2.ansi 为 0 时表示最短距离相对于原图不变;

3.ansi 为-1 时表示最短距离相对于原图变短;

样例

样例输入
45 427 346 135 2 1 18 2 3 12
样例说明

样例输出
1 1 1 0 -1

在原图中的最短路径为:1->3->4->2 ,最短距离为 5+6+7=18

如果令第 1 条边反向,新的图中不存在从 1 号点到达 2 号点的路径

如果令第 2 条边反向,新的图中不存在从 1 号点到达 2 号点的路径

如果令第 3 条边反向,新的图中不存在从 1 号点到达 2 号点的路径

如果令第 4 条边反向, 新的图中多了一条从 1 号点到达 2 号点的路径:1->2,长

度为 18,最短距离仍然不变

如果令第 5 条边反向,新的图中多了一条从 1 号点到达 2 号点的路径:1->3->2,

长度为 5+12=17,最短距离相对于原图变短了

数据范围
有 20%的数据,2<=n<=100,m<=1e3,1<=ci<=1e5 有 20%的数据,2<=n<=1e5,m<=1e5, 1<=ci<=1e5,且出度大于 2 的点不超过 15 个 其他 60%的数据,2<=n<=1e5,m<=1e5, 1<=ci<=1e5,且无其他限制

数列(seq)
时间限制:1s 空间限制:512MB 题目描述
有一个长度为 n 的数列,第 i 个元素的值为 ai。小明可以把这段数列切成几 段数列,然后重新将各段数列拼接成新的长度为 n 的数列(拼接过程中不可以将 数列翻转)。他想知道最少需要切几次才能使得拼接成的新数列是单调不降的数 列。
输入格式
从文件 seq.in 中读入数据 第一行包含一个正整数 n,表示初始数列的长度 第二行包括 n 个用空格隔开的正整数,第 i 个正整数 ai,表示初始数列第 i 个元素值的大小。
输出格式
输出到文件 seq.out 中 只有一行,包含一个正整数 ans,表示最少需要切 ans 次才能重新拼接得到 单调不降的数列。

样例输入
6 112314

样例输出 2

样例解释
在 4 个和 5 个元素右端的地方分别切一次,于是得到了{1,1,2,3},{1},{4}这三段 数列,然后重新按照{1},{1,1,2,3},{4}的顺序排列,再拼接成{1,1,2,3,4}的新数列, 显然这个新数列是单调不降的。
数据范围
对于 40%的数据,n<=1e3,1<=ai<=2e5 对于 100%的数据,n<=1e5,1<=ai<=2e9


相关文章:
NOIP2018联赛测试题衡阳市第八中学.pdf
NOIP2018 联赛测试题衡阳市第八中学题目名称 题目类型 目录 可执行文件名
湖南省衡阳市第八中学2017-2018学年高一五科联赛数学试....pdf
湖南省衡阳市第八中学2017-2018学年高一五科联赛数学试题+PDF版含答案_
湖南省衡阳市第八中学2017-2018学年高一下学期五科联赛....doc
湖南省衡阳市第八中学2017-2018学年高一下学期五科联赛试题 数学 (word版含答案) - 2017 年下期衡阳市八中高一五科联赛 数学试题 考试范围:集合及运算、函数及其...
...2018学年湖南省衡阳市第八中学高一下学期五科联赛数....doc
2017-2018学年湖南省衡阳市第八中学高一下学期五科联赛数学试题+Word版含答案 - 2017-2018 学年湖南省衡阳市第八中学高一下学期五科联赛 数学试题题 本试卷分第...
2017-2018学年湖南省衡阳八中高一五科联赛数学试题.doc
2017-2018学年湖南省衡阳八中高一五科联赛数学试题 - 2017 年下期衡阳市八中高一五科联赛 数学试题 第Ⅰ卷(共 60 分)最新试卷十年寒窗苦,踏上高考路,心态放平...
湖南省衡阳市第八中学2018-2019学年高二上学期六科联赛....doc
湖南省衡阳市第八中学2018-2019学年高二上学期六科联赛试题(12月)历史Word版含答案 - 2018 年下期衡阳市八中高二联赛 历史试题 命题人:蒋平 审题人:唐卓然 请...
2018 年全国初中数学联赛模拟测试题(初三组)答案.doc
2018 年全国初中数学联赛模拟测试题(初三组) 第一试一、 选择题 . (本题
湖南省衡阳市第八中学2018-2019学年高三高考适应性考试....doc
湖南省衡阳市第八中学2018-2019学年高三高考适应性考试文综政治试题 - 衡阳市八中 2018-2019 学年高考适应考试文综政治试题 1. 近年来,美国等发达国家推动其国内...
湖南省衡阳市第八中学2017_2018学年高一地理下学期期末....doc
湖南省衡阳市第八中学2017_2018学年高一地理下学期期末结业考试试题(实验班,含解析) - 湖南省衡阳市第八中学 2017-2018 学年高一(实验班)下学期期末结 业考试...
【新】湖南省衡阳市第八中学2017-2018学年高一地理下学....doc
【新】湖南省衡阳市第八中学2017-2018学年高一地理下学期期末结业考试试题(实验班) - 小中高 精品 教案 试卷 湖南省衡阳市第八中学 2017-2018 学年高一地理下...
【全国百强校】湖南省衡阳市第八中学2017-2018年高二12....doc
【全国百强校】湖南省衡阳市第八中学2017-2018年高二12月月考政治试题 - 2017 年衡阳市八中高二 12 月份月考 政治试题 请注意:时量 90 分钟 满分 100 分 第...
湖南省衡阳市第八中学2018-2019学年高一(实验班)下学期....doc
湖南省衡阳市第八中学2018-2019学年高一(实验班)下学期期末结业考试理综-化学试题+Word版含答案 - 2018-2019 学年 9.A、B、C、D 为原子序数依次增大的短周期...
2018届湖南省衡阳市第八中学高三(实验班)第一次模拟文....doc
2018届湖南省衡阳市第八中学高三(实验班)第一次模拟文综政治试题 - 政治试题 12.海关总署发布第 57 号公告,针对我国居民在境外购买意愿较强、关税税率较高的...
湖南省衡阳市第八中学2018_2019学年高一英语上学期期中....doc
湖南省衡阳市第八中学2018_2019学年高一英语上学期期中试题 - 衡阳市八中 2018 年下期期中考试试题 高一英语 时量:120 分钟 总分:100 分 注意事项: 1. 答第...
湖南省衡阳市第八中学2018_2019学年高二政治下学期期中....doc
湖南省衡阳市第八中学 2018-2019 学年高二政治下学期期中试题 理 第 I
湖南省衡阳市第八中学2018-2019学年高一上学期期末考试....doc
湖南省衡阳市第八中学2018-2019学年高一上学期期末考试 历史 Word版含
湖南省衡阳市第八中学2017-2018学年高一自主招生考试语....doc
湖南省衡阳市第八中学2017-2018学年高一自主招生考试语文试题(一) Wor
湖南省衡阳市第八中学2018-2019学年高一自主招生考试语....doc
湖南省衡阳市第八中学2018-2019学年高一自主招生考试语文试题(一) Wor
湖南省衡阳市第八中学2018_2019学年高二地理下学期年度....doc
湖南省衡阳市第八中学2018_2019学年高二地理下学期年度过关考试试题 - 湖南省衡阳市第八中学 2018-2019 学年高二地理下学期年度过关考 试试题 请注意:时量 90 ...
NOIP2018第二十四届全国青少年信息学奥林区克联赛初赛....doc
NOIP2018第二十四届全国青少年信息学奥林区克联赛初赛普及组试题及参考答案(手打版) 第二十四届全国青少年信息学奥林区克联赛初赛 普及组一、单项选择题 1、以下哪...
更多相关标签: