蓝桥杯第九届省赛Java-B组

发表于 | 更新于 | 分类于 | 阅读次数： | 字数： 5,354 | 阅读时长： 24

第一题：第几天

2000年的1月1日，是那一年的第1天。 那么，2000年的5月4日，是那一年的第几天？

注意：需要提交的是一个整数，不要填写任何多余内容。

日期类题目解题方法如下：

解法1：2000年是闰年二月有29天，一月和三月有31天，四月有30天，所以：31+29+31+30+4=125

解法2：在考场可以拿电脑自带日期计算器：

计算器

解法3：利用vbs脚本：

新建记事本，写入如下代码，把文件后缀txt改为vbs就行。

求两日期间隔类题目：

1
msgbox( DateDiff( "d", "2000-1-1", "2000-5-4") + 1 )

vbs

图：程序运行结果

求一个日期加上指定天数后的日期：

如下：求2015/5/14日加上6天后的日期.

1
msgbox( DateAdd("d", 6, "2018-5-14"))

vbs2

图：程序运行结果

解法4：java编程：更多日期类计算可参考：Java日期与时间的处理

程序源代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
import java.util.Calendar;
import java.util.Date;

public class 第几天 {

	public static void main(String[] args) {
		
		Calendar c1 = Calendar.getInstance();
		c1.set(2000, 1, 1);
		Calendar c2 = Calendar.getInstance();
		c2.set(2000, 5, 4);
		Date d2 = c2.getTime();
		Date d1 = c1.getTime();
		long diff = d2.getTime() - d1.getTime();
		long days = diff / (1000 * 60 * 60 * 24);
		System.out.println(days + 1);
	}
}

程序运行结果：

1
125

第二题：方格计数

如图下图所示，在二维平面上有无数个1x1的小方格。

我们以某个小方格的一个顶点为圆心画一个半径为1000的圆。 你能计算出这个圆里有多少个完整的小方格吗？

注意：需要提交的是一个整数，不要填写任何多余内容。

2

解题思路：只看第一象限，圆心为（0，0），然后遍历第一象限圆内的所有点( i, j )，当且仅当这个点的左上角到圆心的距离小于半径，ans++。最后ans *= 4。

程序源代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class Main {
	/**
	 * 只看第一象限，圆心为（0，0），然后遍历第一象限圆内的所有点( i, j )，当且仅当这
	 * 个点的左上角到圆心的距离小于半径，ans++。最后ans *= 4。
	 * @param args
	 */
	public static void main(String[] args) {
		System.out.println(work(1000));
		
	}

	private static int work(int n) {
		int count = 0;
		for(int i = 1; i <= n; ++i)
			for(int j = 1; j <= n; ++j) {
				int d = i*i + j*j;
				if( d <= n*n)
					++count;
			}
		return count*4;
	}
}

程序运行结果：

1
3137548

第三题：复数幂

设i为虚数单位。对于任意正整数n，(2+3i)^n 的实部和虚部都是整数。 求 (2+3i)^123456 等于多少？

即(2+3i)的123456次幂，这个数字很大，要求精确表示。

答案写成 “实部±虚部i”的形式，实部和虚部都是整数（不能用科学计数法表示），中间任何地方都不加空格，实部为正时前面不加正号。(2+3i)^2 写成: -5+12i，
(2+3i)^5 的写成: 122-597i

注意：需要提交的是一个很庞大的复数，不要填写任何多余内容。

解题思路：把实部和虚部存储，连乘123456次。

程序源代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
public class 复数幂 {

	public static void main(String[] args) {
		//(2 + 3i)(a + bi) = 2a + 2bi + 3ai - 3b
		int a = 2, b = 3;
		for(int i = 1; i < 123456; i++) {
			int temp = 2*a - 3*b;
			b = 3*a + 2*b;
			a = temp;
		}
		System.out.println(a + "+"+b+"i");
	}
}

程序运行结果：

1
13483137+1100011648i

第四题：测试次数

x星球的居民脾气不太好，但好在他们生气的时候唯一的异常举动是：摔手机。

各大厂商也就纷纷推出各种耐摔型手机。x星球的质监局规定了手机必须经过耐摔测试，并且评定出一个耐摔指数来，之后才允许上市流通。

x星球有很多高耸入云的高塔，刚好可以用来做耐摔测试。塔的每一层高度都是一样的，与地球上稍有不同的是，他们的第一层不是地面，而是相当于我们的2楼。

如果手机从第7层扔下去没摔坏，但第8层摔坏了，则手机耐摔指数=7。 特别地，如果手机从第1层扔下去就坏了，则耐摔指数=0。
如果到了塔的最高层第n层扔没摔坏，则耐摔指数=n

为了减少测试次数，从每个厂家抽样3部手机参加测试。

某次测试的塔高为1000层，如果我们总是采用最佳策略，在最坏的运气下最多需要测试多少次才能确定手机的耐摔指数呢？

请填写这个最多测试次数。

注意：需要填写的是一个整数，不要填写任何多余内容。

程序源代码：

1
2


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
package 蓝桥杯2018省赛;

public class 测试次数 {
	public static void main(String[] args) {
		System.out.println(Test(1000, 3));
	}

	private static int Test(int m, int n) {
		if(m < 1 || n < 1)
			return 0;
		//上一层备忘录，存储手机数量-1的m层楼层条件下的最优化尝试次数
		int [] preCache = new int[m + 1];
		//当前备忘录，存储当前鸡蛋数量的m层楼层条件下的最优化尝试次数
		int [] currentCache = new int[m + 1];
		//把备忘录每个元素初始化成最大的尝试次数
		for(int i = 0; i <= m; i++) {
			currentCache[i] = i; 
		}
		for(int i = 2; i <= n; i++) {
			//当前备忘录拷贝给上一次备忘录，并重新初始化当前备忘录
			preCache = currentCache.clone();
			for(int j = 0; j <= m; j++) {
				currentCache[j] = j;
			}
			for(int floor = 1; floor <= m; floor++) {
				for(int k = 1; k < floor; k++) {
					//扔手机的楼层从1到m枚举一遍，如果当前算出的尝试次数小于
					//上一次算出的尝试次数，则取代上一次的尝试次数。
	                //这里可以打印k的值，从而知道第一个手机是从第几次扔的。
					currentCache[floor] = Math.min(currentCache[floor],
						1 + Math.max(preCache[k-1], currentCache[floor-k]));
					
				}
			}
		}
		return currentCache[m];
	}
}

程序运行结果：

1
19

第五题：快速排序

以下代码可以从数组a[]中找出第k小的元素。
它使用了类似快速排序中的分治算法，期望时间复杂度是O(N)的。

请仔细阅读分析源码，填写划线部分缺失的内容。

注意：只提交划线部分缺少的代码，不要抄写任何已经存在的代码或符号。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
> public class Main{ 
> 	public static int quickSelect(int a[], int l, int r, int k) { 
> 		Random rand = new Random(); 
> 		int p = rand.nextInt(r - l + 1) + l; 
> 		int x = a[p]; 
> 		int tmp = a[p]; a[p] = a[r]; a[r] = tmp; 
> 		int i = l, j = r; 
> 		while(i < j) { 
> 			while(i < j && a[i] < x) i++; 
> 			if(i < j) { 
> 				a[j] = a[i]; 
> 				j--; 
> 			} 
> 			while(i < j && a[j] > x) j--; 
> 			if(i < j) { 
> 				a[i] = a[j]; 
> 				i++; 
> 			} 
> 		} 
> 		a[i] = x; 
> 		p = i; 
> 		if(i - l + 1 == k) return a[i]; 
> 		if(i - l + 1 < k) return quickSelect( _______________________ ); //填空 
> 		else return quickSelect(a, l, i - 1, k); 
> 	} 
> 	public static void main(String args[]) { 
> 		int [] a = {1, 4, 2, 8, 5, 7}; 
> 		System.out.println(quickSelect(a, 0, 5, 4)); 
> 	} 
> }
>

答案：a, i+1, r, k-(i-l+1)

第六题：递增三元组

给定三个整数数组 A = [A1, A2, … AN], B = [B1, B2, … BN], C = [C1, C2,
… CN]， 请你统计有多少个三元组(i, j, k) 满足：

  1. 1 <= i, j, k <= N
  2. Ai < Bj < Ck

【输入格式】 第一行包含一个整数N。 第二行包含N个整数A1, A2, … AN。 第三行包含N个整数B1, B2, … BN。
第四行包含N个整数C1, C2, … CN。

对于30%的数据，1 <= N <= 100
对于60%的数据，1 <= N <= 1000
对于100%的数据，1 <= N <=
100000 0 <= Ai, Bi, Ci <= 100000

【输出格式】 一个整数表示答案

【输入样例】
3
1 1 1
2 2 2
3 3 3

【输出样例】
27

资源约定： 峰值内存消耗（含虚拟机） < 256M CPU消耗 < 1000ms

请严格按要求输出，不要画蛇添足地打印类似：“请您输入…” 的多余内容。 所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。
不要使用package语句。不要使用jdk1.7及以上版本的特性。 主类的名字必须是：Main，否则按无效代码处理。

程序源代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
package 蓝桥杯2018省赛;

import java.util.Scanner;

public class 递增三元组 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[] a = new int[n+1];
		int[] b = new int[n+1];
		int[] c = new int[n+1];
		for(int i = 1; i <= n; i++) {
			a[i] = sc.nextInt();
		}
		for(int i = 1; i <= n; i++) {
			b[i] = sc.nextInt();
		}
		for(int i = 1; i <= n; i++) {
			c[i] = sc.nextInt();
		}
		int count = 0;
		for(int i = 1; i <= n; i++) {
			for(int j = 1; j <= n; j++) {
				for(int k = 1; k <= n; k++) {
					if(a[i] < b[j] && b[j] < c[k]) {
						count++;
					}
				}
			}
		}
		System.out.println(count);
	}
}

第七题：螺旋折线

如图所示的螺旋折线经过平面上所有整点恰好一次。 对于整点(X, Y)，我们定义它到原点的距离dis(X,Y)是从原点到(X, Y)的螺旋折线段的长度。

7

例如dis(0, 1)=3, dis(-2, -1)=9

给出整点坐标(X, Y)，你能计算出dis(X, Y)吗？

【输入格式】 X和Y

对于40%的数据，-1000 <= X, Y <= 1000
对于70%的数据，-100000 <= X， Y <= 100000
对于100%的数据, -1000000000 <= X, Y <= 1000000000

【输出格式】 输出dis(X, Y)

【输入样例】 0 1

【输出样例】 3

资源约定： 峰值内存消耗（含虚拟机） < 256M CPU消耗 < 1000ms

请严格按要求输出，不要画蛇添足地打印类似：“请您输入…” 的多余内容。

所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。 不要使用> package语句。不要使用jdk1.7及以上版本的特性。
主类的名字必须是：Main，否则按无效代码处理。

程序源代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
package 蓝桥杯2018省赛;

import java.util.Scanner;

public class 螺旋折线 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int x = sc.nextInt();
		int y = sc.nextInt();
		System.out.println(dis(x, y));
	}

	private static int dis(int x, int y) {
		
		if(x >= 0 && y >=0 && y <=x) {
			int num = 0;
			for(int i = 1; i < x*2; i++) {
				num += i*2;
			}
			return num + x*3 - y;
		}
		if(y >= 0 && x >=0 && y > x) {
			int num = 0;
			for(int i = 1; i < y*2; i++) {
				num += i*2;
			}
			return num + y + x;
		}
		
		if(x < 0 && y > 0 && Math.abs(x) <= y) {
			int num = 0;
			for(int i = 1; i < y*2; i++) {
				num += i*2;
			}
			return num + y - Math.abs(x);
		}
		
		if(x < 0 && y >= 0 && Math.abs(x) > y) {
			int num = 0;
			for(int i = 1; i < Math.abs(x)*2; i++) {
				num += i*2;
			}
			return num - Math.abs(x) + y;
		}
		
		if(x < 0 && y < 0 && Math.abs(x) > Math.abs(y)) {
			int num = 0;
			for(int i = 1; i < Math.abs(x)*2; i++) {
				num += i*2;
			}
			return num - Math.abs(x) - Math.abs(y) ;
		}
		if(x <= 0 && y < 0 && Math.abs(x) <= Math.abs(y)) {
			int num = 0;
			for(int i = 1; i <= Math.abs(y)*2; i++) {
				num += i*2;
			}
			return num + Math.abs(x) + Math.abs(y);
		}
		if(x >= 0 && y < 0 && x <= Math.abs(y)) {
			int num = 0;
			for(int i = 1; i <= Math.abs(y)*2; i++) {
				num += i*2;
			}
			return num + Math.abs(y) - x;
		}
		if(x > 0 && y < 0 && x > Math.abs(y)) {
			int num = 0;
			for(int i = 1; i <= x*2; i++) {
				num += i*2;
			}
			return num - x + Math.abs(y);
		}
		return 0;
	}
}

第八题：日志统计

小明维护着一个程序员论坛。现在他收集了一份”点赞”日志，日志共有N行。其中每一行的格式是：

ts id

表示在ts时刻编号id的帖子收到一个”赞”。

现在小明想统计有哪些帖子曾经是”热帖”。如果一个帖子曾在任意一个长度为D的时间段内收到不少于K个赞，小明就认为这个帖子曾是”热帖”。

具体来说，如果存在某个时刻T满足该帖在[T, T+D)这段时间内(注意是左闭右开区间)收到不少于K个赞，该帖就曾是”热帖”。

给定日志，请你帮助小明统计出所有曾是”热帖”的帖子编号。

【输入格式】 第一行包含三个整数N、D和K。 以下N行每行一条日志，包含两个整数ts和id。

对于50%的数据，1 <= K <= N <= 1000
对于100%的数据，1 <= K <= N <= 100000
0 <= ts<= 100000 0 <= id <= 100000

【输出格式】 按从小到大的顺序输出热帖id。每个id一行。

【输入样例】 7 10 2
0 1
0 10
10 10
10 1
9 1
100 3
100 3

【输出样例】 1 3

资源约定： 峰值内存消耗（含虚拟机） < 256M CPU消耗 < 1000ms

请严格按要求输出，不要画蛇添足地打印类似：“请您输入…” 的多余内容。

所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。 不要使用package语句。不要使用jdk1.7及以上版本的特性。
主类的名字必须是：Main，否则按无效代码处理。

程序代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
package 蓝桥杯2018省赛;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Iterator;
import java.util.List;
import java.util.Scanner;

public class 日志统计 {
	@SuppressWarnings("unchecked")
	public static void main(String[] args) {
		//读取输入数据
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int D = sc.nextInt();
		int K = sc.nextInt();
		int [] ts = new int[N+1];
		int [] id = new int[N+1];
		for(int i = 1; i <= N; i++) {
			ts[i] = sc.nextInt();
			id[i] = sc.nextInt();
		}
		//用来存放热点ID
		List<Integer> hotspotID = new ArrayList<Integer>();
		//idList:用来将日志中的所有id过滤出来
		List idList = new ArrayList<Integer>();
		for(int i = 1; i < N; i++) {
			if(!idList.contains(id[i])) {
				idList.add(id[i]);
			}
		}
		/*
		 * 遍历idList里面的id号，对每个id号进行分段查询统计，看是否为热点id
		 */
		Iterator<Integer> iterator = idList.iterator();
		while(iterator.hasNext()) {
			int ID = iterator.next();
			//time用来存放每个id对应的点赞时间集合
			List time = new ArrayList<Integer>();
			for(int i = 1; i <= N; i++) {
				if(ID == id[i]) {
					time.add(ts[i]);
				}
			}
			//对时间集合进行排序，方便按时间段统计热点次数
			Collections.sort(time);
			//时间集合里面的最小时间
			int beginTime = (int) time.get(0);
			//时间集合里面的最大时间
			int endTime = (int) time.get(time.size()-1);
			//从开始时间（T , T+D）每个时间段的热点进行循环统计
			for(int i = beginTime; i <= endTime ; i += D) {
				beginTime = i;
				//用来存放当前统计时间段的点赞次数
				List<Integer> hotspot = new ArrayList<Integer>();
				for(int j = 0; j < time.size(); j++) {
					int curTime = (int) time.get(j);
					if(beginTime <= curTime && curTime < beginTime+10) {
						 hotspot.add(curTime);
					}
				}
				//如果当前时间段的点赞次数满足大于热点次数K，
				//则将该ID号添加到热点ID序列中。同时跳出循环。
				if(hotspot.size() >= K) {
					hotspotID.add(ID);
					break;
				}
			}
		}
		for(int i = 0 ; i < hotspotID.size(); i++) {
			if(i == hotspotID.size()) {
				System.out.println(hotspotID.get(i));
			}else {
				System.out.print(hotspotID.get(i) + " ");
			}
		}
	}
}

第九题：全球变暖

你有一张某海域NxN像素的照片，”.”表示海洋、”#”表示陆地，如下所示：

1
2
3
4
5
6
7
8
> ....... 
> .##.... 
> .##....
>  ....##. 
> ..####. 
> ...###.
>  .......
>

其中”上下左右”四个方向上连在一起的一片陆地组成一座岛屿。例如上图就有2座岛屿。

由于全球变暖导致了海面上升，科学家预测未来几十年，岛屿边缘一个像素的范围会被海水淹没。具体来说如果一块陆地像素与海洋相邻(上下左右四个相邻像素中有海洋)，它就会被淹没。

例如上图中的海域未来会变成如下样子：

1
2
3
4
5
6
7
8
> ....... 
> ....... 
> .......
> ....... 
> ....#.. 
> .......
> .......
>

请你计算：依照科学家的预测，照片中有多少岛屿会被完全淹没。

【输入格式】 第一行包含一个整数N。 (1 <= N <= 1000) 以下N行N列代表一张海域照片。

照片保证第1行、第1列、第N行、第N列的像素都是海洋。

【输出格式】 一个整数表示答案。

【输入样例】 

1
2
3
4
5
6
7
8
9
> 7
> .......
> .##....
> .##....
> ....##.
> ..####.
> ...###.
> .......
>

【输出样例】 1

资源约定： 峰值内存消耗（含虚拟机） < 256M CPU消耗 < 1000ms

请严格按要求输出，不要画蛇添足地打印类似：“请您输入…” 的多余内容。

所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。 不要使用package语句。不要使用jdk1.7及以上版本的特性。
主类的名字必须是：Main，否则按无效代码处理。

测试数据：

1
2
3
4
5
6
7
8
9
10
11
12
> 10
> ..........
> .##...##..
> ..##..###.
> .###...##.
> .##..##...
> ....##..#.
> ....##....
> .###.##...
> .###......
> ..........
>

淹没后的地图:

1
2
3
4
5
6
7
8
9
10
11
> ..........
> ..........
> .......#..
> ..#.......
> ..........
> ..........
> ..........
> ..........
> ..........
> ..........
>

淹没的岛屿：3

解题思路：

我采用的思路是：首先用dfs计算出没淹没前地图中岛屿的数量。然后处理淹没后的地图，此时再计算出淹没后岛屿的数量。最后输出差值，即为完全淹没的岛屿数量。

java代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
package 蓝桥杯2018省赛;

import java.util.Scanner;

public class 全球变暖 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		char[][] land = new char[n][];
		for(int i = 0; i < n; i++) {
			land[i] = sc.next().toCharArray();
		}
		char[][] land1 = arrCopy(land);//复制地图，防止改变原地图
		int beginCont = 0;//记录水未淹没前的岛屿数量
		for(int i = 0; i < n; i++) { //求水未淹没前的岛屿数量
			for(int j = 0; j < n; j++) {
				if(land1[i][j] == '#') {
					dfs(land1, i, j);
					beginCont++;
				}
			}
		}
		solve(land);//处理水淹没后的地图
		int endCount = 0;//记录水淹没后的岛屿数量
		for(int i = 0; i < n; i++) { //求水淹没后的岛屿数量
			for(int j = 0; j < n; j++) {
				if(land[i][j] == '#') {
					dfs(land, i, j);
					endCount++;
				}
			}
		}
		//淹没前的岛屿数量 - 淹没后的岛屿数量 = 淹没的岛屿数量
		System.out.println(beginCont - endCount);
	}

	//处理水平面升高，淹没岛屿后的地图
	private static void solve(char[][] land) {
		int n = land.length;
		int[][] flag = new int[n][n];
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < n; j++) {
				if(flag[i][j] == 0) {
					if(land[i][j] == '.') {
						if(i - 1 >= 0) {//检查上方
							if(land[i-1][j]  == '#') {
								land[i-1][j] = '.';
								flag[i-1][j] = 1;
							}
						}
						if(i + 1 < n) {//检查下方
							if(land[i+1][j]  == '#') {
								land[i+1][j] = '.';
								flag[i+1][j] = 1;
							}
						}
						if(j - 1 >= 0) {//检查左方
							if(land[i][j-1]  == '#') {
								land[i][j-1] = '.';
								flag[i][j-1] = 1;
							}
						}
						if(j + 1 < n) {//检查右方
							if(land[i][j+1]  == '#') {
								land[i][j+1]= '.';
								flag[i][j+1] = 1;
							}
						}
					}
				}
			}
		}

	}

	//dfs处理，查看地图上有多少个岛屿
	private static void dfs(char[][] land1, int x, int y) {
		land1[x][y] = '.'; //将岛屿去掉
		int n = land1.length;
		//检查每个点的上下左右四个方向
		if(x - 1 >= 0) {//检查上方
			if(land1[x-1][y]  == '#') {
				dfs(land1, x - 1, y);
			}
		}
		if(x + 1 < n) {//检查下方
			if(land1[x+1][y] == '#') {
				dfs(land1, x + 1, y);
			}
		}
		if(y - 1 >= 0) {//检查左方
			if(land1[x][y - 1] == '#') {
				dfs(land1, x, y - 1);
			}
		}
		if(y + 1 < n) {//检查右方
			if(land1[x][y + 1] == '#') {
				dfs(land1, x , y + 1);
			}
			
		}
	}

	//拷贝二维数组
	private static char[][] arrCopy(char[][] land) {
		int n = land.length;
		char[][] land1 = new char[n][n];
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < n; j++) {
				land1[i][j] = land[i][j];
			}
		}
		return land1;
	}

	//输出二维数组，用于测试
	private static void print(char[][] land) {
		for(int i = 0; i < land.length; i++) {
			for(int j = 0; j < land.length; j++) {
				System.out.print(land[i][j]);
			}
			System.out.println();
		}
	}
}

第十题：堆的记数

我们知道包含N个元素的堆可以看成是一棵包含N个节点的完全二叉树。

每个节点有一个权值。对于小根堆来说，父节点的权值一定小于其子节点的权值。

假设N个节点的权值分别是1~N，你能求出一共有多少种不同的小根堆吗？

例如对于N=4有如下3种：

1
2
3
4
5
6
>     1
>    /  \
>   2    3
>  /
> 4
>
1
2
3
4
5
6
>     1
>    / \
>   3   2
>  /
> 4
>
1
2
3
4
5
6
>     1
>    / \
>   2   4
>  /
> 3
>

由于数量可能超过整型范围，你只需要输出结果除以1000000009的余数。

【输入格式】 一个整数N。
对于40%的数据，1 <= N <= 1000
对于70%的数据，1 <= N <= 10000
对于100%的数据，1 <= N <= 100000

【输出格式】 一个整数表示答案。

【输入样例】 4

【输出样例】 3

资源约定： 峰值内存消耗（含虚拟机） < 256M CPU消耗 < 1000ms

请严格按要求输出，不要画蛇添足地打印类似：“请您输入…” 的多余内容。

所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。 不要使用package语句。不要使用jdk1.7及以上版本的特性。
主类的名字必须是：Main，否则按无效代码处理。

坚持原创技术分享，您的支持将鼓励我继续创作！