NOIP冲刺2010试题三第一题：abbreviate【题目描述】最近情报人员得到了一些经过加密的文章，每个单词都很长。破译人员想到先把单词化简一下，方法是把每个单词尽量取短些的前缀，但所取的前缀不能是其他单词的前缀。这个任务现在就交给你来完成。解释：“字符串s1是s2的前缀”是说把字符串s2的后面去掉某些，只保留与s1相同长度，s2就与s1完全相同。如：“abc“是”abcaade“和”abc“的前缀，但不是”abadc“的前缀。数据范围单词数N，1=n=50; 每个单词长度不超过50；并且都是由小写字母构成。保证所给单词没有一个单词是另一个单词的前缀。【输入文件】第一行一个整数N，表示单词的个数。下面有N行，每行一个单词。【输出文件】共N行，每行一个单词，是对应上面N个单词化简后的单词。【样例输入1】3abcefgijh【样例输出1】aei【样例输入2】3aacaadaae【样例输出2】aacaadaae第二题：blocks【题目描述】为了增强幼儿园小朋友的数数能力，小虎老师给了一个家庭游戏作业。让小虎那一块空的围棋盘，随机在一些方格中放些棋子（有黑白两种颜色），如果一个方格和它的上、下、左、右四个方格之一有相同颜色的棋子，则认为两个格子是相互连通的。这期间，要求小虎不断统计共有多少个连通块。如下图是一个5*9的一块棋盘，其中“.“表示空格，”*“表示黑棋子，”“表示白棋子。则有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 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，分别表示一种物品的相关数据：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【题目描述】小虎刚刚上了幼儿园，老师让他做一个家庭作业：首先画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摆放法*-*-*-*