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

杭州学军中学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
NOIP2011提高组解题报告day2_理学_高等教育_教育专区。noip历届复赛试题及解析 ...第 3 个旅客旅行时间 7-5 = 2 分钟。 总时间 7+1+2 = 10 分钟。 【...
2011杭州学军中学高中英语会考模拟试卷_5
2011 杭州学军中学高中英语会考模拟试卷第 I 卷 客观题 一. 听力(共两节, ...2011杭州学军中学会考模... 102下载券 杭州学军中学NOIP2011模... 5...
NOIP2011初赛C提高组参考答案
CCF NOIP2011 提高组(C 语言)参考答案与评分标准一、单项选择题(共 10 题,每题 1.5 分,共计 15 分) 1 B 2 B 3 A 4 D 5 B 6 A 7 C 8 D 9 ...
noip2011初赛试题及答案(完美Word版)
第十七届全国青少年信息学奥林匹克联赛初赛试题( 提高...——江郎 2011-10-25 13 CCF NOIP2011 提高组(...1 CD 2 ABCD 3 AB 4 BC 5 BC 6 ABD 7 CD...
第十七届NOIP2011 提高组初赛试题及答案解析
第十七届NOIP2011 提高组初赛试题及答案解析_计算机...更新为:SA=2,SB=5,SC=4,SD=3 答案:BCD 10....模拟一下,发现是隔一个输出一个的斐波那契数列,注意...
NOIP2011复赛模拟01
NOIP2011复赛模拟01_IT认证_资格考试/认证_教育专区。NOIP2011 复赛模拟 01 汪...1*13+2*9+3*4+4*0+5*3+6*5+7*14+8*20+9*18+ 10*1+11*12 =...
浙江省杭州学军中学2011高三第一次月考--历史
浙江省杭州学军中学2011高三第一次月考--历史浙江省杭州学军中学2011高三第一次...2010 学年杭州学军中学高三年级第一次月考 历史答案 1-5 DCCDD 6-10 DBBCC...
浙江省杭州学军中学10-11学年高二上学期期中试题 生物 ...
10页 5财富值 浙江省杭州学军中学2011届... 13页...浙江省杭州二中2010-2011学... 7页 免费 浙江省杭州...A.1∶2 B.2∶1 C.3∶1 D.1∶1 38.右图...
浙江省杭州学军中学10-11学年高二生物上学期期中试题浙...
1/2 相关文档推荐 浙江省杭州学军中学2011届... 13页 5财富值 浙江省杭州...浙江省杭州二中2010-2011学... 7页 免费 浙江省杭州二中10-11学年高... 8...
浙江省杭州学军中学2011届高三第一次月考 生物
浙江省杭州学军中学2011届... 10页 5财富值喜欢此文档的还喜欢 精 浙江省杭州...1 - 30 题每 题 1 分, 3131 - 40 题每题 2 分,共 50 分) 1.经测...
更多相关标签:
noip2011 day2 | noip2011 day2 题解 | noip2011day2观光公交 | noip2016day2 | noip2013 day2 | noip2012day2 | noip2015day2解题报告 | noip2012day2疫情控制 |