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

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++语言 对于 C 语言 对于 Pascal 语言 gcd.cpp gcd.c gcd.pas route.cpp route.c route.pas seq.cpp seq.c seq.pas

最大公约数(gcd)
时间限制:1s
题目描述 最大公 约数 GCD(a,b) 是 指 a,b 共有 的因子中最大的那一个。比如说, GCD(12,18)=6,因为 6 既是 12 的因子,也是 18 的因子,而且不存在其他比 6 大的而且也是 12,18 的因子的数。 小明想知道如果给定 n,m,对于 1<= i <=n,GCD( i , m )的最大值是多少。

空间限制:512MB

输入格式 从文件 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 题目描述
给出一个包含 n 个点,m 条有向边的图,每个点都有独特的标号,点的标号 范围为 1 到 n。对于每条边做一次询问,询问将该条边的方向取反,长度不变, 其他边都保持不变是否会使得从 1 号点到 2 号点的最短路径长度相比原始的图变 长,变短或者不变。可能存在重边,即两条边的起点和终点都对应相同;但不存 在自环, 即不存在某一条边的起点和终点是同一个点。保证原图中存在从 1 号点 到 2 号点的路径。 注意,每次只做询问,不对原图产生任何影响。

空间限制:512MB

输入格式
从文件 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 题目描述
有一个长度为 n 的数列,第 i 个元素的值为 ai。小明可以把这段数列切成几 段数列, 然后重新将各段数列拼接成新的长度为 n 的数列 (拼接过程中不可以将 数列翻转) 。他想知道最少需要切几次才能使得拼接成的新数列是单调不降的数 列。

空间限制:512MB

输入格式
从文件 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


相关文章:
更多相关标签: