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

NOIP2012提高组复赛试题


全国信息学奥林匹克联赛(NOIP2012)复赛 CCF 全国信息学奥林匹克联赛(NmP2012)复赛提高组 day2

提高组 day1

2.

1 ·同余方程

〖问题描述〗 求关于的同余方程三 1 (mod 句的最小正整数解。 输入〗 输入文件为 mod.ino 输入只有一行,包含两个正整数用一

个空格隔开 输出〗 输出文件为 mod.outo 输出只有一行,包含一个正整数№即最小正整数解。输入数据保证一定有解。 〖输入输出样例〗 mod. in 3 10 〖数据范围〗 对于 40%的数据,2 L000:对于 60%的数 据,2 50,000,000: 对于 100%的数据,2,2,000,000,000。 mod.out 7

2 ·借教室 (classroom. cpp/c/pas) 问题描述〗 在大学期间,经常需要租借教室。大到院系举办活动,小到学习小组自习讨论,都需要向学校申请借教 室。教室的大小功能不同,借教室人的身份不同,借教室的手续也不一样。 面对海量租借教室的信息,我们自然希望编程解决这个问题。 我们需要处理接下来 n 天的借教室信息,其中第 i 天学校有个教室可供租借。共有 m 份订单,每份订 单用三个正整数描述,分别为 d],斗 t},表示某租借者需要从第丬天到第 t]天租借教室(包括第丬天和第 t) 天) ,每天需要租借 dj 个教室。 我们假定,租借者对教室的大小、地点没有要求。即对于每份订单,我们只需要每天提供 d]个教室, 而它们具体是哪些教室,每天是否是相同的教室则不用考虑。 借教室的原则是先到先得,也就是说我们要按照订单的先后顺序依次为每份订单分配教室。如果在分配 的过程中遇到一份订单无法完全满足,则需要停止教室的分配,通知当前申请人修改订单。这里的无法满足 指从第丬天到第 t)天中有至少一天剩余的教室数量不足 d)个。现在我们需要知道,是否会有订单无法完全满 足。如果有,需要通知哪一个申请人修改 输入〗 输入文件为 classroom.in 第一行包含两个正整数 n,m,表示天数和订单的数量。 第 1 页共 10 页

全国信息学奥林匹克联赛(NOIP2012)复赛 第二行包含 n 个正整数,其中第 i 个数为 ri,表示第 i 天可用于租借的教室数量。

提高组 day1

接下来有 m 行,每行包含三个正整数 dJ,s],t],表示租借的数量,租借开始、结束分别在第几天。 每行相邻的两个数之间均用一个空格隔开。天数与订单均用从 1 开始的整数编号。 〖输出〗 输出文件为 classroom.outo 如果所有订单均可满足,则输出只有一行,包含一个整数 0。否则(订单无法完全满足)输出两行,第 一行输出一个负整数一 1 ,第二行输出需要修改订单的申请人编号。 〖输入输出样例〗 01 ssroom.in 2543 classroom. 00t 2

2 13 3 24 4 24
输入输出样例说明〗 第 1 份订单满足后,4 天剩余的教室数分别为 0,3,2,3。第 2 份订单要求第 2 天到第 4 天每天提供 3 个教室,而第 3 天剩余的教室数为 2,因此无法满足。分配停止,通知第 2 个申请人修改订单。 〖数据范围〗 对于 10%的数据,有 1 孓 n,m 孓 10;对于 30% 的数据,有 1 孓 n,m 孓 1000;对于 70%的数 据,有 1 孓 n,m 孓 105; 对于 100%的数据,有 1 孓 n,m 孓 106,0 孓 ri,dj 孓 109,1 < sj < tj < no

3 ·疫情控制 (blockade.cpp/c/pas 〖问题描述〗 H 国有 n 个城市,这 n 个城市用 n-l 条双向道路相互连通构成一棵树,1 号城市是首都,也是树中的根 节点。 H 国的首都爆发了一种危害性极高的传染病。当局为了控制疫清,不让疫情扩散到边境城市(叶子节点 所表示的城市) ,决定动用军队在一些城市建立检查点,使得从首都到边境城市的每一条路径上都至少有一 个检查点,边境城市也可以建立检查点。但特别要注意的是,首都是不能建立检查点的。 现在,在 H 国的一些城市中已经驻扎有军队,且一个城市可以驻扎多个军队。一支军 队可以在有道路连接的城市间移动,并在除首都以外的任意一个城市建立检查点,且只能在一个城市建立检 查点。一支军队经过一条道路从一个城市移动到另一个城市所需要的时间等于道路的长度(单位:小时) 。 请问最少需要多少个小时才能控制疫情。注意:不同的军队可以同时移动。 第 2 页共 10 页

全国信息学奥林匹克联赛(NOIP2012)复赛 〖输入〗 输入文件名为 blockade . ino 第一行一个 整数 n,表示城市个数。

提高组 day1

接下来的 n.1 行,每行 3 个整数,u、v、w,每两个整数之间用一个空格隔开,表示从城市 u 到城市 v 有一条长为 w 的道路。数据保证输入的是一棵树,且根节点编号为 1。 接下来一行一个整数 m,表示军队个数。 接下来一行 m 个整数,每两个整数之间用一个空格隔开,分别表示这 m 个军队所驻扎的城市的编号。 〖输出〗 输出文件为 b 工 ockade.outo 共一行,包含一个整数,表示控制疫情所需要的最少时间。如果无法控制疫情则输出.1。 〖输入输出样例〗 b 工 o c kade.i n 4 121 132 343 2 22 输入输出样例说明〗 第一支军队在 2 号点设立检查点,第二支军队从 2 号点移动到 3 号点设立检查点,所需时间为 3 个小 时。 〖数据范围〗 保证军队不会驻扎在首都。对于 20% 的数据,荃 10; 对于 40%的数据,2 囟 50,()w < 105;对于 60% 的数据,2 n 1000,0<w < 106:对于 80%的数 据,2 n 引 0,000; 对于 100%的数据,2 n n 50,000,()w < 109 blockade . out 3

第 3 页共 10 页

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

提高组 day1

CCF 全国信息学奥林匹克联赛(NOIP2012)复赛 提高组 day1 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 a H e b f l c n l a l o b p w c y 第 4 页共 10 页 o a o r b s l c n d a d

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

提高组 day1

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

【输入输出样例】 vigenere.in CompleteVictory Yvqgpxaimmklongnzfwpvxmniytm vigenere.out Wherethereisawillthereisaway

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

3.
【问题描述】

国王游戏

(game.cpp/c/pas)

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

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

第 5 页共 10 页

全国信息学奥林匹克联赛(NOIP2012)复赛 【输出】 输出文件名为 game.out。

提高组 day1

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

【输入输出样例】 game.in 3 game.out 2

1 1 2 3
7 4 4 6

【输入输出样例说明】按 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%的数据,保证答案不超过 109; 对于 100%的数据,有 1 ≤ n ≤1,000,0 < a、b < 10000。

4.
【问题描述】

开车旅行

(drive.cpp/c/pas)

小 A 和小 B 决定利用假期外出旅行,他们将想去的城市从 1 到 N 编号,且编号较小的城市在编号较 大的城市的西边,已知各个城市的海拔高度互不相同,记城市 i 的海拔高度为 Hi,城市 i 和城市 j 之间的 距离 d[i,j]恰好是这两个城市海拔高度之差的绝对值,即 d[i, j] = | ? |。

第 6 页共 10 页

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

提高组 day1

旅行过程中,小 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 drive.out

第 7 页共 10 页

全国信息学奥林匹克联赛(NOIP2012)复赛 4 2 3 1 4 3 4 1

提高组 day1

1 1 2 0
0 0 0 0

1 2 3 4

3 3 3 3

【输入输出样例 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 drive.out

第 8 页共 10 页

全国信息学奥林匹克联赛(NOIP2012)复赛 10 4 5 6 1 2 3 7 8 9 10 7 10 2 3 2 2 4 2 1 7 7 7 7 7 7 7 7 7 7 2 4 5 1 5 1 2 1 2 0 0 0 0 0

提高组 day1

1 2 3 4 5 6 7 8 9 10

【输入输出样例 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。

【数据范围】对于 30%的数据,有 1≤N≤20,1≤M≤20;对于 40%的数据,有 1≤N≤100,1≤M≤100;对于 50%的数据, 有 1≤N≤100,1≤M≤1,000; 对于 70%的数据,有 1≤N≤1,000,1≤M≤10,000;

第 9 页共 10 页

全国信息学奥林匹克联赛(NOIP2012)复赛 对于 100%的数据,有 1≤N≤100,000,1≤M≤10,000,-1,000,000,000≤Hi≤1,000,000,000, 0≤X0≤1,000,000,000,1≤Si≤N,0≤Xi≤1,000,000,000,数据保证 Hi 互不相同。

提高组 day1

第 10 页共 10 页


相关文章:
NOIP2012提高组复赛试题
全国信息学奥林匹克联赛(NOIP2012)复赛 CCF 全国信息学奥林匹克联赛(NmP2012)复赛提高组 day2 提高组 day1 2. 1 ·同余方程 〖问题描述〗 求关于的同余方程...
noip 2012 提高组 解题报告
noip 2012 提高组 解题报告_学科竞赛_高中教育_教育专区。noip 2012 提高组 解题报告 Vigenère 密码模拟注意大小写 var i,l,t:longint; a:Array[0..1000] ...
NOIP2012senior_day1复赛提高组
全国信息学奥林匹克联赛(NOIP2012)复赛 提高组 day1 CCF 全国信息学奥林匹克联赛(NOIP2012)复赛 提高组 day1 (请选手务必仔细阅读本页内容)一.题目概况中文题目...
NOIP2012提高组初赛及答案(Pascal)
NOIP2012提高组初赛及答案(Pascal)_学科竞赛_高中教育_教育专区。用了两天的时间...第十八届全国青少年信息学奥林匹克联赛初赛(提高组 Pascal 语言试题) 竞赛时间:...
NOIP2012 提高组初赛答案
NOIP2012 提高组初赛答案_学科竞赛_高中教育_教育专区。NOIP2012 提高组初赛答案...NOIP2012提高组初赛试题 暂无评价 19页 1下载券 NOIP2000提高组初赛答案 1页...
2012全国信息学奥林匹克联赛提高第一天试题
2012全国信息学奥林匹克联赛提高第一天试题_学科竞赛_高中教育_教育专区。这是我整理的2012NOIP复赛第一天试题完全word版全国信息学奥林匹克联赛(NOIP2012) 提高组第...
NOIP2007提高组复赛试题解题报告
NOIP2007提高组复赛试题解题报告_经济/市场_经管营销_专业资料。NOIP2007提高组复赛试题解题报告今日推荐 160份文档 四季养生 中医养生与保健 中医养生知识大全 女人...
noip2002 提高组 复赛试题及参考程序(pascal)
noip2002 提高组 复赛试题及参考程序(pascal)_高考_高中教育_教育专区。略......文档贡献者 梦中浔梦 贡献于2012-07-30 专题推荐 noip2001 提高组 复赛试.....
2009-2013年NOIP初赛提高组C++语言试题及参考答案
任何一个在(输入规模的)指数时间内能够解决的问题 5.CCF NOIP 复赛考试结束后...11 2012 第十八届全国青少年信息学奥林匹克联赛初赛 提高组 C++语言试题 (竞赛时间...
noip2004 提高组复赛试题及参考程序(pascal)
noip2004 提高组复赛试题及参考程序(pascal)_IT认证_资格考试/认证_教育专区。略...文档贡献者 梦中浔梦 贡献于2012-07-30 专题推荐 noip2001 提高组 复赛试.....
更多相关标签:
noip提高组复赛试题 | noip2012提高组复赛 | noip2016提高组复赛 | noip2015提高组复赛 | noip2014提高组复赛 | noip2010提高组复赛 | noip2016复赛试题 | noip2013提高组复赛 |