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

noi网上同步赛 试2 noi2014


第 31 届全国信息学奥林匹克竞赛

CCF NOI 2014
第二试
竞赛时间:2014 年 7 月 29 日 8:00-13:00
题目名称 目录 可执行文件名 输入文件名 输出文件名 每个测试点时限 内存限制 测试点数目 每个测试点分值 是否有部分分 题目类型 是否有附加文件 动物园 zoo zoo zoo.in zoo.o

ut 1秒 512MB 10 10 否 传统型 是 随机数生成器 random random random.in random.out 5秒 256MB 10 10 否 传统型 是 购票 ticket ticket ticket.in ticket.out 3秒 512MB 10 10 否 传统型 是

提交源程序须加后缀 对于 Pascal 语言 zoo.pas 对于 C 语言 zoo.c 对于 C++ 语言 zoo.cpp

random.pas random.c random.cpp

ticket.pas ticket.c ticket.cpp

注意:最终测试时,所有编译命令均不打开任何优化开关。

第 31 届全国信息学奥林匹克竞赛

第二试 动物园

动物园
【问题描述】 近日,园长发现动物园中好吃懒做的动物越来越多了。例如企鹅,只会卖萌 向游客要吃的。 为了整治动物园的不良风气,让动物们凭自己的真才实学向游客 要吃的,园长决定开设算法班,让动物们学习算法。 某天,园长给动物们讲解 KMP 算法。 园长: “对于一个字符串 S,它的长度为 L。我们可以在 O(L)的时间内,求 出一个名为 next 的数组。有谁预习了 next 数组的含义吗?” 熊猫: “对于字符串 S 的前 i 个字符构成的子串,既是它的后缀又是它的前 缀的字符串中(它本身除外) ,最长的长度记作 next[i]。 ” 园长: “非常好!那你能举个例子吗?” 熊猫: “例 S 为 abcababc,则 next[5]=2。因为 S 的前 5 个字符为 abcab,ab 既是它的后缀又是它的前缀, 并且找不到一个更长的字符串满足这个性质。 同理, 还可得出 next[1] = next[2] = next[3] = 0,next[4] = next[6] = 1,next[7] = 2,next[8] = 3。 ” 园长表扬了认真预习的熊猫同学。随后,他详细讲解了如何在 O(L)的时间 内求出 next 数组。 下课前,园长提出了一个问题: “KMP 算法只能求出 数组。我现在希望 求出一个更强大 num 数组——对于字符串 的前 个字符构成的子串, 既是它的 后缀同时又是它的前缀, 并且该后缀与该前缀不重叠,将这种字符串的数量记作 num[i]。例如 S 为 aaaaa,则 num[4] = 2。这是因为 S 的前 4 个字符为 aaaa,其中 a 和 aa 都满足性质 ‘既是后缀又是前缀’ , 同时保证这个后缀与这个前缀不重叠。 而 aaa 虽然满足性质‘既是后缀又是前缀’ ,但遗憾的是这个后缀与这个前缀重 叠了,所以不能计算在内。同理,num[1] = 0,num[2] = num[3] = 1,num[5] = 2。 ” 最后,园长给出了奖励条件,第一个做对的同学奖励巧克力一盒。听了这句 话,睡了一节课的企鹅立刻就醒过来了!但企鹅并不会做这道题,于是向参观动 物园的你寻求帮助。你能否帮助企鹅写一个程序求出 num 数组呢?
特别地,为了避免大量的输出,你不需要输出 num[i] 分别是多少,你只需要输出 ∏ =1([] + 1) 对 1,000,000,007 取模的结果即可。 其中∏ =1([] + 1) = ([1] + 1) × ([2] + 1) × ? × ([] + 1)。

【输入格式】 从文件 zoo.in 中读入数据。 输入文件的第 1 行仅包含一个正整数 n ,表示测试数据的组数。 随后 n 行,每行描述一组测试数据。每组测试数据仅含有一个字符串 S,S 的定义详见题目描述。数据保证 S 中仅含小写字母。 输入文件中不会包含多余的空行,行末不会存在多余的空格。

第2页

共9页

第 31 届全国信息学奥林匹克竞赛

第二试 动物园

【输出格式】 输出到文件 zoo.out 中。 输出文件应包含 行, 每行描述一组测试数据的答案, 答案的顺序应与输入 数据的顺序保持一致。对于每组测试数据,仅需要输出一个整数,表示这组测试 数据的答案对 1,000,000,007 取模的结果。 输出文件中不应包含多余的空行。 【样例输入 1】 3 aaaaa ab abcababc 【样例输出 1】 36 1 32 【样例输入输出 2】 见选手目录下的 zoo/zoo.in 与 zoo/zoo.ans。 【数据规模与约定】 所有测试点的范围和特点如下表所示

测试点编号 1 2 3 4 5 6 7 8 9 10

约定 ≤ 5, ≤ 50 ≤ 5, ≤ 200 ≤ 5, ≤ 200 ≤ 5, ≤ 10,000 ≤ 5, ≤ 10,000 ≤ 5, ≤ 100,000 ≤ 5, ≤ 200,000 ≤ 5, ≤ 500,000 ≤ 5, ≤ 1,000,000 ≤ 5, ≤ 1,000,000

第3页

共9页

第 31 届全国信息学奥林匹克竞赛

第二试 随机数生成器

随机数生成器
【问题描述】 小 H 最近在研究随机算法。 随机算法往往需要通过调用随机数生成函数 (例 如 Pascal 中的 random 和 C/C++中的 rand)来获得随机性。事实上,随机数生成 函数也并不是真正的“随机” ,其一般都是利用某个算法计算得来的。 比如,下面这个二次多项式递推算法就是一个常用算法: 算法选定非负整数 0 , , , , 作为随机种子,并采用如下递推公式进行计 算。 对于任意 ≥ 1,
2 = ( ? ?1 + ? ?1 + ) mod

这样可以得到一个任意长度的非负整数数列{ }≥1 ,一般来说,我们认为这 个数列是随机的。 利用随机序列{ }≥1 , 我们还可以采用如下算法来产生一个 1 到 K 的随机排 列{ }=1 : 1、初始设 T 为 1 到 K 的递增序列; 2、对 T 进行 K 次交换,第 次交换,交换 和 ( mod )+1 的值。 此外,小 H 在这 次交换的基础上,又额外进行了 次交换操作,对于第 次额外交换,小 H 会选定两个下标 和 ,并交换 和 的值。 为了检验这个随机排列生成算法的实用性,小 H 设计了如下问题: 小 H 有一个 行 列的棋盘,她首先按照上述过程,通过 × + 次交 换操作, 生成了一个 1~ × 的随机排列 { }× 然后将这 × 个数逐行逐 =1 , 列依次填入这个棋盘:也就是第 行第 列的格子上所填入的数应为 (?1)?+ 。 接着小 H 希望从棋盘的左上角,也就是第一行第一列的格子出发,每次向 右走或者向下走, 在不走出棋盘的前提下, 走到棋盘的右下角, 也就是第 行第 列的格子。 小 H 把所经过格子上的数字都记录了下来, 并从小到大排序, 这样, 对于任 何一条合法的移动路径,小 H 都可以得到一个长度为 + ? 1 的升序序列, 我们称之为路径序列。 小 H 想知道,她可能得到的字典序最小的路径序列应该是怎样的呢? 【输入格式】 从文件 random.in 中读入数据。 输入文件的第 1 行包含 5 个整数,依次为 0 , , , , ,描述小 H 采用的随 机数生成算法所需的随机种子。 第 2 行包含三个整数 , , , 表示小 H 希望生成一个 1 到 × 的排列来 填入她 行 列的棋盘, 并且小 H 在初始的 × 次交换操作后, 又进行了 次额外的交换操作。 接下来 行, 第 行包含两个整数 , , 表示第 次额外交换操作将交换
第4页 共9页

第 31 届全国信息学奥林匹克竞赛

第二试 随机数生成器

和 的值。 【输出格式】 输出到文件 random.out 中。 输出一行, 包含 + ? 1 个由空格隔开的正整数,表示可以得到的字典序 最小的路径序列。 【样例输入 1】 1 3 1 9 4 3 5 1 71 4 3 7 9 9

【样例输出 1】 1 2 6 8 9 12 【样例输入 2】 654321 209 111 23 70000001 10 10 0 【样例输出 2】 1 3 7 10 14 15 16 21 23 30 44 52 55 70 72 88 94 95 97 【样例输入 3】 123456 137 701 101 10000007 20 20 0 【样例输出 3】 1 10 12 14 16 26 32 38 44 46 61 81 84 101 126 128 135 140 152 156 201 206 237 242 243 253 259 269 278 279 291 298 338 345 347 352 354 383 395 【样例说明】 对于样例 1,根据输入的随机种子,小 H 所得到的前 12 个随机数 为: 9 5 30 11 64 42 36 22 1 9 5 30 根据这 12 个随机数,小 H 在进行初始的 12 次交换操作后得到的排列为:
第5页 共9页

第 31 届全国信息学奥林匹克竞赛

第二试 随机数生成器

6 9 1 4 5 11 12 2 7 10 3 8 在进行额外的 3 次交换操作之后,小 H 得到的最终的随机排列为: 12 9 1 7 5 11 6 2 4 10 3 8 12 9 1 这个随机排列可以得到如右侧的棋盘: 最 优 路 径 依 次 经 过 的 数 字 为 : 12?9?1?6?2?8。 5 11 6

7 2

4 10 3 8 对于样例 3, 由于卷面宽度不够, 在样例输出中出 现了换行。 请注意, 这里的换行仅作展示用途, 事实上, 样例输出有且仅有一行, 所有的数字都应该出现在同一行中。 【样例输入输出 4】 见选手目录下的 random/random.in 与 random/random.ans。 【数据规模与约定】 所有测试数据的范围和特点如下表所示 测试点编号 , 的规模 的规模 约定 1 2 ≤ , ≤ 8 2 = 0 2 ≤ , ≤ 200 0 ≤ ≤ 300 3 4 0 ≤ , ≤ 108 5 2 ≤ , ≤ 2000 6 0 ≤ 0 < ≤ 108 7 0 ≤ ≤ 50000 8 1 ≤ , ≤ × 2 ≤ , ≤ 5000 9 10 【特别提示】 本题的空间限制是 256 MB,请务必保证提交的代码运行时所使用的总内存 空间不超过此限制。 一个 32 位整数(例如 C/C++中的 int 和 Pascal 中的 Longint)为 4 字节,因 而如果在程序中声明一个长度为 1024 × 1024 的 32 位整型变量的数组,将会占 用 4 MB 的内存空间。

第6页

共9页

第 31 届全国信息学奥林匹克竞赛

第二试 购票

购票
【问题描述】 今年夏天, NOI 在 SZ 市迎来了她 30 周岁的生日。 来自全国 个城市的 OIer 们都会从各地出发,到 SZ 市参加这次盛会。 全国的城市构成了一棵以 SZ 市为根的有根树,每个城市与它的父亲用道路 连接。为了方便起见,我们将全国的 个城市用 1 到 的整数编号。其中 SZ 市 的编号为 1。对于除 SZ 市之外的任意一个城市 ,我们给出了它在这棵树上的 父亲城市 以及到父亲城市道路的长度 。 从城市 前往 SZ 市的方法为: 选择城市 的一个祖先 , 支付购票的费用, 乘坐交通工具到达 。再选择城市 的一个祖先 ,支付费用并到达 。以此类 推,直至到达 SZ 市。 对于任意一个城市 ,我们会给出一个交通工具的距离限制 。对于城市 的祖先 , 只有当它们之间所有道路的总长度不超过 时, 从城市 才可以通过 一次购票到达城市 ,否则不能通过一次购票到达。对于每个城市 ,我们还会 给出两个非负整数 , 作为票价参数。若城市 到城市 所有道路的总长度为 ,那么从城市 到城市 购买的票价为 + 。 每个城市的 OIer 都希望自己到达 SZ 市时,用于购票的总资金最少。你的任 务就是,告诉每个城市的 OIer 他们所花的最少资金是多少。 【输入格式】 从文件 ticket.in 中读入数据。 输入文件的第 1 行包含 2 个非负整数 , ,分别表示城市的个数和数据类型 (其意义将在后面提到) 。 输入文件的第 2 到 行,每行描述一个除 SZ 之外的城市。其中第 行包含 5 个非负整数 分别表示城市 的父亲城市, 它到父亲城市道路的 , , , , , 长度,票价的两个参数和距离限制。 请注意:输入不包含编号为 1 的 SZ 市,第 2 行到第 行分别描述的是城市 2 到城市 。 【输出格式】 输出到文件 ticket.out 中。 输出包含 ? 1 行, 每行包含一个整数。 其中第 行表示从城市 + 1 出发, 到达 SZ 市最少的购票费用。 同样请注意:输出不包含编号为 1 的 SZ 市。 【样例输入 1】 7 3 1 2 20 0 3
第7页 共9页

第 31 届全国信息学奥林匹克竞赛

第二试 购票

1 2 2 3 4

5 4 9 5 4

10 100 5 10 10 10 1 100 10 20 100 10 20 0 10

【样例输出 1】 40 150 70 149 300 150 【样例说明 1】 样例如右图所示。 从每个城市出发到达 SZ 的路线如下 (其中箭头表示一 次直达) : 城市 2: 只能选择 2 → 1, 花费为 2 × 20 + 0 = 40。 城市 3: 只能选择 3 → 1, 花费为 5 × 10 + 100 = 150。 城市 4:由于 4+2 = 6 ≤ 4 = 10, 故可以选择 4 → 1。 若选择 4 → 1, 花费为 (4 + 2) × 10 + 10 = 70 ; 若 选 择 4 → 2 → 1 , 则 花 费 为 (4 × 10 + 10) + (2 × 20 + 0) = 90;因此选择 4 → 1。 城市 5:只能选择 5 → 2 → 1 , 花 费 为 (9 × 1 + 100) + (2 × 20 + 0) = 149; 无 法 选 择 5 → 1 , 因 为 5 = 10,而城市 5 到城市 1 总路程为 9 + 2 = 11 > 5 ,城市 5 不能直达城市 1。 城市 6:若选择 6 → 1,花费为 (5 + 5) × 20 + 100 = 300;若选择 6 → 3 → 1,花费为 (5 × 20 + 100) + (5 × 10 + 100) = 350;因此选择 6 → 1。 城市 7: 选择 7 → 4 → 1, 花费为 (4 × 20 + 0) + ((4 + 2) × 10 + 10) = 150; 其他方案均比该方案差。

第8页

共9页

第 31 届全国信息学奥林匹克竞赛

第二试 购票

【样例输入输出 2】 见选手目录下的 ticket/ticket.in 与 ticket/ticket.ans。 该组样例按照城市的编号几乎平均地被分为了 4 个部分, 每个部分有不同的 特点。你可以使用它们进行针对性的测试。 【数据规模与约定】 对于所有测试数据,保证 0 ≤ ≤ 106 ,0 ≤ ≤ 1012 ,1 ≤ < ;保证 11 0 < ≤ ≤ 2 × 10 ,且任意城市到 SZ 市的总路程长度不超过 2 × 1011 。 输入的 表示数据类型,0 ≤ < 4,其中: 当 = 0 或 2 时,对输入的所有城市 ,都有 = ? 1,即所有城市构成一 个以 SZ 市为终点的链; 当 = 0 或 1 时,对输入的所有城市 ,都有 = 2 × 1011 ,即没有移动的 距离限制,每个城市都能到达它的所有祖先; 当 = 3 时,数据没有特殊性质。 每组测试数据的 和 如下所示 测试点编号 1 2 3 4 5 6 7 8 9 10 【特别提示】 最终评测时,调用栈占用的空间大小不会有单独的限制。 如果你的程序涉及 到调用栈溢出的问题,请阅读 ticket/stack.pdf。请注意,调用栈占用的空间会计 入总空间占用中,和程序其他部分占用的内存共同受到内存限制。 数据的输入输出需要用到 64 位整型。 如果你在计算中需要用到两个 64 位整 型相乘,请务必注意结果是否会溢出。 = 2 × 10 = 2 × 103 = 2 = 0 = 3 = 0 = 2 = 1 = 3

= 2 × 105

第9页

共9页


相关文章:
Noip2014初赛提高组C试题及答案(完整版)
Noip2014 初赛提高组试题及答案(完整版) 提高组 C...Oracle 3. 在 NOI 比赛中,对于程序设计题,选手...只使用两个栈结构 stack1 和 stack2,模拟对数组的...
NOIP2015普及组初赛试题及答案(Pascal)
网上聊天 11. 下面哪种软件不属于即时通信软件( )...在 NOI 系列赛事中参赛选手必须使用由承办单位统一...NOIP(2014)第十届全国... 12页 1下载券 NOIP...
NOIP2014信息学奥赛全国联赛提高组参考答案
NOIP2014信息学奥赛全国联赛提高组参考答案_学科竞赛_...第十届全国青少年信息学奥林匹克联赛初赛 提高组...省专家审定和上机验证,可以不上报CCF NOI 科学委员...
2015noi小学组初赛试题
2015noi小学组初赛试题_学科竞赛_小学教育_教育专区...网上聊天 11. 下面哪种软件不属于即时通信软件( )...第十二届“华杯赛”初赛... 2页 免费 2013希望...
NOI2014省选一试日程
NOI2014 浙江省首轮集训、选拔赛日程 日期 上午 下午 报到:13:00—18:00 ...2-1 省开课时间安排 暂无评价 8页 免费 NOI2013河北省选第一试 7页 1下载...
CCF NOI2014获奖名单
CCF NOI2014获奖名单_学科竞赛_高中教育_教育专区。CCF NOI2014获奖名单 ...CCF NOI2010网上同步赛 9页 免费 CCF精细营销 6页 免费 CCF报名表 暂无评价 ...
第二十一届(2015)全国青少年信息学奥林匹克联赛初赛试题(含答案)
NOI 系列赛事中选手必须使用由承办单位统一提供的设备,下列物品中不允许选手自 带的是( )。 A.鼠标 B.笔 C.身份证 D.准考证 二、问题求解(共 2 题,...
2016信息学竞赛 NOI 2016获奖名单
2016信息学竞赛 NOI 2016获奖名单_学科竞赛_高中教育_教育专区。CCF NOI 2016 ...武汉市第二中学 男 绍兴市第一中学 男 首都师范大学附属中学 男 天津市耀华...
NOIP2014提高组复赛试题(C语言版)
5、特别提醒 :评测在当前最新公布的 NOI Linux 下...(NOIP2014)复赛 提高组 day2 (请选手务必仔细阅读...1.无线网络发射器选址 (wireless.cpp/c/pas) 【...
2015noip第二十一届普及组初赛试题
2015noip第十一届普及组初赛试题_学科竞赛_高中...网上聊天 11.下面哪种软件不属于即时通信软件( )。...O(nIogn) C.O(n) D.O(n2) 20.在 NOI 系列...
更多相关标签:
noi网上同步赛 | noi网络同步赛 | noi网上报名系统 | noi网上报名 | noi初赛 | noi 2015提高组初赛 | noi初赛试题 | noi2016初赛 |