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

清北学堂2012国庆NOIP课件——枚举与搜索


Section 1.2 TEXT Complete Search
枚举搜索 译 by Lucky Crazy 思想: 写枚举搜索时应遵循 KISS 原则(Keep it simple stupid,译为“写最单纯愚蠢的程序”,意 思是应把程序写得尽量简洁) ,竞赛时写程序的最终目标就是在限制时间内求出解,而不需 太在意否还有更快的算法。 枚举搜索具有强大的力量, 他用直

接面向答案并尝试所有方案的方法发现答案。 这种算 法几乎总是解题时你第一个想到的方法。 如果它能在规定的时间与空间限制内找出解, 那么 它常常很容易编写与调试。 这就意味着你可以有时间去解答其他难题, 即那些不能显示枚举 算法强大的题目。 如果你面对一道可能状态小于两百万的题目, 那么你可以考虑使用枚举搜索。 尝试所有 的状态,看看它们是否可行。 小心!小心! 有时,题目不会直接要求你使用枚举算法。 例题 1:派对灯 [IOI 98] 在一次 IOI 派对上有 N 个灯和 4 个灯开光,第一个开关可以使所有灯改变状态(关上开 着的灯,开启关着的灯) ,第二个开关可以改变所有偶数位上灯的状态,第三个开关可以改 变所有奇数位上灯的状态,第四个开关控制着灯 1、4、7、10……(3n+1) 。 告诉你 N 的值和所有按开关的次数(小于 10,000 次) 。并告诉你某些灯的状态(例如: 7 号灯是关着的,10 号灯是开着的)请编程输出所有灯可能的最后状态。 很明显,每次按开关你都要尝试 4 种可能。那么总共要试 410000 次(大约 106020) , 那意味着你没有足够的时间去使用枚举搜索, 但是我们将枚举方法改进一下, 那就可以使用 枚举了。因为无论有多少个灯,由于开关控制的特殊性,都会出现 6 个灯一次循环的情况, 即 1 号灯的状态永远与 7 号灯,13 号灯,19 号灯……相同,2 号灯的状态也永远与 8 号灯, 14 号灯,20 号灯……相同。同样,无论你按了多少次开关,按同一个开关两次就相当于没有 按该开关,那么每一个开关就只需要考虑按一次或没有按,那么这题的枚举量就很小了。 例题 2: 时钟调整 [IOI 94] 有九个钟被摆放在一个 3 X 3 的矩阵中,它们各自指向 12:00,9:00,6:00,3:00 中的一种,你的目的是将它们的指针全部调向 12:00。很遗憾,每一次调整你都只能从九 种调整方案中选择一种执行(九种方案已被从 1 到 9 编号) ,每一种方案可以改变固定钟的 状态(例如:方案 1 控制钟 1,2,3,方案 2 控制钟 1,4,7, 方案 3 控制钟 5,6,8,9……) , 即将方案指定的所有钟向前拨快 3 小时 (使时针向顺时针方向旋转 90 度) 请你输出一个数 , 列,使得按该数列表示方案执行后,所有钟都指向 12:00。并且如果把整个序列看作一个 数,要求该数最小。 最容易想到的方法是用递归枚举 1 到 9 的方案在该步使用。 很可怕, 由于递归的层数在 此没有限定,所以将用掉 9k 的时间(k 为层数) ,那可能是相当巨大的。其实,不用紧张, 细心的你一定会发现:当一个方案执行 4 次后,就相当于没有执行,又因为题目要求输出最 优解,那么任意一个方案都没有必要 4 次以上执行。也就是说,只需要枚举每一个方案的 4 种情况(没执行,执行 1,2,3 次)就可以了。他仅有 49 ,约 262,072 此枚举,我们的计 算机 1s 内就可以算完,应该算是极快了。

Section 1.3 PROB Calf Flac
Calf Flac 译 by timgreen 据说如果你给无限只母牛和无限台巨型便携式电脑(有非常大的键盘),那么母牛们会制 造出世上最棒的回文。你的工作就是去这些牛制造的奇观(最棒的回文)。 寻找回文时不用理睬那些标点符号、 空格(但应该保留下来以便做为答案输出),只用考虑 字母'A'-'Z'和'a'-'z'。要你寻找的最长的回文的文章是一个不超过 20,000 个字符的字符串。我 们将保证最长的回文不会超过 2,000 个字符(在除去标点符号、空格之前)。 PROGRAM NAME: calfflac INPUT FORMAT 一个不超过 20,000 个字符的文件。 SAMPLE INPUT (file calfflac.in) Confucius say: Madam, I'm Adam. OUTPUT FORMAT 输出的第一行应该包括找到的最长的回文的长度。 下一个行或几行应该包括这个回文的原文 (没有除去标点符号、空格),把这个回文输出到一行或多行(如果回文中包括换行符)。如果有 多个回文长度都等于最大值,输出那个前出现的。 SAMPLE OUTPUT (file calfflac.out) 11 Madam, I'm Adam

Section 1.4 PROB Arithmetic Progressions
等差数列 译 by tim green 一个等差数列是一个能表示成 a, a+b, a+2b,..., a+nb (n=0,1,2,3,...).在这个问题中 a 是一个 非负的整数,b 是正整数。写一个程序来找出在双平方数集合 S 中长度为 n 的等差数列。双 平方数集合是所有能表示成 p2+q2 的数的集合。 PROGRAM NAME: ariprog INPUT FORMAT 第一行: N(3<= N<=25),要找的等差数列的长度。 第二行: M(1<= M<=250),搜索双平方数的上界 0 <= p,q <= M。 SAMPLE INPUT (file ariprog.in) 5 7 OUTPUT FORMAT 如果没有找到数列,输出`NONE'。如果找到了,输出一行或多行, 每行由于二个整数组成:a,b. 这些行应该先按 b 排序再按 a 排序。将不会有只多于 10,000 个等差数列。 SAMPLE OUTPUT (file ariprog.out)

14 37 4 28 29 8 1 12 5 12 13 12 17 12 5 20 2 24

Section 3.1 PROB Humble Numbers
丑数 译 by tim green 对于一给定的素数集合 S = {p1, p2, ..., pK}, 来考虑那些质因数全部属于 S 的数的集合。 这个集合包括,p1, p1p2, p1p1, 和 p1p2p3 (还有其它)。这是个对于一个输入的 S 的丑数集 合。注意:我们不认为 1 是一个丑数。 你的工作是对于输入的集合 S 去寻找集合中的第 N 个丑数。 longint(signed 32-bit)对于程 序是足够的。 PROGRAM NAME: humble INPUT FORMAT 第 1 行: 第 2 行: 二个被空间分开的整数:K 和 N , 1<= K<=100 , 1<= N<=100,000. K 个被空间分开的整数:集合 S 的元素

SAMPLE INPUT (file humble.in) 4 19 2357 OUTPUT FORMAT 单独的一行,写上对于输入的 S 的第 N 个丑数。 SAMPLE OUTPUT (file humble.out) 27

Section 3.2 PROB Magic Squares
魔板 IOI'96 译 by Felicia Crazy 在成功地发明了魔方之后,拉比克先生发明了它的二维版本,称作魔板。这是一张有 8 个大小相同的格子的魔板: 1 2 3 4

8 7 6 5 我们知道魔板的每一个方格都有一种颜色。 8 种颜色用前 8 个正整数来表示。 这 可以用 颜色的序列来表示一种魔板状态,规定从魔板的左上角开始,沿顺时针方向依次取出整数, 构成一个颜色序列。对于上图的魔板状态,我们用序列(1,2,3,4,5,6,7,8)来表 示。这是基本状态。 这里提供三种基本操作,分别用大写字母“A”,“B”,“C”来表示(可以通过这些操作改 变魔板的状态) : “A”:交换上下两行; “B”:将最右边的一行插入最左边; “C”:魔板中央作顺时针旋转。 下面是对基本状态进行操作的示范: A: 8 7 6 5 1 2 3 4 B: 4 1 2 3 5 8 7 6 C: 1 7 2 4 8 6 3 5

对于每种可能的状态, 这三种基本操作都可以使用。 你要编程计算用最少的基本操作完 成基本状态到特殊状态的转换,输出基本操作序列。 PROGRAM NAME: msquare INPUT FORMAT 只有一行,包括 8 个整数,用空格分开(这些整数在范围 1——8 之间) ,表示目标状态。 SAMPLE INPUT (file msquare.in) 26845731 OUTPUT FORMAT Line 1: Line 2: 包括一个整数,表示最短操作序列的长度。 在字典序中最早出现的操作序列,用字符串表示,除最后一行外,每行输出 60 个字 符。

SAMPLE OUTPUT (file msquare.out) 7 BCABCCB

Section 4.1 PROB Fence Rails
栅栏的木料 Burch, Kolsad, and Schrijvers 译 by Jeru 农民 John 准备建一个栅栏来围住他的牧场。他已经确定了栅栏的形状,但是他在木料 方面有些问题。当地的杂货储存商扔给 John 一些木板,而 John 必须从这些木板中找出尽可 能多所需的木料。 当然,John 可以切木板。因此,一个 9 英尺的木板可以切成一个 5 英尺和一个 4 英尺 的木料 (当然也能切成 3 个 3 英尺的,等等)。John 有一把梦幻之锯,因此他在切木料时, 不会有木料的损失。所需要的木料规格都已经给定。你不必切出更多木料,那没有用。 PROGRAM NAME: fence8

INPUT FORMAT 第 1 行: 第 2 行到第 N+1 行: 第 N+2 行: N (1 <= N <= 50), 表示提供的木板的数目 N 行,每行包括一个整数,表示各个木板的长度。 R (1 <= R <= 1023), 所需木料的数目

第 N+3 行到 R 行,每行包括一个整数(1 <= ri <= 128)表示所需木料的长度。 第 N+R+1 行: SAMPLE INPUT (file fence8.in) 4 30 40 50 25 10 15 16 17 18 19 20 21 25 24 30 OUTPUT FORMAT 只有一行,一个数字,表示能切除的最多的所需木料的树木。当然,并不是任何时候都能切 出所有所需木料。 SAMPLE OUTPUT (file fence8.out) 7

Section 4.1 PROB Cryptcowgraphy
解密牛语 Brian Dean 译 by Jeru 农民 Brown 和 John 的牛们计划协同逃出它们各自的农场。它们设计了一种加密方法用 来保护它们的通讯不被他人知道。如果一头牛有信息要加密,比如"International Olympiad in Informatics",它会随机地把 C,O,W 三个字母插到到信息中(其中 C 在 O 前面,O 在 W 前 面) ,然后它把 C 与 O 之间的文字和 O 与 W 之间的文字的位置换过来。这里是两个例子: International Olympiad in Informatics-> CnOIWternational Olympiad in Informatics International Olympiad in Informatics-> International Cin InformaticsOOlympiad W 为了使解密更复杂, 牛们会在一条消息里多次采用这个加密方法 (把上次加密的结果再 进行加密) 。一天夜里,John 的牛们收到了一条经过多次加密的信息。请你写一个程序判断

它是不是这条信息经过加密(或没有加密)而得到的: Begin the Escape execution at the Break of Dawn PROGRAM NAME:cryptcow INPUT FORMAT 一行,不超过 75 个字符的加密过的信息。 SAMPLE INPUT(file cryptcow.in) Begin the EscCution at the BreOape execWak of Dawn OUTPUT FORMAT 一行,两个整数. 如果能解密成上面那条逃跑的信息,第一个整数应当为 1,否则为 0; 如果第一个数为 1,则第二个数表示此信息被加密的次数,否则第二个数为 0。 SAMPLE OUTPUT(file cryptcow.out) 11


相关文章:
清北学堂08国庆赠送试题答案
清北学堂2012国庆NOIP课件... 24页 免费 清北学堂2012国庆NOIP课件... 15页...{枚举每一个中间顶点} for i←1 to n do {枚举每一个顶点对} for j←1...
清北学堂2012国庆NOIP模拟试题——刘佳倩解题报告
清北学堂2012国庆NOIP课件... 6页 2财富值喜欢此文档的还喜欢 ...当 N 很大时,单纯的枚举算法超时。考虑把空间按照类似魔方的形式划分成>=N 份...
清北学堂2012国庆NOIP模拟试题——刘佳倩
搜 试试 帮助 全部 DOC PPT TXT PDF XLS 百度文库 教育专区 高中教育 学科...清北学堂2012国庆NOIP模拟试题清北学堂2012国庆NOIP模拟试题隐藏>> NOIP2012 模拟...
清北学堂08国庆免费赠送试题
清北学堂2012国庆NOIP课件... 27页 2财富值 清北学堂2012国庆NOIP模拟... 4...国庆学员辅助 学员辅助试 清北学堂 08 国庆学员辅助试题清北学堂教研部提供 上传...
NOIP清北学堂11.14模拟赛题目题解
搜 试试 帮助 全部 DOC PPT TXT PDF XLS ...清北学堂2012国庆NOIP模拟... 5页 2财富值 ...注意,以上说的只是找最大子矩阵,竖着枚举分割线的...
2012寒假清北学堂生态学&动物行为学模块试题
清北学堂2012国庆NOIP课件... 27页 2财富值 生态学※动物行为学 69页 2财富...2012 寒假生态学 动物行为学模块试题 寒假生态学 动物行为学模块试题 生态学&动物...
清北学堂NOIP2010模拟试题与详细解析(13)
搜 试试 7 帮助 全部 DOC PPT TXT PDF XLS ...清北学堂NOIP2010模拟试题与详细解析(13)_IT/计算机...试题解析一、防护伞【考查算法】枚举 【算法描述】...
October 2009 Qualifying Papaya Jungle木瓜丛林_题目
1页 免费 清北学堂2012国庆NOIP课件... 34页 2财富值如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处进行反馈。 ...
矿业工程构造分析复习题
搜 试试 帮助 全部 DOC PPT TXT PDF XLS 百度文库 教育专区 高等教育 理学...清北学堂2012国庆NOIP课件... 27页 2财富值 构造总复习题及答案 21页 1财富...
历年NOIP(普及组提高组)试题分析
搜 试试 7 帮助 全部 DOC PPT TXT PDF XLS ...(160) 2012 (150) 数字统计 枚举 ★ 接水问题 ...NOIP-2011-D1B NOIP-2011-D1C NOIP-2011-D2A ...
更多相关标签:
清北学堂 | 国庆节课件 | 清北学堂官网 | 清北学堂生物题库 | 国庆节ppt课件 | 清北学堂怎么样 | 国庆节主题班会课件 | 国庆课件 |