【题解】黑色联通块
【题目描述】
输入一个n×n的黑白图像（1表示黑色，0表示白色），任务是统计其中黑色连通块的个数。如果两个黑格子有公共边或者公共顶点，就说它们属于同一个联通块。如下图所示的图形有3个联通块。
【输入描述】
第1行输入一个正整数n（n≤700），此后输入n行，每行是由n个0或1组成的字符串。
【输出描述】
输出连通块的个数
【样例输入】
6 100100 001010 000000 110000 111000 010100
【样例输出】
3
【题解】Ride to Office
【题目描述】
起点与终点相隔4500米。现Charley 需要从起点骑车到终点。但是，他有个习惯，沿途需要有人陪伴，即以相同的速度， 与另外一个人一起骑。而当他遇到以更快的速度骑车的人时，他会以相应的速度跟上这个更快的人。先给定所有与Charley 同路的人各自的速度与出发时间，问Charley 以这种方式跟人，骑完4500米需要多少时间。得出的结果若是小数，则向上取整。
【输入描述】
输入若干组数据，每组数据第一行n(1≤n≤10000),n为0，表示输入结束，接着输入n行数据，每行2个数据，表示速度v和出发时间t，如果t<0，表示陪伴人提早出发了。
【输出描述】
输出对应若干行数据，每行输出1个数，表示最快到达的时间。
【样例输入】
4 20 0 25 -155 27 190 30 240 2 21 0 22 34 0
【样例输出】
780 771
【题解】走出迷宫的最少步数
【题目描述】
一个迷宫由R行C列格子组成，有的格子里有障碍物，不能走；有的格子是空地，可以走。
给定一个迷宫，求从左上角走到右下角最少需要走多少步(数据保证一定能走到)。只能在水平方向或垂直方向走，不能斜着走。
【输入描述】
第一行是两个整数，R和C，代表迷宫的行数和列数。（ 1<= R，C <= 40)
接下来是R行，每行C个字符，代表整个迷宫。空地格子用’.‘表示，有障碍物的格子用’#‘表示。迷宫左上角和右下角都是’.’。
【输出描述】
输出从左上角走到右下角至少要经过多少步（即至少要经过多少个空地格子）。计算步数要包括起点和终点。
【样例输入】
5 5 ..### #.... #.#.# #.#.# #.#..
【样例输出】
9
【题解】公交乘车
【题目描述】
A城市有一条非常特别的街道，该街道在每个公里的节点上都有一个公交车站，乘客可以在任意的公交站点上车，在任意的公交站点下车。乘客根据每次乘坐公交的公里数进行付费，比如，下表就是乘客乘坐不同的公里数要付的费用。（请注意：不一定公里数越高，费用越高，这也是这条街道特别的地方）
一辆公交车单次行驶的公里数一定不超过10公里，一个乘客如果打算乘坐公交车完成n公里（1<=n<=100）的行程，他可以选择无限次的换车来完成行程。
请问，他最少要花多少钱？
【输入描述】
第一行十个整数分别表示公交行走1到10公里的费用（<=500）。注意这些数并无实际的经济意义，即行驶10公里费用可能比行驶一公里少。
第二行一个整数n表示，旅客的总路程数。 （1<=n<=100）
【输出描述】
仅一个整数表示最少费用。
【样例输入】
12 21 31 40 49 58 69 79 90 101 15
【样例输出】
147
【题解】摘花生问题
【题目描述】
Hello Kitty想摘点花生送给她喜欢的米老鼠。
她来到一片有网格状道路的矩形花生地(如下图)，从西北角进去，东南角出来。
地里每个道路的交叉点上都有种着一株花生苗，上面有若干颗花生，经过一株花生苗就能摘走该它上面所有的花生。
Hello Kitty只能向东或向南走，不能向西或向北走。
问Hello Kitty最多能够摘到多少颗花生。
【输入描述】
第一行是一个整数T，代表一共有多少组数据。
接下来是T组数据。
每组数据的第一行是两个整数，分别代表花生苗的行数R和列数 C。
每组数据的接下来R行数据，从北向南依次描述每行花生苗的情况。每行数据有C个整数，按从西向东的顺序描述了该行每株花生苗上的花生数目M。
【输出描述】
对每组输入数据，输出一行，内容为Hello Kitty能摘到得最多的花生颗数。
【样例输入】
2 2 2 1 1 3 4 2 3 2 3 4 1 6 5
【样例输出】
8 16
【数据范围】
1 ≤ T ≤ 100,
1 ≤ R, C ≤ 100,
0 ≤ M ≤ 1000
【题解】采摘花生2
【题目描述】
Hello Kitty又一次来到花生地里摘花生，从左上角进入花生地，从右下角出去，只能向右或者向下，请问Hello Kitty应该沿着什么样的路线走，能够摘到的花生数量最多（假设花生地里没有任何2株的花生一样多，也不存在多条路线能够摘到一样多的花生的情况）？
比如输入：
2 2
1 2
3 4
应该输出：1-3-4，也就是按照1 3 4这三株数量的花生摘过去，能够摘到最多的花生！
【输入描述】
第一行是2个整数m和n（2=<m,n<=100），代表花生地有m行，n列花生！
后面m行，每行有n个整数代表了每行中，每株花生的数量
【输出描述】
输出Hello Kitty按照走过的路线中，摘到每株花生的数量。
【样例输入】
2 2 1 2 3 4
【样例输出】
1-3-4
【题解】将钱分给最多的儿童
【题目描述】
给你一个整数 money ，表示你总共有的钱数（单位为美元）和另一个整数 children ，表示你要将钱分配给多少个儿童。
你需要按照如下规则分配：
所有的钱都必须被分配。
每个儿童至少获得
1美元。没有人获得
4美元。
请你按照上述规则分配金钱，并返回 最多 有多少个儿童获得 恰好 8 美元。如果没有任何分配方案，返回 -1 。
【输入描述】
一行，两个数，第一个数表示money,第二个数表示children
【输出描述】
一行，最多有多少个儿童获得恰好8美元。如果没有任何分配方案，输出-1
【样例1输入】
20 3
【样例1输出】
1
【样例1解释】
最多获得 8 美元的儿童数为 1 。一种分配方案为： - 给第一个儿童分配 8 美元。 - 给第二个儿童分配 9 美元。 - 给第三个儿童分配 3 美元。 没有分配方案能让获得 8 美元的儿童数超过 1 。
【样例2输入】
16 2
【样例2输出】
2
【样例2解释】
每个儿童都可以获得 8 美元。
【题解】电池的寿命
【题目描述】
小S新买了一个掌上游戏机，这个游戏机由两节5号电池供电。为了保证能够长时间玩游戏，他买了很多5号电池，这些电池的生产商不同，质量也有差异，因而使用寿命也有所不同，有的能使用5个小时，有的可能就只能使用3个小时。显然如果他只有两个电池一个能用5小时一个能用3小时，那么他只能玩3个小时的游戏，有一个电池剩下的电量无法使用，但是如果他有更多的电池，就可以更加充分地利用它们，比如他有三个电池分别能用3、3、5小时，他可以先使用两节能用3个小时的电池，使用半个小时后再把其中一个换成能使用5个小时的电池，两个半小时后再把剩下的一节电池换成刚才换下的电池（那个电池还能用2.5个小时），这样总共就可以使用5.5个小时，没有一点浪费。
现在已知电池的数量和电池能够使用的时间，请你找一种方案使得使用时间尽可能的长。
【输入描述】
输入包含多组数据。每组数据包括两行，第一行是一个整数N(2≤N≤1000)，表示电池的数目，接下来一行是N个正整数表示电池能使用的时间。
【输出描述】
对每组数据输出一行，表示电池能使用的时间，保留到小数点后1位。
【样例输入】
2 3 5 3 3 3 5
【样例输出】
3.0 5.5
【题解】营救巨轮
【题目描述】
一艘远洋巨轮在大海中遇到故障，船长库克立刻发出了求救信号。距离最近的辽宁号收到了讯息，时间就是生命，必须尽快赶到那里。
通过侦测，辽宁号获取了一张海洋图。这张图将海洋部分分化成n*n个比较小的单位，其中用1标明的是陆地，用0标明是海洋。船只能从一个格子，移到相邻的四个格子。
为了尽快赶到出事地点，辽宁号最少需要走多远的距离。
【输入描述】
第一行为n,下面是一个n*n的0、1矩阵，表示海洋地图
最后一行为四个小于n的整数，分别表示辽宁号和故障巨轮的位置。
【输出描述】
辽宁号到故障巨轮的最短距离，答案精确到整数。
【样例输入】
3 001 101 100 1 1 3 3
【样例输出】
4
【题解】骨牌铺方格
【题目描述】
有1×n（n<=50）的一个长方形，用一个1×1、1×2和1×3的骨牌铺满方格，请问有多少种铺法？
例如当n=3时为1×3的方格。此时用1×1、1×2和1×3的骨牌铺满方格，共有四种铺法。如下图：
【输入描述】
一个整数n（n<=50）
【输出描述】
骨牌的铺法
【样例输入】
3
【样例输出】
4