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

NOIP2008


全国信息学奥林匹克联赛(NOIP2008)复赛提高组

全国信息学奥林匹克联赛(NOIP2008)复赛 提高组

1.

笨小猴

(wird.pas/c/cpp)

笨小猴的词汇量很小,所以每次做英语选择题的时候都很头疼。但是他找到了一种方法,经试验证明, 用这种方法去选择选项的

时候选对的几率非常大! 这种方法的具体描述如下:假设 maxn 是单词中出现次数最多的字母的出现次数, minn 是单词中出 现次数最少的字母的出现次数,如果 maxn-minn 是一个质数,那么笨小猴就认为这是个 Lucky Word,这 样的单词很可能就是正确的答案。

【输入】 输入文件 word.in 只有一行,是一个单词,其中只可能出现小写字母,并且长度小于 100。

【输出】 输出文件 word.out 共两行,第一行是一个字符串,假设输入的的单词是 Lucky Word ,那么输出 “Lucky Word”,否则输出“No Answer”; 第二行是一个整数,如果输入单词是 Lucky Word,输出 maxn-minn 的值,否则输出 0。

【输入输出样例 1】 word.in error word.out Lucky Word 2 【输入输出样例 1 解释】 单词 error 中出现最多的字母 r 出现了 3 次,出现次数最少的字母出现了 1 次,3-1=2,2 是质数。 【输入输出样例 2】 word.in Olympic word.out No Answer 0 【输入输出样例 2 解释】 单词 olympic 中出现最多的字母 i 出现了 2 次,出现次数最少的字母出现了 1 次,2-1=1,1 不是质数。 第 1 页共 8 页

全国信息学奥林匹克联赛(NOIP2008)复赛提高组

【问题描述】

2.

火柴棒等式

(matches.pas/c/cpp)

给你 n 根火柴棍,你可以拼出多少个形如“A+B=C”的等式?等式中的 A、B、C 是用火柴棍拼出的 整数(若该数非零,则最高位不能是 0) 。用火柴棍拼数字 0-9 的拼法如图所示:

注意:

1. 加号与等号各自需要两根火柴棍 2. 如果 A≠B,则 A+B=C 与 B+A=C 视为不同的等式(A、B、C>=0) 3. n 根火柴棍必须全部用上

【输入】 输入文件 matches.in 共一行,又一个整数 n(n<=24) 。

【输出】 输出文件 matches.out 共一行,表示能拼成的不同等式的数目。

【输入输出样例 1】 matches.in 14 matches.out 2

【输入输出样例 1 解释】 2 个等式为 0+1=1 和 1+0=1。

【输入输出样例 2】 matches.in matches.out

第 2 页共 8 页

全国信息学奥林匹克联赛(NOIP2008)复赛提高组

【问题描述】
18 9

【输入输出样例 2 解释】 9 个等式为: 0+4=4 0+11=11 1+10=11 2+2=4 2+7=9 4+0=4 7+2=9 10+1=11 11+0=11

3.

传纸条

(wassage.pas/c/cpp) 小渊和小轩是好朋友也是同班同学,他们在一起总有谈不完的话题。一次素质拓展活动 中,班上同学安排做成一个 m 行 n 列的矩阵,而小渊和小轩被安排在矩阵对角线的两端, 因此,他们就无法直接交谈了。幸运的是,他们可以通过传纸条来进行交流。纸条要经由许多同学传到对 方手里,小渊坐在矩阵的左上角,坐标(1,1),小轩坐在矩阵的右下角,坐标 (m,n)。从小渊传到小轩的纸条 只可以向下或者向右传递,从小轩传给小渊的纸条只可以向上或者向左传递。 在活动进行中,小渊希望给小轩传递一张纸条,同时希望小轩给他回复。班里每个同学 都可以帮他们传递,但只会帮他们一次,也就是说如果此人在小渊递给小轩纸条的时候帮忙,那么在小轩 递给小渊的时候就不会再帮忙。反之亦然。 还有一件事情需要注意,全班每个同学愿意帮忙的好感度有高有低(注意:小渊和小轩的好心程度没 有定义,输入时用 0 表示) ,可以用一个 0-100 的自然数来表示,数越大表示越好心。小渊和小轩希望尽可 能找好心程度高的同学来帮忙传纸条,即找到来回两条传递路 径,使得这两条路径上同学的好心程度只和最大。现在,请你帮助小渊和小轩找到这样的两条路径。

【输入】

第 3 页共 8 页

全国信息学奥林匹克联赛(NOIP2008)复赛提高组

【问题描述】
输入文件 message.in 的第一行有 2 个用空格隔开的整数 m 和 n,表示班里有 m 行 n 列 (1<=m,n<=50) 。 接下来的 m 行是一个 m*n 的矩阵,矩阵中第 i 行 j 列的整数表示坐在第 i 行 j 列的学生的好心程度。 每行的 n 个整数之间用空格隔开。

【输出】 输出文件 message.out 共一行,包含一个整数,表示来回两条路上参与传递纸条的学生 的好心程度之和的最大值。

【输入输出样例】 message.in 33 039 285 570 message.out 34

【限制】 30%的数据满足:1<=m,n<=10 100%的数据满足:1<=m,n<=50

4.

双栈排序

(twostack.pas/c/cpp)

Tom 最近在研究一个有趣的排序问题。如图所示,通过 2 个栈 S1 和 S2,Tom 希望借助 以下 4 种操作实现将输入序列升序排序。 操作 a 如果输入序列不为空,将第一个元素压入栈 S1

第 4 页共 8 页

全国信息学奥林匹克联赛(NOIP2008)复赛提高组

【问题描述】
操作 b 如果栈 S1 不为空,将 S1 栈顶元素弹出至输出序列 操作 c 如果输入序列不为空,将第一个元素压入栈 S2 操作 d 如果栈 S2 不为空,将 S2 栈顶元素弹出至输出序列 如果一个 1~n 的排列 P 可以通过一系列操作使得输出序列为 1,2,?,(n-1),n,Tom 就称 P 是一个 “可双栈排序排列”。例如(1,3,2,4) 就是一个“可双栈排序序列”,而(2,3,4,1) 不是。下图描述了一个将 (1,3,2,4)排序的操作序列:<a,c,c,b,a,d,d,b>

第 5 页共 8 页

全国信息学奥林匹克联赛(NOIP2008)复赛提高组

【问题描述】

当然,这样的操作序列有可能有几个,对于上例(1,3,2,4),<a,c,c,b,a,d,d,b>是另外一个可行的操作序列。 Tom 希望知道其中字典序最小的操作序列是什么。

第 6 页共 8 页

全国信息学奥林匹克联赛(NOIP2008)复赛提高组 【输入】 输入文件 twostack.in 的第一行是一个整数 n。 第二行有 n 个用空格隔开的正整数,构成一个 1~n 的排列。

【输出】 输出文件 twostack.out 共一行,如果输入的排列不是“可双栈排序排列”,输出数字 0; 否则输出字典序最小的操作序列,每两个操作之间用空格隔开,行尾没有空格。

【输入输出样例 1】 twostack.in 4 1324 twostack.out abaabbab

【输入输出样例 2】 twostack.in 4 2341 twostack.out 0

【输入输出样例 3】 twostack.in 3 231 twostack.out acabbd

【限制】 30%的数据满足: n<=10 50%的数据满足: n<=50 100%的数据满足: n<=1000 【思路】 构造“不可能”边+二分图着色 点的分配转化为了二分图的着色。

(以下摘自洛谷 OI【题解】 )
考虑对于任意两个数 q1[i]和 q1[ j]来说,它们不能压入同一个栈中的充要条件是什么(注意没有必要使它们同时存在于同一个栈 中,只是压入了同一个 栈).实际上,这个条件 p 是:存在一个 k,使得 i<j<k 且 q1[k]<q1[i]<q1[ j]. 首先证明充分性,即如果满足条件 p,那么这两个数一定不能压入同一个栈.这个结论很显然,使用反证法可证. 假设这两个数压入了同一个栈,那么在压入 q1[k]的时候栈内情况如下:

第 7 页共 8 页

全国信息学奥林匹克联赛(NOIP2008)复赛提高组
…q1[i]…q1[ j]… 因为 q1[k]比 q1[i]和 q1[j]都小,所以很显然,当 q1[k]没有被弹出的时候,另外两个数也都不能被弹出(否则 q2 中的数字顺序就 不是 1,2,3,…,n 了). 而之后,无论其它的数字在什么时候被弹出,q1[ j]总是会在 q1[i]之前弹出.而 q1[ j]>q1[i],这显然是不正确的. 接下来证明必要性.也就是,如果两个数不可以压入同一个栈,那么它们一定满足条件 p.这里我们来证明它的逆否命题,也就是"如 果不满足条件 p,那么这两个数一定可以压入同一个栈." 不满足条件 p 有两种情况:一种是对于任意 i<j<k 且 q1[i]<q1[ j],q1[k]>q1[i];另一种是对于任意 i<j,q1[i]>q1[ j]. 第一种情况下,很显然,在 q1[k]被压入栈的时候,q1[i]已经被弹出栈.那么,q1[k]不会对 q1[ j]产生任何影响(这里可能有点乱,因为 看起 来,当 q1[ j]<q1[k]的时候,是会有影响的,但实际上,这还需要另一个数 r,满足 j<k<r 且 q1[r]<q1[ j]<q1[k],也就是证明充 分性的时候所说的情况…而事实上我们现在并不考虑这个 r,所以说 q1[k]对 q1[ j]没 有影响). 第二种情况下,我们可以发现这其实就是一个降序序列,所以所有数字都可以压入同一个栈. 这样,原命题的逆否命题得证,所以原命题得证. 此时,条件 p 为 q1[i]和 q1[j]不能压入同一个栈的充要条件也得证. 这样,我们对所有的数对(i,j)满足 1<=i<j<=n,检查是否存在 i<j<k 满足 p1[k]<p1[i]& lt;p1[ j].如果存在,那么在点 i 和点 j 之 间连一条无向边,表示 p1[i]和 p1[ j]不能压入同一个栈.此时想到了什么?那就是二分图~ 二分图的两部分看作两个栈,因为二分图的同一部分内不会出现任何连边,也就相当于不能压入同一个栈的所有结点都分到了两个 栈中. 此时我们只考虑检查是否有解,所以只要 o(n)检查出这个图是不是二分图,就可以得知是否有解. 然后处理最小字典序问题。实际上对二分图染色后对应的操作显然编号小的优先使用 a 操作,可以使得字典序尽量小。 这里要提二分图的一个性质:二分图中不同的连通分量染色是互不影响的。所以为了满足最小字典序的问题,可以选取编号最 小的未染色结点染成 1 并对它所在连通分量染色。染完之后,模拟输出序列就可以了。

第 8 页共 8 页


更多相关文档:

NOIP2008年提高组初赛试题(十四届)(非常详细)

NOIP2008 初赛(提高组)试题&解析 第十四届全国青少年信息学奥林匹克联赛初赛试题 ( 提高组 Pascal 语言 二小时完成 )●● 全部试题答案均要求写在答卷纸上,写在...

NOIP2008提高组解题报告

(ways,pw-1); fout <<ways[0] <<' ' <<endl; return 0; } NOIP2008 提高组解题报告 angwuy 1 word 这道题完全是送分题,只需要直接统计,再判断素数...

NOIP2008提高组前三题解题报告

NOIP2008 提高组前三题解题报告 [日期:2008-11-18] 来源: 作者:张恩权 [字体:大中小] NOIP2008 提高组前三题解题报告 1.笨小猴 基本的字符串处理, 细心一...

NOIP2008提高组初赛试题_C++含答案

NOIP2008提高组初赛试题_C++含答案_英语考试_外语学习_教育专区。第十四届全国青少年信息学奥林匹克联赛初赛试题( 提高组 C++ 语言 二小时完成 )●● 全部试题答案...

NOIP2008普及组初赛试题答案

⑤ ) ); end; ); end; NOIP2008 年普及组(Pascal 语言)参考答案与评分标准(修正) 年普及组( 语言) 考答案与评分标准(修正) 一、单项选择题: (每题 1.5...

NOIP2008普及组复赛试题与解题报告

NOIP 2008 普及组解题报告一、ISBN 号码(isbn.pas/c/cpp) 【问题描述】 每一本正式出版的图书都有一个 ISBN 号码与之对应,ISBN 码包括 9 位数字、1 位识别...

NOIP2008获奖名单全集

NOIP2008获奖名单全集_幼儿读物_幼儿教育_教育专区。NOIP2008获奖名单全集2008 全国青少年信息学奥林匹克联赛获奖名单 *为往年获 奖者 证书编号 IO80001 IO80002 IO80...

NOIP2008普及组复赛思路及程序(PASCAL)

NOIP2008普及组复赛思路及程序(PASCAL)_城乡/园林规划_工程科技_专业资料。saf第一题 Program Gy; Const Name='isbn'; Var A,B:String; Procedure Inp; Begin...

NOIP2008普及组复赛试题

NOIP2008普及组复赛试题_初一英语_英语_初中教育_教育专区。NOIP2008普及组复赛试题全国信息学奥林匹克联赛( 全国信息学奥林匹克联赛(NOIP2008)复赛 )普及组 一.题...

NOIP2008普及组复赛解题报告

NOIP2008普及组复赛解题报告_IT/计算机_专业资料。如标题NOIP2008 普及组复赛解题报告 一、ISBN 号码 基础字符串处理题,心细一点的基本都能得满分。 参考程序: pr...
更多相关标签:
noip | noip2008普及组复赛 | noip2008提高组 | noip2008提高组初赛 | ioi | noip2008提高组复赛 | noip2009 | noip2008传纸条 |
网站地图

文档资料共享网 nexoncn.com copyright ©right 2010-2020。
文档资料共享网内容来自网络,如有侵犯请联系客服。email:zhit325@126.com