9512.net
甜梦文库
当前位置:首页 >> 学科竞赛 >>

NOI2016Day1试题



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

CCF NOI 2016
第一试
竞赛时间:2016 年 7 月 24 日 8:30-13:30
题目名称 目录 可执行文件名 输入文件名 输出文件名 每个测试点时限 内存限制 测试点数目 每个测试点分值 是否有部分分 题目类型 是否有样例文件 是否有附加文件 优秀的拆分 excellent

excellent excellent.in excellent.out 1.5 秒 512MB 20 5 否 传统型 是 否 网格 grid grid grid.in grid.out 2秒 1GB 25 4 否 传统型 是 否 循环之美 cyclic cyclic cyclic.in cyclic.out 2秒 512MB 25 4 否 传统型 是 否

提交源程序须加后缀 对于 C++ 语言 excellent.cpp 对于 C 语言 excellent.c 对于 Pascal 语言 excellent.pas 编译开关 对于 C++ 语言 对于 C 语言 对于 Pascal 语言

grid.cpp grid.c grid.pas

cyclic.cpp cyclic.c cyclic.pas

-O2 -lm -O2 -lm -O2

-O2 -lm -O2 -lm -O2

-O2 -lm -O2 -lm -O2

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

第一试 优秀的拆分

优秀的拆分
【问题描述】 如果一个字符串可以被拆分为 的形式, 其中 和 是任意非空 字 .. 符串,则我们称该字符串的这种拆分是优秀的。 例如,对于字符串 aabaabaa,如果令 = aab, = a,我们就找到了这 个字符串拆分成 的一种方式。 一个字符串可能没有优秀的拆分,也可能存在不止一种优秀的拆分。比如我 们令 = a , = baa,也可以用 表示出上述字符串;但是,字符串 abaabaa 就没有优秀的拆分。 现在给出一个长度为 的字符串 ,我们需要求出,在它所有子串 的所有 .... 拆分方式中,优秀拆分的总个数。这里的子串是指字符串中连续 的一段。 .. 以下事项需要注意: 1. 2. 3. 出现在不同位置的相同子串,我们认为是不同的子串,它们的优秀拆分 均会被计入答案。 在一个拆分中,允许出现 = 。例如 cccc 存在拆分 = = c。 字符串本身也是它的一个子串。

【输入格式】 输入文件为 excellent.in。 每个输入文件包含多组数据。 输入文件的第一行只有一个整数 , 表示数据 的组数。保证 1 ≤ ≤ 10。 接下来 行,每行包含一个仅由英文小写字母构成的字符串 ,意义如题 所述。 【输出格式】 输出文件为 excellent.out。 输出 行,每行包含一个整数,表示字符串 所有子串的所有拆分中,总 共有多少个是优秀的拆分。

第2页

共 11 页

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

第一试 优秀的拆分

【样例 1 输入】 4 aabbbb cccccc aabaabaabaa bbaabaababaaba 【样例 1 输出】 3 5 4 7 【样例 1 说明】 我们用 [, ] 表示字符串 第 个字符到第 个字符的子串(从 1 开 始计数) 。 第一组数据中,共有 3 个子串存在优秀的拆分: [1,4] = aabb,优秀的拆分为 = a, = b; [3,6] = bbbb,优秀的拆分为 = b, = b; [1,6] = aabbbb,优秀的拆分为 = a, = bb。 而剩下的子串不存在优秀的拆分,所以第一组数据的答案是 3。 第二组数据中,有两类,总共 4 个子串存在优秀的拆分: 对于子串 [1,4] = [2,5] = [3,6] = cccc ,它们优秀的拆分相同,均为 = c, = c,但由于这些子串位置不同,因此要计算 3 次; 对于子串 [1,6] = cccccc,它优秀的拆分有 2 种: = c, = cc 和 = cc, = c,它们是相同子串的不同拆分,也都要计入答案。 所以第二组数据的答案是 3 + 2 = 5。 第三组数据中,[1,8] 和 [4,11] 各有 2 种优秀的拆分,其中 [1,8] 是 问题描述中的例子,所以答案是 2 + 2 = 4。 第四组数据中,[1,4],[6,11],[7,12],[2,11],[1,8] 各有 1 种优秀 的拆分,[3,14] 有 2 种优秀的拆分,所以答案是 5 + 2 = 7。 【样例 2 输入输出】 见选手目录下的 excellent/excellent2.in 与 excellent/excellent2.ans。

第3页

共 11 页

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

第一试 优秀的拆分

【样例 3 输入输出】 见选手目录下的 excellent/excellent3.in 与 excellent/excellent3.ans。 【子任务】 对于全部的测试点,保证 1 ≤ ≤ 10。以下对数据的限制均是对于单组输 入数据而言的,也就是说同一个测试点下的 组数据均满足限制条件。 我们假定 为字符串 的长度,每个测试点的详细数据范围见下表: 测试点编号 1、2 3、4 5、6 7、8 9、10 11、12 13、14 15 16 17 18 19 20 ≤ 300 ≤ 2000 ≤ 10 ≤ 20 ≤ 30 ≤ 50 ≤ 100 ≤ 200 ≤ 300 ≤ 500 ≤ 1000 ≤ 2000 ≤ 30000 无 其他约束 中所有字符 全部相同

第4页

共 11 页

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

第一试 网格

网格
【问题描述】 跳蚤国王和蛐蛐国王在玩一个游戏。 他们在一个 行 列的网格上排兵布阵。其中的 个格子中(0 ≤ ≤ ) ,每个格子有一只蛐蛐,其余的格子中,每个格子有一只跳蚤。 我们称占据的格子有公共边的两只跳蚤是相邻 的。 .. 我们称两只跳蚤是连通 的, 当且仅当这两只跳蚤相邻 ,或存在另一只跳蚤与 .. .. 这两只跳蚤都连通 。 .. 现在,蛐蛐国王希望,将某些(0 个,1 个或多个)跳蚤替换成蛐蛐,使得 在此之后存在至少两只跳蚤不 连通 。 . .. 例如:我们用图 表示一只跳蚤,用图 表示一只蛐蛐,那么图 1 描述

了一个 = 4, = 4, = 2 的情况。 这种情况下蛐蛐国王可以通过将第 2 行第 2 列,和第 3 行第 3 列的两 只跳蚤替换为蛐蛐, 从而达成他的希望, 如图 2 所示。 并且, 不存在更优的方案, 但是可能存在其他替换 2 只跳蚤的方案。

图1

图2

你需要首先判断蛐蛐国王的希望能否被达成。如果能够达成,你还需要最小 化被替换的跳蚤的个数。

第5页

共 11 页

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

第一试 网格

【输入格式】 输入文件为 grid.in。 每个输入文件包含多组数据。 输入文件的第一行只有一个整数 ,表示数据的组数。保证 1 ≤ ≤ 20。 接下来依次输入 组数据,每组数据的第一行包含三个整数 , , 。保证 1 ≤ , ≤ 109 ,0 ≤ ≤ min(, 105 )。 接下来 行,每行包含两个整数 , ,表示第 行,第 列的格子被一 个蛐蛐占据(1 ≤ ≤ , 1 ≤ ≤ ) 。每一组数据当中,同一个蛐蛐不会被多次 描述。 同一行相邻的整数之间由一个空格隔开。 【输出格式】 输出文件为 grid.out。 对于每一组数据依次输出一行答案。 如果这组数据中,蛐蛐国王的希望不能被达成,输出 ?1。否则,输出被替 换的跳蚤的个数的最小值。 【样例 1 输入】 4 4 1 4 2 1 2 1 2 1

4 1 4 3 2 2 1 2 1

2

1 2

0

【样例 1 输出】 2 1 0 -1

第6页

共 11 页

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

第一试 网格

【样例 1 说明】 第一组数据就是问题描述中的例子。 对于第二组数据, 可以将第 2 行第 2 列的一只跳蚤替换为蛐蛐, 从而使得 存在两只跳蚤不 连通 ,并且不存在更优的方案。 . .. 对于第三组数据,最初已经存在两只跳蚤不 连通 ,故不需要再进行替换。 . .. 对于第四组数据, 由于最多只有一只跳蚤,所以无论如何替换都不能存在两 只跳蚤不 连通 。 . .. 【样例 2 输入输出】 见选手目录下的 grid/grid2.in 与 grid/grid2.ans。 【提示】 如果你的程序需要用到较大的栈空间 (这通常意味着需要较深层数的递归) , 请务必仔细阅读选手目录下的文档 stack.pdf, 以了解在最终评测时栈空间的限制 与在当前工作环境下调整栈空间限制的方法。 【子任务】 对于全部的测试点,保证 1 ≤ ≤ 20。我们记 ∑ 为某个测试点中,其 组输入数据的所有 的总和。对于所有的测试点,∑ ≤ 105 。 对于全部的数据,满足 1 ≤ , ≤ 109 , 0 ≤ ≤ , 1 ≤ ≤ , 1 ≤ ≤ 。 每个测试点的详细数据范围见下表。表中的 , , 均是对于单个输入数据 (而非测试点) 而言的, 也就是说同一个测试点下的 组数据均满足限制条件; 而 ∑ 是对于单个测试点而言的。为了方便阅读, “测试点”一列被放到了表格 的中间而不是左边。

第7页

共 11 页

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

第一试 网格

, ≤ 4 ≤ 8 ≤ 15 ≤ 30 ≤ 100 ≤ 300 ≤ 1000

测试点 1 2 3 4 5 6 7 8





≤ 5 ≤ 15 ≤ 30

≤ 20000

9 10

≤ 20000 ≤ 105 , ≤ 20000 ≤ 3 × 105 ≤ 106 ≤ 109 , ≤ 105

11 12 13 14 15 16 17 18 19 20 ∑ ≤ 105 = 0 ≤ 1 ≤ 2 ≤ 3 ≤ 10 ≤ 30 ≤ 300 ∑ ≤ 20000 ∑ ≤ 105 ∑ ≤ 20000

, ≤ 109

21 22 23 24 25

第8页

共 11 页

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

第一试 循环之美

循环之美
【问题描述】 牛牛是一个热爱算法设计的高中生。在他设计的算法中,常常会使用带小数 的数进行计算。牛牛认为,如果在 进制下,一个数的小数部分是纯循环 的, ... 那么它就是美的。 现在,牛牛想知道:对于已知的十进制数 和 ,在 进制下,有多少 个数值上互不相等 的纯循环小数,可以用分数 .... ≤ ,且 , 是整数。 一个数是纯循环的,当且仅当其可以写成以下形式: . 1 ? 2 3 … ?1 ? 其中, 是一个整数, ≥ 1; 对于 1 ≤ ≤ , 是 进制下的一位数字。 例如,在十进制下,0.45454545 … … = 0. 4?5? 是纯循环的,它可以用
5 11

表示,其中 1 ≤ ≤ ,1 ≤

、22
1 6

10

等分数表示;在十进制下,0.1666666 … … = 0.16? 则不是纯循环的,它可以用 等分数表示。

需要特别注意的是,我们认为一个整数是纯循环的, 因为它的小数部分可以 表示成 0 的循环或是 ? 1 的循环; 而一个小数部分非零的有限小数不是纯循 环的。 【输入格式】 输入文件为 cyclic.in。 输入文件只有一行,包含三个十进制正整数 , , ,意义如题所述。 【输出格式】 输出文件为 cyclic.out。 只输出一行一个整数,表示满足条件的美的数的个数。

第9页

共 11 页

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

第一试 循环之美

【样例 1 输入】 2 6 10 【样例 1 输出】 4 【样例 1 说明】 满足条件的数分别是: 1/1 = 1.0000 … … 1/3 = 0.3333 … … 2/1 = 2.0000 … … 2/3 = 0.6666 … … 1/1 和 2/2 虽然都是纯循环小数,但因为它们相等,因此只计数一次;同 样,1/3 和 2/6 也只计数一次。 【样例 2 输入】 23333 666666 310 【样例 2 输出】 5089564081 【提示】 这部分将提供一个将分数化为对应的小数的方法, 如果你已经熟悉这个方法, 你不必阅读本提示。 分数可以通过除法, 用分子除以分母化为对应的小数。有些分数在除法过程 中无法除尽, 这样的分数在不断进行的除法过程中余数 一定会重复出现。从商数 .. 的个位所对应的余数起, 设第一次重复出现的余数前两次出现的位置所对应的商 数位分别是小数点后第 位和小数点后第 位 (特殊地: 如果其中一个对应的 商数位是个位,则认为 = 0;不妨设 < ) ,则其循环部分可以用小数点后 第 + 1 位到小数点后第 位的循环来表示。 例如: 在十进制下, 将
5 11

转化为小数时, 个位开始的商数依次为 4,5,4, …,

对应的余数分别为 6,5,6, …。余数第一次重复出现的位置是个位和小数点后第 2 位,那么 = 0, = 2 即其循环部分可以用小数点第 1 位到第 3 位来表示。
第 10 页 共 11 页

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

第一试 循环之美

表示为:11 = 0.45454545 … = 0. 4?5?。 在十进制下,将
1 6

5

转化为小数时,个位开始的商数依次为 1,6,6, …,对应的

余数分别为 4,4,4 …。 余数第一次重复出现的位置是小数点后第 1 位和小数点后 第 2 位,即其循环部分可以用小数点后第 2 位来表示。表示为:6 = 0.1666 … … = 0.16?。 需要注意的是:商数 重复出现并不代表进入了循环节。 .. 【子任务】 对于所有的测试点, 保证 1 ≤ ≤ 109 , 1 ≤ ≤ 109 , 2 ≤ ≤ 2000。 对于每 个测试点,有以下约束(其中留空的表示没有特殊的约束) : 测试点 编号 1 2 3 4 5 6 7 8 9 10 11 12 测试点 编号 13 14 15 16 17 18 19 20 21 22 23 24、25
1

≤ 10 ≤ 100 ≤ 1000 ≤ 10000 ≤ 10 ≤ 100 ≤ 1000 ≤ 10000 ≤ 10 ≤ 100 ≤ 1000 ≤ 10000

≤ 20 ≤ 104

=2 =2 =2 =2

≤ 105 ≤ 2 × 105 ≤ 5 × 105 ≤ 106 ≤ 2 × 106 ≤ 5 × 106 ≤ 107 ≤ 2 × 107 ≤ 2 × 107 ≤ 108 ≤ 108

≤ 108

≤ 100 ≤ 1000

≤ 108

≤ 100 ≤ 1000

≤ 20 ≤ 104

=3 =3 =3 =3

≤ 108

≤ 100 ≤ 1000

≤ 20 ≤ 104

≤ 100 ≤ 100 ≤ 1000

≤ 108 ≤ 108

第 11 页

共 11 页



更多相关文章:
更多相关标签:

All rights reserved Powered by 甜梦文库 9512.net

copyright ©right 2010-2021。
甜梦文库内容来自网络,如有侵犯请联系客服。zhit325@126.com|网站地图