第一周

第一周：1月28日-2月6日

T1：愤怒小鸟 来源：第七届蓝桥杯-决赛-Java-B组

X星球愤怒的小鸟喜欢撞火车！

一根平直的铁轨上两火车间相距1000米
两火车（不妨称A和B）以时速10米/秒相对行驶。

愤怒的小鸟从A车出发，时速50米/秒，撞向B车，
然后返回去撞A车，再返回去撞B车，如此往复....
两火车在相距1米处停车。

问：这期间愤怒的小鸟撞B车多少次？

注意：需要提交的是一个整数（表示撞B车的次数），不要填写任何其它内容。

解题思路：

代码：

public class T1 {
    public static void main(String[] args) {
        double locateA = 0, locateB = 1000;//A的初始位置为0，B的初始位置为1000
        double crashTime;//撞车时间
        int count = 0;//撞B车的次数统计
        boolean isCrashB = false;//撞的是否是B车
        //两车距离大于1时执行循环
        while (locateB - locateA > 1) {
            crashTime = (locateB - locateA) / 60;
            isCrashB = !isCrashB;//第奇数次循环撞的是B车，第偶数次循环撞的是A车
            if (isCrashB) {
                count++;
            }
            locateA += 10 * crashTime;//小鸟撞车后A的位置
            locateB -= 10 * crashTime;//小鸟撞车后B的位置
        }
        System.out.println(count);
    }
}
输出结果：9

T2：反幻方 来源：第七届蓝桥杯-决赛-Java-B组

我国古籍很早就记载着
2 9 4
7 5 3
6 1 8
这是一个三阶幻方。每行每列以及对角线上的数字相加都相等。
下面考虑一个相反的问题。
可不可以用 1~9 的数字填入九宫格。
使得：每行每列每个对角线上的数字和都互不相等呢？
这应该能做到。
比如：
9 1 2
8 4 3
7 5 6
你的任务是搜索所有的三阶反幻方。并统计出一共有多少种。
旋转或镜像算同一种。
比如：
9 1 2
8 4 3
7 5 6

7 8 9
5 4 1
6 3 2

2 1 9
3 4 8
6 5 7
等都算作同一种情况。
请提交三阶反幻方一共多少种。这是一个整数，不要填写任何多余内容。

解题思路：

1.为了求出有多少种三阶反幻方，需要先求出1-9九个数字的全排列，相当于每一种情况都要判断一遍。这里就要用到深度优先搜索(DFS)的思想。

2.每一种情况，都要判断三行三列以及两对角线相加是否都不同，那么一共可以得到8个值，这8个值都不相同，才满足题意。考虑到Java中的Set集合具有元素不会重复的特性，因此可以将这8个值存入一个Set集合，如果最终集合中有8个元素，说明满足题意，小于8个元素，说明有相同的情况存在，应当舍弃。统计有多少个方阵满足每行每列每个对角线上的数字和都互不相等。

3.因为旋转或镜像算同一种情况，观察一下可以发现，一个方阵通过旋转，可以得到4种不同的形态(旋转0度、90度、180度、270度)，通过镜像，也可以得到4种形态(上下翻转、左右翻转)。因此，一个满足题意的方阵，通过旋转和镜像，会有8种不同的形态。而这8种形态，也必然会在全排列中出现，所以最终满足满足题意的方阵数目 = 每行每列每个对角线上的数字和都互不相等的数目 / 8

DFS三个重点：1.截止条件。2.候选结点。3.筛选。

public class T2 {
    private static int count = 0;

    public static void main(String[] args) {
        //Key：1-9 Value：是否被使用过
        HashMap<Integer, Boolean> map = new HashMap<>();
        for (int i = 1; i <= 9; i++) {
            map.put(i, false);
        }
        LinkedList<Integer> list = new LinkedList<>();//存储结果
        dfs(map, 1, list);//深度优先搜索
        System.out.println(count / 8);//旋转或镜像会有8种不同形态但算同一种情况
    }

    public static void dfs(HashMap<Integer, Boolean> map, int level, LinkedList<Integer> result) {
        //1.截止条件
        if (level > map.size()) {
            //截止后说明一个完整的排列已经生成，可以开始计算行、列、对角线的和
            int row1 = result.get(0) + result.get(1) + result.get(2);
            int row2 = result.get(3) + result.get(4) + result.get(5);
            int row3 = result.get(6) + result.get(7) + result.get(8);
            int col1 = result.get(0) + result.get(3) + result.get(6);
            int col2 = result.get(1) + result.get(4) + result.get(7);
            int col3 = result.get(2) + result.get(5) + result.get(8);
            int diag1 = result.get(0) + result.get(4) + result.get(8);
            int diag2 = result.get(2) + result.get(4) + result.get(6);
            /**
             * 创建一个Set集合，将这些结果存入set中，如果最终set集合中的元素数量不是8，说明有重复的元素
             */
            HashSet<Integer> set = new HashSet<>();
            Collections.addAll(set, row1, row2, row3, col1, col2, col3, diag1, diag2);
            if (set.size() == 8) {
                count++;
            }
            return;
        }
        //2.候选结点
        for (int i = 1; i <= map.size(); i++) {
            //筛选
            if (!map.get(i)) {
                result.push(i);//当前结点的值没有被使用过则可以加入结果集
                map.put(i, true);//加入结果集后要改变状态
                dfs(map, level + 1, result);
                result.pop();//通过出栈将结果集初始化
                map.put(i, false);//将各个结点的使用状态初始化
            }
        }
    }
}

T3：打靶 来源：第七届蓝桥杯-决赛-Java-B组

小明参加X星球的打靶比赛。
比赛使用电子感应计分系统。其中有一局，小明得了96分。

这局小明共打了6发子弹，没有脱靶。
但望远镜看过去，只有3个弹孔。
显然，有些子弹准确地穿过了前边的弹孔。

不同环数得分是这样设置的：
1,2,3,5,10,20,25,50

那么小明的6发子弹得分都是多少呢？有哪些可能情况呢？

下面的程序解决了这个问题。
仔细阅读分析代码，填写划线部分缺失的内容。
public class Main
{	
    static void f(int[] ta, int[] da, int k, int ho, int bu, int sc)
    {
        if(ho<0 || bu<0 || sc<0) return;
        if(k==ta.length){
            if(ho>0 || bu>0 || sc>0) return;
            for(int i=0; i<da.length; i++){
                for(int j=0; j<da[i]; j++) 
                    System.out.print(ta[i] + " ");
            }
            System.out.println();
            return;
        }
        
        for(int i=0; i<=bu; i++){
            da[k] = i;
            f(ta, da, k+1,  __________________ , bu-i, sc-ta[k]*i);   // 填空位置
        }
        
        da[k] = 0;
    }
    
    public static void main(String[] args)
    {
        int[] ta = {1,2,3,5,10,20,25,50};
        int[] da = new int[8];
        f(ta, da, 0, 3, 6, 96);
    }
}
注意：只填写划线处缺少的内容，不要填写已有的代码或符号，也不要填写任何解释说明文字等。

解题思路：

1.经过分析代码，可以得出此题各个参数的含义如下：

数组ta中存放环数分值，数组da里面存放每个分值各打了多少次，k记录DFS中当前所在层数，ho记录还剩多少个弹孔没打，bu记录还剩多少颗子弹，sc记录还剩多少分没打。

2.填空位置是让我们填写递归调用DFS方法的参数ho，ho记录还剩多少个弹孔没有打，按理说此处应该填写ho - 1。但是从for循环中的参数i可以发现，i是从0开始的，当i = 0时，da[k] = i，则此时da[k] = 0，相当于打中da[k]的次数没有增加，则没有增加弹孔。而当i > 0时，则子弹是打在了靶子上的，产生弹孔且只产生一个弹孔。

因此此题答案为：

ho - (i == 0 ? 0 : 1)