2014年第五届蓝桥杯决赛Java本科B组试题解析

第一题国王的遗产

X国是个小国。国王K有6个儿子。在临终前，K国王立下遗嘱：国王的一批牛作为遗产要分给他的6个儿子。
其中，大儿子分1/4，二儿子1/5，三儿子1/6，....
直到小儿子分1/9。
牛是活的，不能把一头牛切开分。

最后还剩下11头牛，分给管家。

请计算国王这批遗产中一共有多少头牛。

这是一个整数，请通过浏览器提交答案，不要填写任何多余的内容（比如说明性的文字）

 1 // 国王的遗产
 2 
 3 public class t1 {
 4 
 5     public static void main(String[] args) {
 6 
 7         for (int i = 12; i <= 10000; i++) {
 8             if (i % 4 == 0 && i % 5 == 0 && i % 6 == 0 && i % 7 == 0 && i % 8 == 0 && i % 9 == 0) {
 9                 if (i - i / 4 - i / 5 - i / 6 - i / 7 - i / 8 - i / 9 == 11) {
10                     System.out.println(i);
11                 }
12             }
13         }
14         // answer: 2520
15 
16         // 验算
17         System.out.println(
18                 2520 / 4 + "  " + 2520 / 5 + "  " + 2520 / 6 + "  " + 2520 / 7 + "  " + 2520 / 8 + "  " + 2520 / 9);
19         int res = 2520 - 2520 / 4 - 2520 / 5 - 2520 / 6 - 2520 / 7 - 2520 / 8 - 2520 / 9;
20         System.out.println(res);
21     }
22 
23 }

第二题六角幻方

把 1 2 3 ... 19 共19个整数排列成六角形状，如下：

* * *
* * * *
* * * * *
* * * *
* * *

要求每个直线上的数字之和必须相等。共有15条直线哦！

再给点线索吧！我们预先填好了2个数字，第一行的头两个数字是：15 13，参见图【p1.png】，黄色一行为所求

请你填写出中间一行的5个数字。数字间用空格分开。

这是一行用空格分开的整数，请通过浏览器提交答案，不要填写任何多余的内容（比如说明性的文字等）

解决思路：DFS

 1 // 六角幻方
 2 // 每一行的和应该是38 (1到19的和是190，190/5=38)
 3 
 4 public class t2 {
 5 
 6     public static boolean[] vis = new boolean[20];
 7     public static int[] a = new int[20];
 8 
 9     public static void dfs(int x) {
10         // 剪枝
11         if (x == 8) {
12             if (a[4] + a[5] + a[6] + a[7] != 38)
13                 return;
14         }
15         if (x == 9) {
16             if (15 + a[4] + a[8] != 38)
17                 return;
18         }
19         if (x == 13) {
20             if (a[8] + a[9] + a[10] + a[11] + a[12] != 38)
21                 return;
22             if (a[3] + a[7] + a[12] != 38)
23                 return;
24         }
25         if (x == 14) {
26             if (38 != 13 + a[5] + a[9] + a[13])
27                 return;
28         }
29         if (x == 17) {
30             if (13 + a[6] + a[11] + a[16] != 38 || a[13] + a[14] + a[15] + a[16] != 38)
31                 return;
32         }
33         if (x == 18) {
34             if (a[3] + a[6] + a[10] + a[14] + a[17] != 38 || a[8] + a[13] + a[17] != 38)
35                 return;
36         }
37         if (x == 19) {
38             if (a[7] + a[11] + a[15] + a[18] != 38 || a[4] + a[9] + a[14] + a[18] != 38)
39                 return;
40         }
41         if (x == 20) {
42             // 最后出口
43             if (a[17] + a[18] + a[19] == 38) {
44                 System.out.println(a[8] + " " + a[9] + " " + a[10] + " " + a[11] + " " + a[12]);
45                 // answer: 9 6 5 2 16
46                 return;
47             }
48         }
49         for (int i = 1; i < 20; i++) {
50             if (!vis[i]) {
51                 vis[i] = true;
52                 a[x] = i;
53                 dfs(x + 1);
54                 vis[i] = false;
55             }
56         }
57     }
58 
59     public static void main(String[] args) {
60 
61         a[1] = 15;
62         a[2] = 13;
63         a[3] = 10;
64         vis[15] = vis[13] = vis[10] = true;
65         dfs(4);
66 
67     }
68 
69 }

第三题格子放鸡蛋

  1 X星球的母鸡很聪明。它们把蛋直接下在一个 N * N 的格子中，每个格子只能容纳一枚鸡蛋。它们有个习惯，要求：每行，每列，以及每个斜线上都不能有超过2个鸡蛋。如果要满足这些要求，母鸡最多能下多少蛋呢，有多少种摆放方法呢？
  2  
  3 
  4     下面的程序解决了这个问题，请仔细分析程序逻辑，推断划线处缺少的代码。
  5 
  6 public class A
  7 {
  8     static int max = 0;
  9     static int T = 0;
 10     static final int N = 6;
 11         
 12     // 只能在(r,c) 以及其右，其下放置 
 13     static void f(int[][] da, int r, int c)
 14     {    
 15         if(r>=N){
 16             int n = count(da);
 17             if(n>max) {
 18                 max = n;
 19                 T = 0;
 20             }
 21             if(n==max) T++;
 22             return;
 23         }
 24         
 25         //计算一下步放哪
 26         int r_next = r;
 27         int c_next = c + 1;
 28         if(c_next>=N){
 29             c_next = 0;
 30             r_next++;
 31         }
 32         
 33         if(____________________){  // 填空位置
 34             da[r][c] = 1;
 35             f(da, r_next, c_next); 
 36         }
 37         
 38         da[r][c] = 0;
 39         f(da, r_next, c_next);
 40     }
 41     
 42     static int count(int[][] da)
 43     {
 44         int n = 0;
 45         
 46         for(int i=0; i<da.length; i++)
 47         for(int j=0; j<da[i].length; j++) 
 48             if(da[i][j]==1) n++;
 49             
 50         return n;
 51     }
 52     
 53     static int spy(int[][] da, int r, int c)
 54     {
 55         int m=0;
 56         
 57         // 该行
 58         int n=0;
 59         for(int i=0; i<N; i++) if(da[r][i]==1) n++;
 60         if(n>m) m = n;
 61 
 62         //该列
 63         n=0;
 64         for(int i=0; i<N; i++) if(da[i][c]==1) n++;
 65         if(n>m) m = n;
 66         
 67         //右斜线
 68         n=0;
 69         for(int i=0; i<N; i++){ 
 70             if(r-i<0 || c-i<0) break; 
 71             if(da[r-i][c-i]==1) n++;
 72         }
 73         for(int i=1; i<N; i++){ 
 74             if(r+i>=N || c+i>=N) break; 
 75             if(da[r+i][c+i]==1) n++;
 76         }
 77         if(n>m) m = n;
 78         
 79         //左斜线
 80         n=0;
 81         for(int i=0; i<N; i++){ 
 82             if(r-i<0 || c+i>=N) break; 
 83             if(da[r-i][c+i]==1) n++;
 84         }
 85         for(int i=1; i<N; i++){ 
 86             if(r+i>=N || c-i<0) break; 
 87             if(da[r+i][c-i]==1) n++;
 88         }
 89         if(n > m) m = n;
 90         
 91         return m;
 92     }
 93     
 94     public static void main(String[] args)
 95     {
 96         int[][] da = new int[N][N];
 97         
 98         f(da, 0, 0);
 99         
100         System.out.println(max);
101         System.out.println(T);
102     }
103 }
104 
105 注意：通过浏览器提交答案。只填写缺少的内容，不要填写任何多余的内容（例如：说明性文字或已有符号）。

解决思路：经典算法N皇后问题的变体，读完题可以知道大概是要根据spy函数的调用结果来判断

  1 public class t3 {
  2 
  3     static int max = 0;
  4     static int T = 0;
  5     static final int N = 6;
  6 
  7     // 只能在(r,c) 以及其右，其下放置
  8     static void f(int[][] da, int r, int c) {
  9         if (r >= N) {
 10             int n = count(da);
 11             if (n > max) {
 12                 max = n;
 13                 T = 0;
 14             }
 15             if (n == max)
 16                 T++;
 17             return;
 18         }
 19 
 20         // 计算一下步放哪
 21         int r_next = r;
 22         int c_next = c + 1;
 23         if (c_next >= N) {
 24             c_next = 0;
 25             r_next++;
 26         }
 27 
 28         if (spy(da, r, c) < 2) { // 填空位置
 29             da[r][c] = 1;
 30             f(da, r_next, c_next);
 31         }
 32 
 33         da[r][c] = 0;
 34         f(da, r_next, c_next);
 35     }
 36 
 37     static int count(int[][] da) {
 38         int n = 0;
 39 
 40         for (int i = 0; i < da.length; i++)
 41             for (int j = 0; j < da[i].length; j++)
 42                 if (da[i][j] == 1)
 43                     n++;
 44 
 45         return n;
 46     }
 47 
 48     static int spy(int[][] da, int r, int c) {
 49         int m = 0;
 50 
 51         // 该行
 52         int n = 0;
 53         for (int i = 0; i < N; i++)
 54             if (da[r][i] == 1)
 55                 n++;
 56         if (n > m)
 57             m = n;
 58 
 59         // 该列
 60         n = 0;
 61         for (int i = 0; i < N; i++)
 62             if (da[i][c] == 1)
 63                 n++;
 64         if (n > m)
 65             m = n;
 66 
 67         // 右斜线
 68         n = 0;
 69         for (int i = 0; i < N; i++) {
 70             if (r - i < 0 || c - i < 0)
 71                 break;
 72             if (da[r - i][c - i] == 1)
 73                 n++;
 74         }
 75         for (int i = 1; i < N; i++) {
 76             if (r + i >= N || c + i >= N)
 77                 break;
 78             if (da[r + i][c + i] == 1)
 79                 n++;
 80         }
 81         if (n > m)
 82             m = n;
 83 
 84         // 左斜线
 85         n = 0;
 86         for (int i = 0; i < N; i++) {
 87             if (r - i < 0 || c + i >= N)
 88                 break;
 89             if (da[r - i][c + i] == 1)
 90                 n++;
 91         }
 92         for (int i = 1; i < N; i++) {
 93             if (r + i >= N || c - i < 0)
 94                 break;
 95             if (da[r + i][c - i] == 1)
 96                 n++;
 97         }
 98         if (n > m)
 99             m = n;
100 
101         return m;
102     }
103 
104     public static void main(String[] args) {
105         int[][] da = new int[N][N];
106 
107         f(da, 0, 0);
108 
109         System.out.println(max);
110         System.out.println(T);
111     }
112 
113 }