1. 路径之谜
  2. 广场舞
  3. 机器人塔
  4. 平方末尾
  5. 七星填数

一、路径之谜

小明冒充X星球的骑士，进入了一个奇怪的城堡。 城堡里边什么都没有，只有方形石头铺成的地面。 假设城堡地面是 n x n 个方格。【如图1.png】所示。

图1.jpg

按习俗，骑士要从西北角走到东南角。 可以横向或纵向移动，但不能斜着走，也不能跳跃。 每走到一个新方格，就要向正北方和正西方各射一箭。 （城堡的西墙和北墙内各有 n 个靶子） 同一个方格只允许经过一次。但不必做完所有的方格。 如果只给出靶子上箭的数目，你能推断出骑士的行走路线吗？ 有时是可以的，比如图1.png中的例子。 本题的要求就是已知箭靶数字，求骑士的行走路径（测试数据保证路径唯一）

输入： 第一行一个整数N(0<N<20)，表示地面有 N x N 个方格 第二行N个整数，空格分开，表示北边的箭靶上的数字（自西向东） 第三行N个整数，空格分开，表示西边的箭靶上的数字（自北向南）

输出： 一行若干个整数，表示骑士路径。

为了方便表示，我们约定每个小格子用一个数字代表，从西北角开始编号: 0,1,2,3.... 比如，图1.png中的方块编号为： 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

示例： 用户输入： 4 2 4 3 4 4 3 3 3

程序应该输出： 0 4 5 1 2 3 7 11 10 9 13 14 15

资源约定： 峰值内存消耗 < 256M CPU消耗 < 1000ms 请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。

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

思路：就是DFS，啥也没有，题干一如既往的长，唯一复杂的就是变量多了些。我们直接错（0，0）进行搜素，遍历每个结点，同时保证符合要求即可（注意每次col和row要往同一个方向进行）。看来是有必要认真梳理一下类似的题目了。

这样的搜素必然要有vis[][]记录是否遍历，必然要有dir[][]控制方向。 告诫自己：以后注意采用匈牙利命名法，类似iMax。

完整代码如下： 

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
import java.util.Scanner;

public class Main {
	static int n;
	static int[] row, col;
	static int rowSum;
	static int colSum;
	static int[][] print;//标定每个单元格的数字
	static int[] map;//记录打印顺序，长度为（rowSum+colSum）/2，即len的最终值
	static int len = 0;//记录路径的行进长度
	static int[][] vis;
	static int[][] dir = {{0, 1}, {0, -1}, {-1, 0}, {1, 0}};
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		n = in.nextInt();
		row = new int[n + 1];
		col = new int[n + 1];
		vis = new int[n + 1][n + 1];
		print = new int[n + 1][n + 1];
		map = new int[n*n + 1];
        int index = 0;
        for(int i=0; i<n; ++i) {
        	for(int j=0; j<n; ++j) {
            	print[i][j] = index++;
            }
        }
            
		for (int i = 0; i < n; i++) {
			row[i] = in.nextInt();
			rowSum += row[i];
		}
		for (int i = 0; i < n; i++) {
			col[i] = in.nextInt();
			colSum += col[i];
		}
		
		len = 1;
		vis[0][0] = 1;
		row[0]--;
		rowSum--;
		col[0]--;
		colSum--;
		map[0] = 0;
		f(0, 0);
	}
	private static void f(int x, int y) {
		// TODO Auto-generated method stub
		if (x == n - 1 && y == n - 1) {
			if (colSum == 0 && rowSum == 0) {
				for (int i = 0; i < len; i++) {
					System.out.print(map[i] + " ");
				}
			}
		}
		
		for (int i = 0; i < 4; i++) {
			int dx = x + dir[i][0];
			int dy = y + dir[i][1];
			
			if (dx >= 0 && dx < n && dy >= 0 && dy < n && vis[dx][dy] == 0 && row[dy] > 0 && col[dx] > 0) {
//				row和col要往同一个方向进行，即同时加减。
				vis[dx][dy] = 1;
				row[dy]--;
				rowSum--;
				col[dx]--;
				colSum--;
				map[len++] = print[dx][dy];
				f(dx, dy);
				len--;
				vis[dx][dy] = 0;
				row[dy]++;
				rowSum++;
				col[dx]++;
				colSum++;
			}
		}
	}
}

二、广场舞

LQ市的市民广场是一个多边形，广场上铺满了大理石的地板砖。 地板砖铺得方方正正，就像坐标轴纸一样。 以某四块砖相接的点为原点，地板砖的两条边为两个正方向，一块砖的边长为横纵坐标的单位长度，则所有横纵坐标都为整数的点都是四块砖的交点（如果在广场内）。 广场的砖单调无趣，却给跳广场舞的市民们提供了绝佳的参照物。每天傍晚，都会有大批市民前来跳舞。 舞者每次都会选一块完整的砖来跳舞，两个人不会选择同一块砖，如果一块砖在广场边上导致缺角或者边不完整，则没人会选这块砖。 （广场形状的例子参考【图1.png】）

图1.jpg 现在，告诉你广场的形状，请帮LQ市的市长计算一下，同一时刻最多有多少市民可以在广场跳舞。

【输入格式】 输入的第一行包含一个整数n，表示广场是n边形的（因此有n个顶点）。 接下来n行，每行两个整数，依次表示n边形每个顶点的坐标（也就是说广场边缘拐弯的地方都在砖的顶角上。数据保证广场是一个简单多边形。 【输出格式】 输出一个整数，表示最多有多少市民可以在广场跳舞。

【样例输入】 5 3 3 6 4 4 1 1 -1 0 4

【样例输出】 7

【样例说明】 广场如图1.png所示，一共有7块完整的地板砖，因此最多能有7位市民一起跳舞。

【数据规模与约定】 对于30%的数据，n不超过100，横纵坐标的绝对值均不超过100。 对于50%的数据，n不超过1000，横纵坐标的绝对值均不超过1000。 对于100%的数据，n不超过1000，横纵坐标的绝对值均不超过100000000（一亿）。

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

思路：有ACM经验的大牛一定一眼就能看出来这是个凸包问题，当然人家都不会看这种水平的题......好了，言归正传，想深入了解凸包问题的可以参考下面两篇文章。

蛮力法在求解凸包问题中的应用（JAVA）

分治法在求解凸包问题中的应用（JAVA）--快包算法

单就这个题目，还达不到传统凸包问题的难度，所以不了解也可以做。我们只需要判断在所围面积中的点，它的右侧、下侧、右下侧三个点是否也在范围内就可以了。如果都在范围内那么这个砖就是完整的，反之，不是完整的。

以下图为例，我们可能不能漫无边际的处理任意个点，所以我们可以先找出所有坐标中的x的上下限，y的上下限，即图中红色虚线所围区域。之后对区域中的每个点进行判断。而如何判断一个点是不是在所围区域之内呢？这里需要用到两点式直线方程的概念，我们构成边界的点（x1,y1）(x2,y2)，两两带入两点式，再带入所判断点(x,y)的一个坐标dy，就可以求出另一个坐标dx。而求出来的坐标dx，如果在实际x的左侧，则不再范围内；反之，在范围内。

完整代码如下： 

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
public class Point {
    int x;
    int y;
    public Point(int x, int y) {
        // TODO Auto-generated constructor stub
        this.x = x;
        this.y = y;
    }
}

import java.util.Scanner;

public class Main {
    static int cnt = 0;
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        Point[] points = new Point[n];
        int maxX = 0, minX = 99999999;
        int maxY = 0, minY = 99999999;
        for(int i = 0; i < n; i++) {
            int x = in.nextInt();
            int y = in.nextInt();
            points[i] = new Point(x, y);

            if(points[i].x > maxX) {
                maxX = points[i].x;
            }
            if(points[i].x < minX) {
                minX = points[i].x;
            }

            if(points[i].y > maxY) {
                maxY = points[i].y;
            }
            if(points[i].y < minY) {
                minY = points[i].y;
            }
        }
        for(int i = minX; i < maxX; i++) {  //x的最小值到最大值
            for(int j = minY; j < maxY; j++) {  //y的最小值到最大值
                //判读右、下、右下的三个点是否都在范围内
                if(f(points, i, j) && f(points, i+1, j) && f(points, i, j+1) && f(points, i+1, j+1)) {
                    cnt++;
                }
            }
        }
        System.out.println(cnt);

    }

    public static boolean f(Point[] points, int x, int y) {
        boolean flag = false;
        /**
         * 由于输入时按顺序的，所以计算还简单了，只需要求出0点-1点、1点-2点、2点-3点、3点-4点、(4点-0点)的斜率即可。
         * 其中4点-0点不好求，这里的做法非常巧妙，首先将j赋为4，先将4点和0点比较，之后 j=i,i++ ,避免了双层嵌套还解决了回环的问题。
         * */
        int j = points.length - 1;
        for(int i = 0; i < points.length; i++) {
            // 各点y坐标值的最小值                                                   y坐标值的最大值
            if(y > Math.min(points[i].y, points[j].y) && y <= Math.max(points[i].y, points[j].y)) {
                //两点式获得斜率，确定该点是否在范围内
                double temp = (double) points[i].x + (double)((( y- points[i].y)/ (double)(points[i].y - points[j].y)) * (double)((points[i].x - points[j].x)));
                if(temp < x) {
                    flag = true;
                }
            }
            j = i;
        }
        return flag;
    }
}

三、机器人塔

X星球的机器人表演拉拉队有两种服装，A和B。 他们这次表演的是搭机器人塔。 类似：

图2.jpg

队内的组塔规则是：

A 只能站在 AA 或 BB 的肩上。
B 只能站在 AB 或 BA 的肩上。

你的任务是帮助拉拉队计算一下，在给定A与B的人数时，可以组成多少种花样的塔。 输入一行两个整数 M 和 N，空格分开（0<M,N<500）,分别表示A、B的人数，保证人数合理性。 要求输出一个整数，表示可以产生的花样种数。

例如： 用户输入： 1 2 程序应该输出： 3

再例如： 用户输入： 3 3 程序应该输出： 4

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

解析：由题目分析我们可以知道，只要确定了最后一排的顺序就可以确定一个机器人塔，我们根据这个思路，只要对最后一排进行深搜，将符合条件的情况记录即可。那么这样一个思路我们需要解决的首要问题就是最后一排有几个数，我们要对几个“机器人”进行全排列。因为m+n最多1000个人，所以机器人塔最多会有50层，这里稍微估计一下就能猜出。 

1
2
3
4
5
6
7
8
9
10
11
12
// 求出按三角形排列从第1层到第i层有a[i]个元素，非常巧妙的思路
for (int i = 0; i <= 50; i++) {
	sum += i;
	a[i] = sum;
}
// 求出在n个A和m个B的情况下，最多能摆到第几层。		
for (int i = 0; i <= 50; i++) {
	if (a[i] == m+n) {
		maxRow = i;
		break;
	}
}

只能说有些代码巧妙地难以理解 

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
import java.util.Scanner;

public class Main {
	static int[] a = new int[1005];
	static char[] s = new char[1005];
	static int sum = 0;
	static int m, n;
	static int maxRow;
	static int cnt = 0;
	static int[] vis = new int[1005];
    public static void main(String[] args) {
    	Scanner in = new Scanner(System.in);
    	m = in.nextInt();
    	n = in.nextInt();
    	// 求出按三角形排列从第1层到第i层有a[i]个元素，巧妙至极   	
		for (int i = 0; i <= 50; i++) {
			sum += i;
			a[i] = sum;
		}
		// 求出在n个A和m个B的情况下，最多能摆到第几层。		
		for (int i = 0; i <= 50; i++) {
			if (a[i] == m+n) {
				maxRow = i;
				break;
			}
		}
		dfs(1);
		System.out.println(cnt);
	}
	private static void dfs(int n) {
		// TODO Auto-generated method stub
		if (n == maxRow + 1) {
			if (check(maxRow)) {
				cnt++;
			}
			return;
		}
		if (vis[n] == 0) {
			vis[n] = 1;
			s[n] = 'A';
			dfs(n + 1);
			s[n] = 'B';
			dfs(n + 1);
			vis[n] = 0;
		}
	}
	private static boolean check(int t) {
		char[] temp = new char[1005];
		//	将字符串temp从第1位到第s.length()-1位给从temp的第1位开始赋值	
		System.arraycopy(s, 1, temp, 1, s.length-1);
		int sum_a = 0, sum_b = 0;
		while (t != 0) {
			for (int i = 1; i <= t; i++) {
				if (temp[i] == 'A') {
					sum_a++;
				}
				if (temp[i] == 'B') {
					sum_b++;
				}
			}
			//	t--代表上移一排，但是采用的是对数组更新，缩短	
			for (int i = 1; i <= t-1; i++) {
				if (temp[i] == temp[i + 1]) {
					temp[i] = 'A';
				} else {
					temp[i] = 'B';
				}
			}
			t--;
		}
		if (sum_a == m && sum_b == n) {
			return true;
		}
		return false;
	}
}

四、平方末尾

能够表示为某个整数的平方的数字称为“平方数” 比如，25,64 虽然无法立即说出某个数是平方数，但经常可以断定某个数不是平方数。 因为平方数的末位只可能是：[0, 1, 4, 5, 6, 9] 这6个数字中的某个。 所以，4325435332必然不是平方数。

如果给你一个2位或2位以上的数字，你能根据末位的两位来断定它不是平方数吗？

请计算一下，一个2位以上的平方数的最后两位有多少种可能性？

注意：需要提交的是一个整数，表示2位以上的平方数最后两位的不同情况数。 不要填写任何多余内容（比如，说明解释文字等）

答案：22 解析：水题，采用set存放即可。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;

public class Main {
       public static void main(String[] args) {
		Set<Integer> set = new HashSet<Integer>();
		for (int i = 4; i <= 1000; i++) {
			int sum = (int) Math.pow(i, 2);
			String str = sum + "";
			Integer u = Integer.valueOf(str.substring(str.length()-2));
			set.add(u);
		}
		Iterator it = set.iterator();
		while (it.hasNext()) {
			System.out.println(it.next());

五、七星填数

如图【图1.png】所示。 这里写图片描述 在七角星的14个节点上填入1~14 的数字，不重复，不遗漏。 要求每条直线上的四个数字之和必须相等。 图中已经给出了3个数字。 请计算其它位置要填充的数字，答案唯一。 填好后，请提交绿色节点的4个数字（从左到右，用空格分开）

比如：12 5 4 8 当然，这不是正确的答案。

注意：只提交4个用空格分开的数字，不要填写任何多余的内容。

答案：6 10 3 9 解析：我们首先要对这十四个结点编号，当然编号可以随意定，但是下面的判断语句要对应着修改。这个题就是简单的进行dfs即可。但是要注意这里一定要进行剪枝，虽然不是暴力循环枚举答案，但是回溯递归的的效率其实并没有强很多，所以如果不进行剪枝的话，一定会发生栈溢出。 这里写图片描述 

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
public class Main {
	static int[] a = {1, 2, 3, 4, 5, 7, 8, 9, 10, 12, 13};
	static int [] b;
	static boolean[] c, d;
	public static void main(String[] args) {
		c = new boolean[14];
		d = new boolean[14];
		b = new int[14];
		
		b[0] = 6;
		b[8] = 14;
		b[10] = 11;
		c[0] = true;
		c[8] = true;
		c[10] = true;
		
		f(0);
	}
	private static void f(int i) {
		// 剪枝
		if (i == 9) {
			if (b[1] + b[2] + b[3] + b[4] != b[0] + b[2] + b[5] + b[8]) {
				return;
			}
		}
		if (i == 11) {
			if (b[1] + b[2] + b[3] + b[4] != b[0] + b[3] + b[6] + b[10]) {
				return;
			}
		}
		if (i == 12) {
			if (b[1] + b[2] + b[3] + b[4] != b[1] + b[5] + b[7] + b[11]) {
				return;
			}
		}
		if (i == 13) {
			if (b[1] + b[2] + b[3] + b[4] != b[9] + b[10] + b[11] + b[12]) {
				return;
			}
		}
		if (i == 14) {
			if (b[1] + b[2] + b[3] + b[4] != b[7] + b[8] + b[12] + b[13]) {
				return;
			}
			if (b[1] + b[2] + b[3] + b[4] != b[4] + b[6] + b[9] + b[13]) {
				return;
			}
			for (int j = 0; j < c.length; j++) {
				System.out.print(j==0 ? "" : " ");
				System.out.print(b[j]);
			}
			return;
		}
		if (c[i] == false) {
			for (int j = 0; j < a.length; j++) {
				if (d[j] == false) {
					d[j] = true;
					c[i] = true;
					b[i] = a[j];
					f(i + 1);
					c[i] = false;
					d[j] = false;
				}
			}
		} else {
			f(i + 1);
		}
	}
}