《NOIP普及组试题(二).doc》由会员分享,可在线阅读,更多相关《NOIP普及组试题(二).doc(4页珍藏版)》请在金锄头文库上搜索。
1、NOIP冲刺2010试题三第一题:abbreviate【题目描述】最近情报人员得到了一些经过加密的文章,每个单词都很长。破译人员想到先把单词化简一下,方法是把每个单词尽量取短些的前缀,但所取的前缀不能是其他单词的前缀。这个任务现在就交给你来完成。解释:“字符串s1是s2的前缀”是说把字符串s2的后面去掉某些,只保留与s1相同长度,s2就与s1完全相同。如:“abc“是”abcaade“和”abc“的前缀,但不是”abadc“的前缀。数据范围单词数N,1=n=50; 每个单词长度不超过50;并且都是由小写字母构成。保证所给单词没有一个单词是另一个单词的前缀。【输入文件】第一行一个整数N,表示单词
2、的个数。下面有N行,每行一个单词。【输出文件】共N行,每行一个单词,是对应上面N个单词化简后的单词。【样例输入1】3abcefgijh【样例输出1】aei【样例输入2】3aacaadaae【样例输出2】aacaadaae第二题:blocks【题目描述】为了增强幼儿园小朋友的数数能力,小虎老师给了一个家庭游戏作业。让小虎那一块空的围棋盘,随机在一些方格中放些棋子(有黑白两种颜色),如果一个方格和它的上、下、左、右四个方格之一有相同颜色的棋子,则认为两个格子是相互连通的。这期间,要求小虎不断统计共有多少个连通块。如下图是一个5*9的一块棋盘,其中“.“表示空格,”*“表示黑棋子,”“表示白棋子。则
3、有4块连通子块。哥哥大虎在一边看一边想,如果棋盘是N*N的,共放了M个棋子,如何使用计算机解决这个问题呢?数据范围 30%数据:1=n=10 60%数据:1=n=100 100%数据:1=n=500,1=m=n*n。【输入文件】第一行两个整数:N,M接下来有M行,每行三个整数:C X Y(0=c=1,1=x,y=n)。分别表示依次放入棋子的颜色(0表示白色,1表示黑色)、要放入格子的横坐标和格子的纵坐标。【输出文件】共M行。第i行一个整数,表示放入第i个棋子后,当前有多少个棋子连通块。【样例输入1】3 51 1 11 1 20 2 21 3 11 2 1【样例输出1】11232【样例输入2】3
4、 51 1 21 2 11 3 21 2 31 2 2【样例输出2】12341第三题:gifts【题目描述】学校刚开完运动会,准备为尽可能多的同学评奖,并为每个人颁发一份奖品。一份奖品包括N个物品,如:5支铅笔、10本练习薄等。每份奖品完全一样。虽然学校的保管室里还有一些办去年运动会后剩余的物品。在商店里,每种物品都有很多,但是,只有两种包装:大盒或小盒,并且不拆开买。现在的问题是,充分利用这M元钱,最多可准备多少份这样的奖品?数据范围:1=n=100,1=m=100000.【输入文件】第一行两个整数:N,M下面有N行,每行有6 个正整数X.,Y,SM,PM,SV,PV,分别表示一种物品的相关
5、数据:X,10=x=100,一份奖品中,这种物品需要的件数;Y,1=y=100,这种物品去年剩余的件数;SM,1=sm100,这种物品小包装的件数;PM,10=PM100,这种物品小包装的1盒价格;SV,SMsv=100,这种物品大包装里的件数;PV,PMPV=100,这种物品大包装的1盒价格;【输出文件】一个整数,最多可准备的礼品份数。【样例输入1】2 10010 8 10 10 13 1112 20 6 10 17 24【样例输出1】5【样例输入2】3 6510 5 7 10 13 1410 5 8 11 14 1510 5 9 12 15 16【样例输出2】2第四题:diagrams【题
6、目描述】小虎刚刚上了幼儿园,老师让他做一个家庭作业:首先画3行格子,第一行有三个格子,第二行有2个格子,第三行有1个格子。每行的格子从左到右可以放棋子,但要求除第一行外,每行放的棋子数不能超过上一行的棋子。玩了一会儿,小虎的哥哥大虎:这个作业有很多种摆放法,我想找到,但我不知道有多少种方案,你能帮助我吗?大虎是学校信息学集训队的,立刻想到用计算机来解决这个问题,并很快有了解答:13。第二天他把问题拿到学校,并说如果第一行有N个格子,第二行有N-1个格子,第N行有1个格子,怎么办?现在请你一块来帮助他解决这个难题。数据范围:30%数据:1=n=1250%数据:1=n=30100%数据:1=n=100【输入文件】仅一行,一个正整数N。【输出文件】一行,方案总数。【样例输入1】2 【样例输出1】4 【样例输入2】3【样例输出2】13【样例说明】样例1说明N=2时,有如下4种摆放棋子法(*表示棋子,_表示空格):方案数1234摆放法*-*-*-*