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

杭州学军中学NOIP2011模拟赛DAY2-2011-10-5


NOIP2011 模拟赛
By 杭州学军中学
中文题目名称 题目名 时间限制 空间限制 最大公约数 gcd.pas/c/cpp 1s 256M 序列游戏 game.pas/c/cpp 1s 256M 纪念品 senzo.pas/c/cpp 1s 256M

编译命令: (以题目名 A 为例) 对于 pascal 语言:fpc A.pas 对

于 C 语言:gcc -o A A.c -lm 对于 C++语言:g++ -o A A.cpp -lm

代码长度限制:50KB 请根据实际评测的机器配置适当放大或缩小时间和空间限制 为了评测及整理方便起见,文件夹名请使用"学校名-选手名"的格式, 里面不需要使用子文件夹,谢谢合作。

出题人:Gy , Chnlich , Nsk

最大公约数
题目描述
刚刚上完小学四年级的 Gy 和 Nsk 在讨论有关用辗转相除法求最 大公约数的问题。他们想知道,对于求 GCD(a,b) (a<=b<=N),辗转最 多的一对是哪一对。 辗转次数的定义:对于数对 A,B(A<=B),令 A'=B mod A,B'=A, 每次将(A,B)变为(A',B'),直到最终 A'=gcd(A,B)时总共进行的变换次 数。 辗转次数的具体解释: 比如在 N=10 时 4,6 -> 2,4 ==> 2 GCD(4,6)是 2 辗转了 1 次

3,8 -> 2,3 -> 1,2 ==> 1 GCD(3,8)是 1 辗转了 2 次

2,9 -> 1,2 ==> 1 GCD(2,9)是 1 辗转了 1 次

所以(3,8)比(2,9)和(4,6)辗转的多。

输入格式
一行,包含一个整数 N,含义如题所述。

输出格式
两行各一个整数,分别表示辗转次数最多的数对的 a 和 b。 如果辗转次数一样,取 b 最小的(如果 b 也一样,取 a 最小的) 。

样例输入
4

样例输出
2 3

数据范围
对于 20% 的数据 N<=10^4 对于 50% 的数据 N<=10^18 对于 100% 的数据 3<=N<=10^12000

序列游戏
题目描述
给定一个整数数列 Q,小学刚毕业的 Gy 和 Nsk 将分别对这个数 列进行一次操作。 首先,Gy 将这个数列的一个前缀(长度可以为 0)的每一个数 乘上-A; 然后,Nsk 将这个数列的一个后缀(长度可以为 0)的每一个数 乘上-B。 设 S 为操作后,这个数列所有元素的和。 Gy 要使 S 尽可能大,Nsk 要使 S 尽可能小。 现在,Chnlich 找到了你。他想要知道双方都不失误的情况下, 最终 S 的值是多少。

输入格式
第一行三个数 N,A,B。N 表示数列 Q 的长度,A,B 如上所述。 接下来 N 行,每行一个数,第 i+1 行的数表示这个数列的第 i 个 数 Qi。

输出格式
一行,表示最终 S 的值。

样例输入
311

-1 -2 -3

样例输出
0

样例解释
若 Gy 操作前 0 个数,则 Nsk 操作后 0 个数,最终序列为-1 -2 -3, 答案为-6; 若 Gy 操作前 1 个数,则 Nsk 操作后 0 个数,最终序列为 1 -2 -3, 答案为-4; 若 Gy 操作前 2 个数,则 Nsk 操作后 0 个数或 3 个数,最终序列 为-1 -2 3 或 1 2 -3,答案为 0; 若 Gy 操作 3 个数,则 Nsk 操作 3 个数,最终序列为-1 -2 -3,答 案为-6; 综上所述,S=max(-6,-4,0,-6)=0。

数据范围
测试点编号 0~1 2~3 4~7 8~13 14~19 N 的范围 N<=10 N<=200 N<=5000 N<=100000 N<=1000000 A,B 的范围 1<=A,B<=3 1<=A,B<=20 1<=A,B<=50 1<=A,B<=100 1<=A,B<=30 Qi 的范围 abs(Qi)<=20 abs(Qi)<=1000 abs(Qi)<=1000000000 abs(Qi)<=1000000000 abs(Qi)<=1000000000

纪念品
题目描述
Gy 和 Nsk 去幻想乡玩。 幻想乡由 N 个旅游景点构成,N 各景点之间有 N-1 条路。其实, 幻想乡可以看做一个棵以 1 号景点为根的树。 每个景点有一种独特的 纪念品,不同的纪念品有不同的价值。 现在某些景点有游客中心,在一个有游客中心的景点 i,你可以 知道以 i 为根的子树的所有景点能买到的纪念品的价值总和。1 号景 点一定有游客中心。 由于 Nsk 对纪念品很感兴趣,他经过的任何一个景点都会要求 Gy 买下那个景点的纪念品。同样,Nsk 不愿意重复经过同一个景点。 起点和终点也算作经过的景点。 现在 Gy 需要知道,从景点 x 到 y 的途中,他可能的最大破费和 最小破费分别是多少。 有许多组路线询问。

输入格式
第一行一个数 n,m,q 表示景点个数、游客中心个数和询问数。 接下来 n-1 行每行两个数 x,y,表示 x 和 y 景点有一条双向边。 接下来 m 行每行 2 个数 x,y,x 表示存在游客中心的景点编号,y 表示以 x 景点为根的子树中的所有景点纪念品价值总和。 每个景点的 纪念品价值都是非负数。

接下来 q 行,每行 2 个数 x,y,询问从 x 走到 y 的途中 Gy 的最 大花费和最小花费。

输出格式
Q 行,每行 2 个数,分别表示每个询问的最大花费和最小花费。

输入样例
323 12 13 17 23 22 21 13

输出样例
33 73 44

数据范围
二十个数据点,各个点的具体情况如下:

数据编号 1~2 3~4 5~6 7 8 9~10 11~20

n <=30 <=1000 <=100000 <=100000 <=100000 <=100000 <=100000

m <=30 <=1000 <=500 <=1 <=100000 <=100000 <=100000

q <=30 <=1000 <=100000 <=100000 <=1 <=100000 <=100000

注释

这是链


相关文章:
杭州学军中学NOIP2011模拟赛DAY2-2011-10-5
10页 免费如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处进行反馈。 杭州学军中学NOIP2011模拟赛DAY2-2011-10-5 隐藏>> NOIP2011...
2011年杭州学军中学高考模拟考试文科综合
2011杭州学军中学高考模拟考试 文科综合试卷本试卷分第Ⅰ卷和第Ⅱ卷两部分。...(10 分) 文科综合参考答案一、选择题 1.D 2.A 3.A 4.B 5.B 6.D 7...
(30)2011学年杭州学军中学第十次月考数学(理科)试题卷2012.5
瑞安市第六中学 2012 届高考模拟试卷(30) 2011 学年杭州学军中学第十次月考数学...1 (C) 5 ?1 2 )(D) 2 2 ?1 2 10.已知函数 f ( x ) ? x x ...
浙江省杭州学军中学2011届高三上学期第二次月考(政治)
浙江省金丽衢十二校2011届... 10页 免费 浙江省杭州学军中学2012届... 10...(5 分) (2)你认为我们中学生应该树立怎样的消费观?(5 分) 63.((5 63.(...
浙江省杭州学军中学2011届高三第一次月考 政治
9页 免费 2011学杭州学军中学高三... 10页 5财富值如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处进行反馈。 ...
2011年学军中学高三理科综合能力模拟试卷(5月19日)
2011年学军中学5月高考模拟... 7页 免费 浙江省杭州学军中学2012届... 22...与坐标值 x 的关系如下表格所示: 1 x/m φ/10 v 5 2 0.10 4.50 3 ...
浙江省杭州学军中学10-11学年高二英语下学期期中考试
浙江省杭州学军中学10-11学... 13页 5财富值 浙江省杭州二中2010-2011学.....杭州学军中学2010/2011学年下学期期中考试高二年级英语试卷 杭州学军中学2010/2011...
NOIP2011初赛模拟训练题
sxzjq123贡献于2011-10-13 0.0分 (0人评价)暂无用户评价 我要评价 ...26页 5财富值 四十六中2011NOIP模拟试题... 9页 2财富值 (信息学奥赛辅导...
NOIP2011复赛模拟题Day2
杭州学军中学NOIP2011模... 8页 免费喜欢此文档的...NOIP2011 复赛模拟Day2 题目名称 时间限制 空间...5 5 9 11 11 7 3 2 6 2 2 3 4 3 输出:...
杭州学军中学2期中考试试题
mfr991017贡献于2011-03-21 0.0分 (0人评价)暂无...2011杭州学军中学会考模拟 10页 5财富值 杭州学军...7页 2财富值如要投诉违规内容,请到百度文库投诉中心...
更多相关标签:
noip2011day2 | noip2011提高组day2 | noip2015提高组day2 | noip2016day2 | noip2016提高组day2 | noip2015 day2 | noip2015day2解题报告 | noip2014提高组day2 |