【2015年蓝桥杯Java-B组省赛题解】_p8625 [蓝桥杯 2015 省 b] 生命之树测试数据

一、三角形面积（直接数格子）

三角形面积

如图1所示。图中的所有小方格面积都是1。
那么，图中的三角形面积应该是多少呢？

请填写三角形的面积。不要填写任何多余内容或说明性文字。
1
2
3
4
5
6

拆成上下两部分三角形，2 * 7 / 2 + 6 * 7 / 2 = 7 + 21 = 28
答案：28

二、立方变自身（模拟、暴力）

立方变自身

观察下面的现象,某个数字的立方，按位累加仍然等于自身。
1^3 = 1 
8^3  = 512    5+1+2=8
17^3 = 4913   4+9+1+3=17
...

请你计算包括1,8,17在内，符合这个性质的正整数一共有多少个？

请填写该数字，不要填写任何多余的内容或说明性的文字。
1
2
3
4
5
6
7
8
9
10
11

public class Main {
    public static void main(String[] args) {
        int ans = 0;
        for (long i = 1; i <= 10000; i++) {
            long tmp = i * i * i;
            long tmp1 = 0;
            while (tmp > 0) {
                tmp1 += tmp % 10;
                tmp /= 10;
            }
            if (tmp1 == i) {
                System.out.println(tmp1);
                ans++;
            }
        }
        System.out.println(ans);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

答案：6

三、三羊献瑞（模拟、暴力）

三羊献瑞

观察下面的加法算式：

      祥 瑞 生 辉
  +   三 羊 献 瑞
-------------------
   三 羊 生 瑞 气

(如果有对齐问题，可以参看【图1.jpg】)

其中，相同的汉字代表相同的数字，不同的汉字代表不同的数字。

请你填写“三羊献瑞”所代表的4位数字（答案唯一），不要填写任何多余内容。
1
2
3
4
5
6
7
8
9
10
11
12
13
14

暴力、全排列都可以

public class Main {
    public static void main(String[] args) {
        // 三 羊 生 瑞 气 献 祥 辉
        for (int i = 1; i <= 9; i++) {
            for (int j = 0; j <= 9; j++) {
                if (j == i) {
                    continue;
                }
                for (int k = 0; k <= 9; k++) {
                    if (k == i || k == j) {
                        continue;
                    }
                    for (int l = 0; l <= 9; l++) {
                        if (l == i || l == j || l == k) {
                            continue;
                        }
                        for (int m = 0; m <= 9; m++) {
                            if (m == i || m == j || m == k || m == l) {
                                continue;
                            }
                            for (int n = 0; n <= 9; n++) {
                                if (n == i || n == j || n == k || n == l || n == m) {
                                    continue;
                                }
                                for (int o = 1; o <= 9; o++) {
                                    if (o == i || o == j || o == k || o == l || o == m || o == n) {
                                        continue;
                                    }
                                    for (int p = 0; p <= 9; p++) {
                                        if (p == i || p == j || p == k || p == l || p == m || p == n || p == o) {
                                            continue;
                                        }
                                        int a = i * 10000 + j * 1000 + k * 100 + l * 10 + m;
                                        int b = i * 1000 + j * 100 + n * 10 + l;
                                        int c = o * 1000 + l * 100 + k * 10 + p;
                                        if (a == b + c) {
                                            System.out.println(b);
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
    }
}
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

答案：1085

四、五、程序填空题

六、加法变乘法（模拟、暴力）

加法变乘法

我们都知道：1+2+3+ ... + 49 = 1225
现在要求你把其中两个不相邻的加号变成乘号，使得结果为2015

比如：
1+2+3+...+10*11+12+...+27*28+29+...+49 = 2015
就是符合要求的答案。

请你寻找另外一个可能的答案，并把位置靠前的那个乘号左边的数字提交（对于示例，就是提交10）。

注意：需要你提交的是一个整数，不要填写任何多余的内容。
1
2
3
4
5
6
7
8
9
10
11
12

假设需要改变的数是：x y z w，x与y相邻，z与w相邻，y和z相间，只需要找到x y z w使得，1225 - x - y - z - w + x * y + z * w = 2015即可。

public class Main {
    public static void main(String[] args) {
        for (int i = 1; i <= 49; i++) {
            int j = i + 1;
            // 注意两个加号不相邻
            for (int k = j + 2; k <= 49; k++) {
                int l = k + 1;
                if (1225 - i - j - k - l + i * j + k * l == 2015) {
                    System.out.println(i);
                }
            }
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

答案：16

七、※牌型种类（搜索）

牌型种数

小明被劫持到X赌城，被迫与其他3人玩牌。
一副扑克牌（去掉大小王牌，共52张），均匀发给4个人，每个人13张。
这时，小明脑子里突然冒出一个问题：
如果不考虑花色，只考虑点数，也不考虑自己得到的牌的先后顺序，自己手里能拿到的初始牌型组合一共有多少种呢？

请填写该整数，不要填写任何多余的内容或说明文字。
1
2
3
4
5
6
7
8

搜索题，注意搜索时要判断当前遍历的poker点数的数量是否=0，为0就只能跳过，不为零就可以取，也可以不取（回溯）。题目中要求的是组合，如果求排列每次都需要从0开始遍历。

import java.util.LinkedList;

public class Main {
    static LinkedList<Character> tmp = new LinkedList<>();
    static int ans = 0;
    public static void main(String[] args) {
        // 52 张牌
        // 2 A K Q J 10 9 8 7 6 5 4 3 都有四张，自己能拿13张
        // 只考虑点数，不考虑得到牌的先后顺序，就是求组合
        int[] nums = new int[13];
        char[] poker = new char[] {'2','A','K','Q','J','1','9','8','7','6','5','4','3'};
        for (int i = 0; i < 13; i++) {
            nums[i] = 4;
        }
        dfs(nums, poker, 0);
        System.out.println(ans);
    }
    static void dfs(int[] nums, char[] poker, int start) {
        if (tmp.size() == 13) {
            System.out.println(tmp);
            ans++;
            return;
        }
        if (tmp.size() > 13) {
            return;
        }
        for (int i = start; i < 13; i++) {
            // 只有剩余牌数 != 0才能拿
            // 剩余牌数 = 0就得考虑下一张牌
            if (nums[i] != 0) {
                nums[i]--;
                tmp.add(poker[i]);
                dfs(nums, poker, i);
                // 回溯：可以不拿当前的牌
                tmp.removeLast();
                nums[i]++;
            } else {
                continue;
            }
        }
    }
}
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

答案：3598180

求组合

import java.util.LinkedList;

public class Main {
    static LinkedList<Integer> tmp = new LinkedList<>();
    public static void main(String[] args) {
        dfs (1);
    }
    static void dfs (int start) {
        if (tmp.size() == 4) {
            System.out.println(tmp);
            return;
        }
        if (tmp.size() > 4) {
            return;
        }
        for (int i = start; i <= 4; i++) {
            tmp.add(i);
            dfs(i + 1);
            tmp.removeLast();
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

求排列

import java.util.LinkedList;

public class Main {
    static LinkedList<Integer> tmp = new LinkedList<>();
    static int[] vis = new int[5];
    public static void main(String[] args) {
        dfs ();
    }
    static void dfs () {
        if (tmp.size() == 4) {
            System.out.println(tmp);
            return;
        }
        if (tmp.size() > 4) {
            return;
        }
        for (int i = 1; i <= 4; i++) {
            if (vis[i] == 0) {
                vis[i] = 1;
                tmp.add(i);
                dfs();
                tmp.removeLast();
                vis[i] = 0;
            }
        }
    }
}
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

八、饮料换购（模拟）

按照题意进行模拟，需要记录总的瓶盖数，每次循环要更新瓶盖数，直到最后瓶盖数 < 3。

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int cnt = n;
        int change = n;
        int tmp = 0;
        while (true) {
            // 兑换的饮料
            cnt += change / 3;
            // 剩余的瓶盖
            tmp = (change / 3 + change % 3);
            change = tmp;
            if (change < 3) {
                System.out.println(cnt);
                break;
            }
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

九、垒骰子（动态规划）

递归代码，超时：

import java.util.Scanner;

public class Main {
    static int n, m;
    static int[] opp = new int[10];
    static boolean[][] conflict = new boolean[10][10];
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        m = scan.nextInt();
        // 记录骰子的对面
        opp[1] = 4;
        opp[2] = 5;
        opp[3] = 6;
        opp[4] = 1;
        opp[5] = 2;
        opp[6] = 3;
        // 记录冲突面
        int a, b;
        for (int i = 0; i < m; i++) {
            a = scan.nextInt();
            b = scan.nextInt();
            // 它们冲突了
            conflict[a][b] = true;
            conflict[b][a] = true;
        }
        long ans = 0;
        // 可以六个面朝上
        for (int i = 1; i <= 6; i++) {
            // 定好了朝上的面，但是侧面的四个面可以转动4次
            ans += 4 * f(i, n - 1);
        }
        System.out.println(ans);
    }
    // 上一层定好了朝上的数字为up的情况下，垒好cnt个骰子的方案数
    static long f(int up, int cnt) {
        // 没有骰子了，返回1（可以由cnt = 1的情况推出）
        if (cnt == 0) {
            return 1;
        }
        long ans = 0;
        for (int i = 1; i <= 6; i++) {
            // 冲突了就继续
            if (conflict[i][opp[up]]) {
                continue;
            }
            // 定好了倒数第二个骰子朝上的面，下一个骰子也还有4种方案数（四个面）
            ans += 4 * f(i, cnt - 1);
        }
        return ans;
    }
}
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

另外一种递归形式：

import java.util.Scanner;

public class Main {
    static int n, m;
    static int[] opp = new int[10];
    static boolean[][] conflict = new boolean[10][10];
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        m = scan.nextInt();
        // 记录骰子的对面
        opp[1] = 4;
        opp[2] = 5;
        opp[3] = 6;
        opp[4] = 1;
        opp[5] = 2;
        opp[6] = 3;
        // 记录冲突面
        int a, b;
        for (int i = 0; i < m; i++) {
            a = scan.nextInt();
            b = scan.nextInt();
            // 它们冲突了
            conflict[a][b] = true;
            conflict[b][a] = true;
        }
        long ans = 0;
        // 可以六个面朝上
        for (int i = 1; i <= 6; i++) {
            // 从第一个筛子开始定
            // 定好了朝上的面，但是侧面的四个面可以转动4次
            ans += 4 * f(i, 1);
        }
        System.out.println(ans);
    }
    static long f(int up, int cnt) {
        // n个筛子都确定好了，那就只有1种情况
        if (cnt == n) {
            return 1;
        }
        long ans = 0;
        for (int i = 1; i <= 6; i++) {
            if (conflict[opp[i]][up]) {
                continue;
            }
            ans += 4 * f(i, cnt + 1);
        }
        return ans;
    }
}
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

我们知道了递归函数形式后，就可以试着推出动态规划的状态转移方程，dp[i][j] 代表第i个面朝上，j个骰子的方案数。所以dp[1][1]…dp[6][1] = 4，对于一个骰子而言，不管哪一面朝上都有4种方案（因为侧面可以旋转）。我们要求的答案ans = dp[1][n] + dp[2][n] + … + dp[6][n]。

dp[1][2] =4 * (dp[1][1] + dp[2][1] + … dp[6][1])，前提是两个骰子相接的面不冲突。

import java.util.Scanner;

public class Main {
    static int n, m;
    static int[] opp = new int[10];
    static boolean[][] conflict = new boolean[10][10];
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        m = scan.nextInt();
        // 记录骰子的对面
        opp[1] = 4;
        opp[2] = 5;
        opp[3] = 6;
        opp[4] = 1;
        opp[5] = 2;
        opp[6] = 3;
        // 记录冲突面
        int a, b;
        for (int i = 0; i < m; i++) {
            a = scan.nextInt();
            b = scan.nextInt();
            // 它们冲突了，注意
            conflict[a][b] = true;
            conflict[b][a] = true;
        }
        long ans = 0;
        // ans = dp[1][n] + dp[2][n] + dp[3][n] + ... + dp[6][n]
        // dp[1][1] = 4
        // dp[2][1] = 4
        // ...
        // dp[6][1] = 4
        // dp[i][j]:i朝上的面，j第几个骰子（从下往上）
        // dp[1][2] = (dp[1][1] + dp[2][1] + ... dp[6][1]) * 4
        long[][] dp = new long[7][n + 1];
        // 初始化，只有一个骰子，每个面朝上都有4种可能（因为侧面可以扭动）
        for (int i = 1; i <= 6; i++) {
            dp[i][1] = 4;
        }
        // i遍历骰子个数
        for (int i = 2; i <= n; i++) {
            // j遍历骰子的面
            for (int j = 1; j <= 6; j++) {
                // 遍历上一个骰子是否与当前骰子的面冲突
                for (int k = 1; k <= 6; k++) {
                    if (conflict[k][opp[j]]) {
                        continue;
                    }
                    dp[j][i] = (dp[j][i] + dp[k][i - 1]) % 1000000007;
                }
                dp[j][i] = (dp[j][i] * 4) % 1000000007;
                if (i == n) {
                    ans = (ans + dp[j][i]) % 1000000007;
                }
            }
        }
        System.out.println(ans);
    }
}
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

上面的代码还不是最优，只能得75分（对我来说够了），需要用滚动数组优化dp数组，否则空间不够。还可以把乘4全部拿到最后求幂运算，用快速幂，就可以加快速度。

可以看到，只要能够想出状态转移方程就已经可以拿很多分了。

十、生命之树（树状DP）

import java.util.*;

public class Main {
	static List<Integer>[] graph;
	static long[] dp;
	static boolean[] vis;
	static long max = Long.MIN_VALUE;
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int n = scan.nextInt();
		dp = new long[n + 1];
		vis = new boolean[n + 1];
		for (int i = 1; i <= n; i++) {
			// 假设每个节点只选择自己，dp数组的值就是自己
			dp[i] = scan.nextInt();
		}
		graph = new LinkedList[n + 1];
		for (int i = 0; i < n + 1; i++) {
			graph[i] = new LinkedList<>();
		}
		for (int i = 0; i < n - 1; i++) {
			int u = scan.nextInt();
			int v = scan.nextInt();
			graph[u].add(v);
			graph[v].add(u);
		}
		// 相当于图，可以从任意节点开始搜索
		dfs(1);
		System.out.println(Math.max(0, max));
	}
	static void dfs(int k) {
		vis[k] = true;
		for (int next : graph[k]) {
			if (vis[next]) continue;
			dfs(next);
			// 对于每个父节点，可以选择选、不选子节点(选一定要能够增大子树和才选，所以需要和0比)
			dp[k] += Math.max(0L, dp[next]);
		}
		max = Math.max(max, dp[k]);
	}
}
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