《2016年暑期培训--搜索》由会员分享，可在线阅读，更多相关《2016年暑期培训--搜索（5页珍藏版）》请在装配图网上搜索。
1、216年信息学暑期培训搜索206年7月7日 ：301：3一、题目概况题目名称细菌水流攀墙残缺的数字源程序名disease。pas/c/cppwter.pas/c/cppallps/cppnumberpas/c/cpp输入文件名diss。inwater。nwa。inumer。in输出文件名isease.outwte.outwalloutumber.out题目类型传统型传统型传统型传统型满 分101010100是否有部分分否否否否内存限制18MM1M28M时间限制ss二、注意事项1. 务必看清题目,严格按照所要求的格式输入、输出。2. 在调试程序时请先使用题目中的示例数据，然后再自行设计多组测试数
2、据进行调试。3. 每题一般有0个测试点，测试有严格的时间限制,请尽可能优化算法.4. 命名规则:（1)每题都规定了该题的英文名称。(2）程序文件和数据文件的主文件名都是该题的英文名字.（3)程序文件扩展名采用语言环境的默认扩展名.(4）数据文件都是文本文件,输入和输出文件的扩展名分别是.n和.ut。5. 程序应从输入文件读取数据，并严格地按照规定的输出格式将结果输出到输出文件中。输入数据文件和输出数据文件都与程序在同一个目录中,由于程序所在目录是不确定的,因此不允许在文件名中含有盘符信息和任何形式的路径信息.6. 选手在竞赛结束时应在指定分区的根目录下建立以参赛号命名的文件夹,并将所完成各题的
3、源程序文件放入到该文件夹中.测试以评测组编译的可执行文件为准，测试系统使用标准的编译指令处理源文件，没有附加任何编译选项,请选手按照考试机器上语言环境的默认配置编译调试自己的程序。由于测试的需要，Pascal源程序不得使用user math。第一题细菌题目描述近期，农场出现了D（D15)种细菌。J要从他的N（N00）头奶牛中尽可能多地选些产奶,但是如果选中的奶牛携带了超过k(kD）种不同细菌，所生产的奶就不合格。请你帮助Joh计算出最多可以选择多少头奶牛.输入格式第1行：三个整数N，D，K。下面N行:第i行表示一头牛携带的细菌情况。第一个整数di表示这头牛所携带的细菌种类数，后面i个整数表示这
4、些细菌的各自种类标号。输出格式一个数，最大可选奶牛数。输入样例6 2 1 1 32 1 2 1输出样例5样例说明选择,3，5,6头奶牛，只有1和2两种细菌.第二题 水流题目描述全球气候变暖，小镇A面临水灾,于是你必须买一些泵把水抽走。泵的抽水能力可以认为是无穷大,但你必须把泵放在合适的位置，从而能使所有的水能流到泵里。小镇可以认为是NM的矩阵,矩阵里的每个单元格都是一个az小写字母，该小写字母表示该格子的高度,字母大的表示该单元格比较高,反之表示该格子高度比较低。当前单元格的水可以流到上、下、左、右四个格子,但必须满足这些格子的高度是小于或者等于当前格子的高度。现在，给你一些M的矩阵，你至少要
5、买多少个泵，才能把所有格子的水都抽走？输入格式多组测试数据。第1行：K,表示有k组测试数据,15。接下来有k组测试数据,每组测试数据格式如下:第行：两个正整数，N,.1N，M50,表示小镇的大小.接下来有N行,每行有M个小写字母，表示小镇的地图。输出格式共K行，每行对应一组数据。至少要买多少个泵，才能把所有格子的水都抽走。输入样例25 5CcccCbbbbCbbcCcccc4 CbababCbbbbCababcCbbcabc输出样例第三题攀墙问题描述最近流行攀岩运动，类似的一种比赛是在一个宽000毫米，高H毫米的墙上，有个支撑点可供攀登用，登上顶者为获胜。支撑点用坐标（x，)表示,墙的左下角坐
6、标为（0，）.为了不太密集，每两个支撑点至少相距300毫米。Bsi知道她可以从一个支撑点上下左右任意地向另一个支撑点移动，但要求两支撑点之间不能超过10毫米才可以。并且如果她爬到-100高度之上时，就可以灵活地直接登顶了。输入格式 第行,两个整数：H和F(101H3000，F000）；第2行到第F+1行，每行两个整数: ，表示一个支撑点的坐标。X表示距左边的距离,y表示距下面的距离。输出格式 只一个整数,表示最少要用的支撑点个数。输入样例00 600 8001600 8001000 2106 300输出样例样例说明攀爬的次序是第个、第3个、第个支撑点。第四题 残缺的数字问题描述可怜的小小在数数字本来有1n这个n个数,但是她一不小心数没了一个数.现在希望找到那个失踪的数。我们只知道0十个数字在这剩下的N1个数中分别出现的次数，你必须依次求出N和X。若有多组解，则全部输出，每行一组。输入格式1行，包含0个数(每个数均不大于300）,分别表示09在N-1个数字中出现的次数。输出格式输出所有可能的N和X，每组一行.按从小到大的顺序排序(为第一关键字,X为第二关键字）。若无解，输出“N SR”。输入样例1 0 1 1 1 文中不足之处，请您见谅！5 / 5
2016年暑期培训--搜索
