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

杭州学军中学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提高组初赛试题及答案C++版
第十七届全国青少年信息学奥林匹克联赛初赛试题( 提高组 C++语言 两小时完成 ) ...4 6 1 2 10 2 3 20 3 4 30 NOIP2011 初赛 提高组 C++ 5 4 1 40 ...
冲刺noip2011模拟试题
冲刺NOIP 2011 模拟试题题目 失落的神庙 失落的猴子...[n div 2]+F[n div 3]+F[n div 5]+F[n...10 数据范围: 40%的数据 n<=100,m<=100,k<=...
noip2011初赛试题及答案(完美Word版)
第十七届全国青少年信息学奥林匹克联赛初赛试题( 提高...——江郎 2011-10-25 13 CCF NOIP2011 提高组(...1 CD 2 ABCD 3 AB 4 BC 5 BC 6 ABD 7 CD...
杭州学军中学2期中考试试题
mfr991017贡献于2011-03-21 0.0分 (0人评价)暂无...2011杭州学军中学会考模拟 10页 5财富值 杭州学军...7页 2财富值如要投诉违规内容,请到百度文库投诉中心...
5---杭州学军中学第十次月考理科综合试题
计算机数学基础 教案 (5) 8页 2财富值 2011学杭州学军中学第十... 9页...标准状况下, 1 mol 己烷含有 NA 个分子 10、 某实验小组学生按照课本实验要求...
浙江省杭州学军中学2011届高三第一次月考政治试题_免费...
浙江省杭州学军中学2011届... 10页 5财富值喜欢此文档的还喜欢 浙江省学军中学2011届高三... 11页 2财富值 浙江省杭州学军中学2009届... 6页 免费 浙江省...
浙江省杭州学军中学2011高三第一次月考--历史
非选择题: 31. (1) taoti.tl100.com 你的首选资源互助社区 (2) (3) 32...2010 学年杭州学军中学高三年级第一次月考 历史答案 1-5 DCCDD 6-10 DBBCC...
2011杭州学军中学高中英语会考模拟试卷
2011 杭州学军中学高中英语会考模拟试卷第 I 卷 客观题 一. 听力(共两节, 满分 15 分) 第一节: (共 5 小题, 每小题 1 分, 满分 5 分) 听下面 5 ...
2011杭州学军中学高中英语会考模拟试卷_2
2011杭州学军中学高中英语会考模拟试卷_22011 杭州学军中学高中英语会考模拟试卷第 I 卷 客观题 一. 听力(共两节, 满分 15 分) 第一节: (共 5 小题, ...
2011杭州学军中学高中英语会考模拟试卷_3
2011 杭州学军中学高中英语会考模拟试卷第 I 卷 客观题 一. 听力(共两节, 满分 15 分) 第一节: (共 5 小题, 每小题 1 分, 满分 5 分) 听下面 5 ...
更多相关标签:
noip2011day2 | noip2016day2 | noip2015 day2 | noip2016提高组day2 | noip2015提高组day2 | noip2015day2解题报告 | noip2012day2 | noip2014提高组day2 |