tceic.com
学霸学习网 这下你爽了
相关标签
当前位置:首页 >> 学科竞赛 >>

2012全国信息学奥林匹克联赛提高第一天试题


全国信息学奥林匹克联赛(NOIP2012)

提高组第一天试题

NOIP2012复赛提高组第一天
(请选手务必仔细阅读本页内容) 一.题目概况
中文题目 英文题目与子目录名 可执行文件名 输入文件名 输出文件名 每个测试点时限 测试点数目 每个测试点分值 附加样例文件 结果比较方式 题目类型
Vigenere 密码

国王游戏 game game game.in game.out 1秒 10 10 有 传统

开车旅行 drive drive drive.in drive.out 1秒 20 5 有 传统

vigenere vigenere vigenere.in vigenere.out 1秒 10 10 有 传统

全文比较(过滤行末空格及文末回车)

二、提交源程序文件名
对于C++语言 对于 C 语言 对于pascal语言 vigenere.cpp vigenere.c vigenere.pas game.cpp game.c game.pas drive.cpp drive.c drive r.pas

三.编译命令(不包含任何优化开关)
对于C++语言 对于 C 语言 对于pascal语言 g++ -o vigenere gcc -o vigenere vigenere.c -lm
fpc vigenere.pas

g++ -o game gcc -o game game .c -lm
fpc game.pas

g++ -o drive gcc -o drive drive.c -lm
fpc drive.pas

vigenere.cpp -lm game.cpp -lm drive .cpp -lm

四.运行内存限制 注意事项:

128M

128M

128M

1、 文件名(程序名和输入输出文件名)必须使用英文小写。 2、C/C++中函数 main()的返回值类型必须是 int,程序正常结束时的返回值必须是 0。 3、全国统一评测时采用的机器配置为:CPU Intel Core2 Quad Q8200 2.33GHz,内存 2G, 上述时限以此配置为准。 4、特别提醒:评测在 NOI Linux 下进行。
第 1 页 共 7 页

全国信息学奥林匹克联赛(NOIP2012)

提高组第一天试题

1. Vigenère密码
(vigenere.cpp/c/pas)

【问题描述】
16世纪法国外交家Blaise de Vigenère设计了一种多表密码加密算法——Vigenère密 码。Vigenère密码的加密解密算法简单易用,且破译难度比较高,曾在美国南北战争中为南 军所广泛使用。 在密码学中,我们称需要加密的信息为明文,用M表示;称加密后的信息为密文,用C 表示;而密钥是一种参数,是将明文转换为密文或将密文转换为明文的算法中输入的数据, 记为k。在Vigenère密码中,密钥k是一个字母串,k=k1k2…kn。当明文M=m1m2…mn时,得到 的密文C=c1c2…cn,其中ci=mi?ki,运算?的规则如下表所示:

Vigenère加密在操作时需要注意: 1. ?运算忽略参与运算的字母的大小写,并保持字母在明文M中的大小写形式; 2. 当明文M的长度大于密钥k的长度时,将密钥k重复使用。 例如,明文M=Helloworld,密钥k=abc时,密文C=Hfnlpyosnd。 明文 H e l l o w o r l d 密钥 a b c a b c a b c a 密文 H f n l p y o s n d
第 2 页 共 7 页

全国信息学奥林匹克联赛(NOIP2012)

提高组第一天试题

【输

入】

输入文件名为 vigenere.in。 输入共2行。 第一行为一个字符串,表示密钥k,长度不超过100,其中仅包含大小写字母。第二行为 一个字符串,表示经加密后的密文,长度不超过1000,其中仅包含大小写字母。

【输

出】

输出文件名为 vigenere.out。 输出共1行,一个字符串,表示输入密钥和密文所对应的明文。

【样

例】
vigenere.in CompleteVictory Yvqgpxaimmklongnzfwpvxmniytm vigenere.out Wherethereisawillthereisaway

【数据说明】
对于100%的数据,输入的密钥的长度不超过100,输入的密文的长度不超过1000,且都 仅包含英文字母。

2.国王游戏
(game.cpp/c/pas)

【问题描述】
恰逢H国国庆,国王邀请n位大臣来玩一个有奖游戏。首先,他让每个大臣在左、右手上 面分别写下一个整数, 国王自己也在左、 右手上各写一个整数。 然后, 让这n位大臣排成一排, 国王站在队伍的最前面。排好队后,所有的大臣都会获得国王奖赏的若干金币,每位大臣获 得的金币数分别是:排在该大臣前面的所有人的左手上的数的乘积除以他自己右手上的数, 然后向下取整得到的结果。 国王不希望某一个大臣获得特别多的奖赏, 所以他想请你帮他重新安排一下队伍的顺序, 使得获得奖赏最多的大臣,所获奖赏尽可能的少。注意,国王的位置始终在队伍的最前面。

【输

入】

输入文件为 game.in。 第一行包含一个整数n,表示大臣的人数。 第二行包含两个整数a和b,之间用一个空格隔开,分别表示国王左手和右手上的整数。 接下来n行,每行包含两个整数a和b,之间用一个空格隔开,分别表示每个大臣左手和右
第 3 页 共 7 页

全国信息学奥林匹克联赛(NOIP2012)

提高组第一天试题

手上的整数。

【输

出】

输出文件名为 game.out。 输出只有一行,包含一个整数,表示重新排列后的队伍中获奖赏最多的大臣所获得的金 币数。

【样

例】
game.in game.out
3 11 23 74 46 2

【样例说明】
按1、2、3号大臣这样排列队伍,获得奖赏最多的大臣所获得金币数为2; 按1、3、2这样排列队伍,获得奖赏最多的大臣所获得金币数为2; 按2、1、3这样排列队伍,获得奖赏最多的大臣所获得金币数为2; 按2、3、1这样排列队伍,获得奖赏最多的大臣所获得金币数为9; 按3、1、2这样排列队伍,获得奖赏最多的大臣所获得金币数为2; 按3、2、1这样排列队伍,获得奖赏最多的大臣所获得金币数为9。 因此,奖赏最多的大臣最少获得2个金币,答案输出2。

【数据范围】
对于20%的数据,有1≤n≤10,0 < a、b <8; 对于40%的数据,有1≤n≤20,0 < a、b < 8; 对于60%的数据,有1≤n≤100; 对于60%的数据,保证答案不超过10 ; 对于100%的数据,有1 ≤n ≤1,000,0 < a、b < 10000。
9

3.开车旅行 (drive.cpp/c/pas)
【问题描述】
小A和小B决定利用假期外出旅行,他们将想去的城市从1到N编号,且编号较小的城市在 编号较大的城市的西边,已知各个城市的海拔高度互不相同,记城市i的海拔高度为Hi,城市
第 4 页 共 7 页

全国信息学奥林匹克联赛(NOIP2012)

提高组第一天试题

i和城市j之间的距离d[i,j]恰好是这两个城市海拔高度之差的绝对值,即d[i,j]=|Hi? Hj|。 旅行过程中,小A和小B轮流开车,第一天小A开车,之后每天轮换一次。他们计划选择一 个城市S作为起点,一直向东行驶,并且最多行驶X公里就结束旅行。小A和小B的驾驶风格不 同,小B总是沿着前进方向选择一个最近的城市作为目的地,而小A总是沿着前进方向选择第 二近的城市作为目的地(注意:本题中如果当前城市到两个城市的距离相同,则认为离海拔 低的那个城市更近) 。如果其中任何一人无法按照自己的原则选择目的城市,或者到达目的地 会使行驶的总距离超出X公里,他们就会结束旅行。 在启程之前,小A想知道两个问题: 1.对于一个给定的X=X0,从哪一个城市出发,小A开车行驶的路程总数与小B行驶的路程 总数的比值最小(如果小B的行驶路程为0,此时的比值可视为无穷大,且两个无穷大视为相 等) 。如果从多个城市出发,小A开车行驶的路程总数与小B行驶的路程总数的比值都最小,则 输出海拔最高的那个城市。 2.对任意给定的X=Xi和出发城市Si,小A开车行驶的路程总数以及小B行驶的路程总数。

【输

入】

输入文件drive.in。 第一行包含一个正整数N,表示城市的数目。 第二行有N个整数, 每两个整数之间用一个空格隔开, 依次表示城市1到城市N的海拔高度, 即H1,H2,……,Hn,且每个Hi都是不同的。 第三行包含一个整数X0。 第四行为一个整数M,表示给定M组Si和Xi。 接下来的M行,每行包含2个整数Si和Xi,表示从城市Si出发,最多行驶Xi公里。

【输

出】

输出文件名为drive.out。 输出共M+1行。 第一行包含一个整数S0,表示对于给定的X0,从编号为S0的城市出发,小A开车行驶的路 程总数与小B行驶的路程总数的比值最小。 接下来的M行,每行包含2个整数,之间用一个空格隔开,依次表示在给定的Si和Xi下小A 行驶的里程总数和小B行驶的里程总数。

【样 例 1】
drive.in
第 5 页

drive.out
共 7 页

全国信息学奥林匹克联赛(NOIP2012)

提高组第一天试题

4 2 3 4 1 2 3 4

3 1 4

3 3 3 3

1 1 2 0 0

1 0 0 0

【样例1说明】

各个城市的海拔高度以及两个城市间的距离如上图所示。 如果从城市1出发,可以到达的城市为2,3,4,这几个城市与城市1的距离分别为1,1,2, 但是由于城市3的海拔高度低于城市2,所以我们认为城市3离城市1最近,城市2离城市1第二 近,所以小A会走到城市2。到达城市2后,前面可以到达的城市为3,4,这两个城市与城市2 的距离分别为2,1,所以城市4离城市2最近,因此小B会走到城市4。到达城市4后,前面已没 有可到达的城市,所以旅行结束。 如果从城市2出发,可以到达的城市为3,4,这两个城市与城市2的距离分别为2,1,由于 城市3离城市2第二近,所以小A会走到城市3。到达城市3后,前面尚未旅行的城市为4,所以 城市4离城市3最近,但是如果要到达城市4,则总路程为2+3=5>3,所以小B会直接在城市3结 束旅行。 如果从城市3出发,可以到达的城市为4,由于没有离城市3第二近的城市,因此旅行还未 开始就结束了。 如果从城市4出发,没有可以到达的城市,因此旅行还未开始就结束了。

【样 例 2】
drive.in 10 4 5 6 1 2 3 7 8 9 10 7 10
第 6 页

drive.out 2 3 2 2 4 2 1
共 7 页

全国信息学奥林匹克联赛(NOIP2012)

提高组第一天试题

17 27 37 47 57 67 77 87 97 10 7

2 5 5 2 2 0 0

4 1 1 1 0 0 0

【样例2说明】
当X=7时, 如果从城市1出发,则路线为1 -> 2 -> 3 -> 8 -> 9,小A走的距离为1+2=3,小B走的距 离为1+1=2。 (在城市1时,距离小A最近的城市是2和6,但是城市2的海拔更高,视为与城市1 第二近的城市,所以小A最终选择城市2;走到9后,小A只有城市10可以走,没有第2选择可以 选,所以没法做出选择,结束旅行) 如果从城市2出发,则路线为2 -> 6 -> 7 ,小A和小B走的距离分别为2,4。 如果从城市3出发,则路线为3 -> 8 -> 9,小A和小B走的距离分别为2,1。 如果从城市4出发,则路线为4 -> 6 -> 7,小A和小B走的距离分别为2,4。 如果从城市5出发,则路线为5 -> 7 -> 8 ,小A和小B走的距离分别为5,1。 如果从城市6出发,则路线为6 -> 8 -> 9,小A和小B走的距离分别为5,1。 如果从城市7出发,则路线为7 -> 9 -> 10,小A和小B走的距离分别为2,1。 如果从城市8出发,则路线为8 -> 10,小A和小B走的距离分别为2,0。 如果从城市9出发,则路线为9,小A和小B走的距离分别为0,0(旅行一开始就结束了) 。 如果从城市10出发,则路线为10,小A和小B走的距离分别为0,0。 从城市2或者城市4出发小A行驶的路程总数与小B行驶的路程总数的比值都最小,但是城 市2的海拔更高,所以输出第一行为2。

【数据范围】
对于20%数据,有0<n≤8,0<m≤8,0≤ai≤8; 对于50%数据,有0<n≤20,0<m≤20,0≤ai≤20; 对于100%数据,有0<n≤100,0<m≤100,0≤ai≤100。

第 7 页

共 7 页


推荐相关:

NOIP2012提高组复赛试题_图文

? ???|。 第 6 页共 10 页 全国信息学奥林匹克联赛(NOIP2012)复赛 提高组 day1 旅行过程中,小 A 和小 B 轮流开车,第一天小 A 开车,之后每天轮换一次...


1995-2012历年全国青少年信息学奥林匹克联赛初赛试题(...

青​少​年​信​息​学​奥​林​匹​克​联​赛​初...第六届全国青少年信息学(计算机)奥林匹克分区联赛初赛试题普及组参考答案 一、...


2012少年信息学奥林匹克联赛初赛C试题

2012少年信息学奥林匹克联赛初赛C试题_学科竞赛_小学教育_教育专区。第十八届全国青少年信息学奥林匹克联赛初赛(普及组 C 语言两小时完成) ●● 全部试题答案均要求...


NOIP2011提高组_第一天_Day1试题

2012全国信息学奥林匹克联... 7页 1财富值 NOIP2012提高组day2试题 4页 5...NOIP2011提高组_第一天_Day1试题 隐藏>> 全国信息学奥林匹克联赛(NOIP2011)复赛...


NOIP2012信息学奥林匹克竞赛初赛-模拟卷

NOIP2012信息学奥林匹克竞赛初赛-模拟卷_学科竞赛_高中教育_教育专区。NOIP2012信息学奥林匹克竞赛初赛-模拟卷2012全国青少年信息学奥林匹克联赛初赛模拟试题一.单...


2012年义乌市小学信息学奥林匹克竞赛试题(附答案)

不能 用画图直接打开 第9题 第 10 题 Fireworks 是图像处理软件 DCCBB 6/7 2012 年义乌市小学信息学奥林匹克竞赛试题 第 11 题第 12 题算法具有五个基本...


2016第22届全国信息学奥林匹克联赛提高组复试二试真题_...

2016第22届全国信息学奥林匹克联赛提高组复试二试真题_IT认证_资格考试/认证_教育专区。2016 第 22 届全国信息学奥林匹克联赛提高组复试二试真题 2016 第 22 ...


2012信息学奥林匹克程序设计普及组初赛试卷及答案pasca...

2012信息学奥林匹克程序设计普及组初赛试卷及答案pascal版_军事/政治_人文社科_专业资料。第十八届全国青少年信息学奥林匹克联赛初赛普及组 Pascal 语言试题竞赛时间:2...


2012年长沙市小学生信息学奥林匹克竞赛初赛试题

2012 年长沙市小学生信息学奥林匹克竞赛初赛试题一、单项选择题(每小题 2 分,共 40 分) 1.目前获得世界计算机科学最高奖——“图灵奖”唯一的华人是( ) A...


CCF全国信息学奥林匹克联赛

CCF全国信息学奥林匹克联赛_学科竞赛_初中教育_教育专区。CCF NOIP2012普及组复赛试卷CCF 全国信息学奥林匹克联赛(NOIP2012)复赛 普及组(请选手务必仔细阅读本页内容...

网站首页 | 网站地图
All rights reserved Powered by 学霸学习网 www.tceic.com
copyright ©right 2010-2021。
文档资料库内容来自网络,如有侵犯请联系客服。zhit325@126.com