WHYZ NOIP复赛资料 （本卷不得外泄，内部使用） NOIP模拟JT 20141104 1 NOIP模拟赛 Problem 卫星照片 切割树 计数 骑士 Program (File Type: satel treecut DigitalCounter kings pas/c/cpp) Input File satel.in treecut.in DigitalCounter.in kings.in Output File satel.out treecut.out DigitalCounter.out kings.out Time Limit 1s 1s 1s 5s Memory Limit 128M 128M 128M 128M WHYZ NOIP复赛资料 （本卷不得外泄，内部使用） NOIP模拟JT 20141104 2 卫星照片(satel) 农夫 John 正在研究他的农场的卫星照片.照片为一个R (1 <=R <= 75) 行 C (1 <= C <= 75) 列的字符矩阵表示.如下图: .................. ..#####.......##.. ..#####......##... .................. #.......###.....#. #.....#####....... 图上的一块相连通的 "#" 表示一群奶牛或一个房间, 两个子"#" 连通的意思是说左右或上下相连.而下面的两块则是分开的: .... .#.. ..#. .... John现在根据卫星照片上的的这些"#"块的形状来判断哪些是牛群,哪些是房间.如果一个"#"块形状的边是水平或垂直的矩形,则是房间.其它的则认为都是牛群.在第一个图中,有三个房间 ( 2x1, 2x5, and 1x1)和2群牛. 请根据输入文件中的数据,统计出房间数和牛群数. 数据中牛群不会包围另一个牛群或房间. 输入格式: satel.in * 第一行,两个整数: R 和 C. * 和 2..R+1行: 第 i+1 行表示照片的第 i 行情况,由 C 字符组成. 输出格式: * 第一行: 房间数. * 第二行: 牛群数. 输入样例 (file satel.in): 5 8 #####..# #####.## ......#. .###...# .###..## 输出样例 (file satel.out): 2 2 WHYZ NOIP复赛资料 （本卷不得外泄，内部使用） NOIP模拟JT 20141104 3 treecut 题目描述： 有一个N个节点的无根树，各节点编号为1..N，现在要求你删除其中的一个点，使分割开的连通块中节点个数都不超过原来的一半多。 数据范围 1 <= N <= 10,000 输入文件 treecut.in 第一行：一个整数N。 后面有N-1行：每行两个整数 X 和 Y，表示一个边连接的两个节点号。 输出文件 treecut.out 输出所有可能选择的点。如果有多个节点，按编号从小到大输出，每个一行。 如果找不到这样的点，输出一行："NONE". 样例 10 1 2 2 3 3 4 4 5 6 7 7 8 8 9 9 10 3 8 3 8 输入 样例说明： 删除3号或8号 节点，则分枝 最多有5个节点 输出 WHYZ NOIP复赛资料 （本卷不得外泄，内部使用） NOIP模拟JT 20141104 4 DigitalCounter 我们有一个N位数字的电子表，当时间到达10^N-1时，下一秒就归0。下面我们给出数字0 到 9的模拟图。 + +---+ +---+ + + +---+ | | | | | | + +---+ +---+ +---+ +---+ | | | | | + +---+ +---+ + +---+ +---+ +---+ +---+ +---+ +---+ | | | | | | | | +---+ + +---+ +---+ + + | | | | | | | | +---+ + +---+ + +---+ 对于每个数字，相邻两个+之间会有一根电子管，当显示该数字时，这些电子管就会发亮。如上图所示：数字0到9，它们的电子管数量分别是：6、2、 5、 5、 4、 5、 6、 3、 7、 5。 设现在的时刻是X, 那么可以算出该时有多少根电子管是亮的。比如：现在时刻是：99，那么共有5 + 5= 10根电子管是亮的。假如从现在时刻开始，再过Y秒后，时刻显示为Z, 我们的问题是：求最小的Y，使得时刻Z发亮的电子管数量与时刻X发亮的电子管数量相等。如：现在X = 99 ，那么再过Y = 5 秒后, 时刻变成了Z = 04, 而时刻Z发亮的电子管数量 = 6 + 4 = 10。于是Y = 5就是你要求的数。 输入： 第一行：一个整数N，表示电子表是10^N进制的。1 <= N <= 15。 对于30%数据，N < 7. 第二行：一个整数X, 表示现在的时刻，可能有前导0。X有N位数字。 输出： 一行：最小的整数Y, 表示从现在X时刻开始，再过Y秒，得到的时刻Z发亮的电子管数量与时刻X发亮的电子管数量相等。 样例1： 输入：DigitalCounter.in 3 007 输出：DigitalCounter.out 11（因为数字007有6+6+3 =15根电子管发亮，所以过11秒后，电子表显示数字018时，才能满足发亮的电子管数量相等。018时刻发亮的电子管数量 = 6 + 2 + 7 = 15） WHYZ NOIP复赛资料 （本卷不得外泄，内部使用） NOIP模拟JT 20141104 5 kings (骑士 5秒) 题目描述： 用字符矩阵来表示一个8x8的棋盘，'.'表示是空格，'P'表示人质，'K'表示骑士。 每一步，骑士可以移动到他周围的8个方格中的任意一格。如果你移动到的格子中有人质（即'P'），你将俘获他。但不能移到出棋盘或当前是'K'的格子中。 请问最少要移动多少步骑士才能俘获所有的人质。 输入文件 kings.in 第一行一个整数N(<=5)，表示有多少个棋盘。即多组测试数据。 每一组有8行，每行8个字符。字符只有'.',大写'P',大写'K'三种字符。'P'和'K'的个数范围都在[1,10]。 输出文件 kings.out 有N行，每行只一个整数，相应棋盘俘获全部人质所需要的最少步数。 样例 2 P......P ........ ........ ........ ...KK... ........ ........ P......P .....P.P ..K....P ....K... ..PP...P ...K..KK ........ K....... KP.K.... 20 9 输入 1 .PPPPKP. ........ ........ ........ ........ ........ ........ ........ 输出 6 本文来源：https://www.wddqw.com/doc/48ce6107ee630b1c59eef8c75fbfc77da2699701.html