【蓝桥日记④】2015第六届省赛（软件类）JavaA组➤答案解析

【蓝桥日记④】2015第六届省赛（软件类）JavaA组➤答案解析

1、熊怪吃核桃

解法：暴力模拟

package sixSession;

/*** 2015第六届 1、熊怪吃核桃 ***/
public class test1 {
    public static void main(String[] args) {
        int n = 1543;
        int throwNum = 0;
        while (n > 0) {
            if (n % 2 == 1) {
                n -= 1;
                throwNum += 1;
            }
            n /= 2;
        }
        System.out.println(throwNum);
    }
}

答案：5

2、星系炸弹

解法：时间函数

package sixSession;

import java.text.SimpleDateFormat;
import java.util.Calendar;

/*** 2015第六届 2、星系炸弹 ***/
public class test2 {
    public static void main(String[] args) {
        Calendar calendar = Calendar.getInstance();
        // 注意 month 是从0开始的
        calendar.set(2014, 10, 9);
        calendar.add(calendar.DATE, 1000);
        SimpleDateFormat smdate = new SimpleDateFormat("yyyy-MM-dd");
        String sdate = smdate.format(calendar.getTime());
        System.out.println(sdate);
    }
}

答案：2017-08-05

3、九数分三组

解法：全排列+剪枝

package sixSession;

/*** 2015第六届 3、九数分三组 ***/
public class test3 {
    public static void main(String[] args) {
        int[] a = {1, 2, 3, 4, 5, 6, 7, 8, 9};
        backtrack(a, 0, 9);
    }

    private static void backtrack(int[] a, int begin, int end) {
        if (begin > 6) {
            int A = a[0] * 100 + a[1] * 10 + a[2];
            int B = a[3] * 100 + a[4] * 10 + a[5];
            if (2 * A != B) return;
        }
        if (begin == end) {
            helper(a);
            return;
        }

        for (int i = begin; i < end; i++) {
            int t = a[begin]; a[begin] = a[i]; a[i] = t;
            backtrack(a, begin + 1, end);
            t = a[begin]; a[begin] = a[i]; a[i] = t;
        }
    }

    private static void helper(int[] a) {
        int A = a[0] * 100 + a[1] * 10 + a[2];
        int B = a[3] * 100 + a[4] * 10 + a[5];
        int C = a[6] * 100 + a[7] * 10 + a[8];
        if (2 * A != B || 3 * A != C) return;
        System.out.print(A + " ");
    }
}

答案：192 219 273 327

4、循环节长度

package sixSession;

import java.util.Vector;

/*** 2015第六届 4、循环节长度 ***/
public class test4 {
    public static int f(int n, int m)
    {
        n = n % m;
        Vector v = new Vector();
        for(;;)
        {
            v.add(n);
            n *= 10;
            n = n % m;
            if(n==0) return 0;
            if(v.indexOf(n)>=0) return v.size() - v.indexOf(n);
        }
    }
    public static void main(String[] args)
    {
        System.out.println(f(1, 8));
        System.out.println(f(8, 3));
        System.out.println(f(11, 13));
        System.out.println(f(39, 190));
    }
}

答案：return v.size() - v.indexOf(n)

5、打印萎形

找规律

package sixSession;

/*** 2015第六届 5、打印萎形 ***/
public class test5 {
    public static void f(int n) {
        String s = "*";
        for (int i = 0; i < 2 * n - 3; i++) s += ".";
        s += "*";

        String s1 = s + "\n";
        String s2 = "";

        for (int i = 0; i < n - 1; i++) {
            s = "." + s.substring(0, s.length() - 3) + "*";
            s1 = s + "\n" + s1;
            s2 += s + "\n";
        }
        System.out.println(s1 + s2);
    }

    public static void main(String[] args) {
        f(7);
    }
}

答案：s.substring(0, s.length() - 3)

6、加法变乘法

解法一：排列组合+回溯法

package sixSession;

/*** 2015第六届 6、加法变乘法 ***/
public class test6 {
    public static void main(String[] args) {
        int[] a = new int[48];
        backtrack(a, 0, 48, 2);
    }

    private static void backtrack(int[] a, int begin, int end, int k) {
        if (k == 0) {
            int pos = check(a);
            if (pos != -1 && pos != 10) System.out.println(pos);
            return;
        }

        for (int i = begin; i < end; i++) {
            a[i] = 1;
            k -= 1;
            backtrack(a, i + 1, end, k);
            k += 1;
            a[i] = 0;
        }
    }

    private static int check(int[] a) {
        int sum = 1, pos = -1;
        boolean multi = false;
        for (int i = 0; i < 48; i++) {
            if (a[i] == 0) {
                sum += i + 2;
                multi = false;
            } else {
                if (multi == false) {
                    if (pos == -1) pos = i + 1;
                    sum -= (i + 1);
                    sum += (i + 1) * (i + 2);
                } else {
                    return -1;
                }
                multi = true;
            }
        }
        return sum == 2015 ? pos : -1;
    }
}

解法二：枚举

package sixSession;

/*** 2015第六届 6、加法变乘法 枚举法 ***/
public class test6_2 {
    public static void main(String[] args) {
        for (int i = 1; i <= 46; i++) {
            for (int j = i + 2; j <= 48; j++) {
                if (i * (i + 1) - (i + i + 1) + j * (j + 1) - (j + j + 1) == 2015 - 1225) {
                    if (i != 10) System.out.println(i);
                }
            }
        }
    }
}

答案：16

7、牌型种数

排列组合+递归

package sixSession;

/*** 2015第六届 7、牌型种数 ***/
public class test7 {
    private static int ans;
    public static void main(String[] args) {
        f(0, 0);
        System.out.println(ans);
    }

    private static void f(int k, int cnt) {
        if (k > 13 || cnt > 13) return;
        if (k == 13 && cnt == 13) {
            ans++;
            return;
        }
        for (int i = 0; i < 5; i++) {
            f(k + 1, cnt + i);
        }
    }
}

答案：3598180

8、移动距离

推理坐标

package sixSession;

import java.util.Scanner;

/*** 2015第六届 8、移动距离 ***/
public class test8 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int w = sc.nextInt();
        int m = sc.nextInt();
        int n = sc.nextInt();
        sc.close();

        int rm = m % w == 0 ? m / w : m / w + 1;
        int rn = n % w == 0 ? n / w : n / w + 1;
        int cm = rm % 2 == 0 ? ((w - m % w + 1) % w) : m % w;
        int cn = rn % 2 == 0 ? ((w - n % w + 1) % w) : n % w;

        int ans = Math.abs(rm - rn) + Math.abs(cm - cn);
        System.out.println(ans);
    }
}

9、垒骰子

解法一：递归(3/5)，heap超出内存

package sixSession;

import java.util.Scanner;

/*** 2015第六届 9、垒骰子 递归 ***/
public class test9 {
    static final int mod = (int)1e9 + 7;
    static final int[] op = {0, 4, 5, 6, 1, 2, 3};
    static boolean[][] conflict = new boolean[7][7];

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), m = sc.nextInt();
        for (int i = 0; i < m; i++) {
            int x = sc.nextInt(), y = sc.nextInt();
            conflict[x][y] = true;
            conflict[y][x] = true;
        }
        sc.close();

        long ans = 0;
        for (int up = 1; up <= 6; up++) {
            ans = (ans +  4 * f(up, n - 1)) % mod;
        }
        System.out.println(ans);
    }

    private static long f(int up, int cnt) {
        if (cnt == 0) {
            return 1;
        }
        long ans = 0;
        for (int u = 1; u <= 6; u++) {
            if (conflict[op[up]][u]) continue;
            ans = (ans + 4 * f(u, cnt - 1)) % mod;
        }
        return ans;
    }
}

解法二：动态规划（4/5）超时

package sixSession;

import java.util.Scanner;

/*** 2015第六届 9、垒骰子 动态规划 ***/
public class test9_2 {
    static final int mod = (int)1e9 + 7;
    static final int[] op = {0, 4, 5, 6, 1, 2, 3};
    static boolean[][] conflict = new boolean[7][7];
    static int[][] dp = new int[2][7];

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), m = sc.nextInt();
        for (int i = 0; i < m; i++) {
            int x = sc.nextInt(), y = sc.nextInt();
            conflict[x][y] = true;
            conflict[y][x] = true;
        }
        sc.close();

        // dp[i][j] 表示在第i层j朝上的方案数
        for (int j = 1; j <= 6; j++) dp[0][j] = 1;

        int cur = 0;
        // 迭代层数
        for (int level = 2; level <= n; level++) {
            cur = 1 - cur; // 滚动数组下标
            //尝试将6个面放在当前一面朝上的方向
            for (int j = 1; j <= 6; j++) {
                dp[cur][j] = 0;
                for (int i = 1; i <= 6; i++) {
                    if (conflict[op[j]][i]) continue;;
                    dp[cur][j] = (dp[cur][j]+ dp[1 - cur][i]) % mod;
                }
            }
        }

        long sum = 0;
        for (int k = 1; k <= 6; k++) {
            sum = (sum + dp[cur][k]) % mod;
        }

        // 利用快速幂求4的n次幂
        long ans = 1;
        long tmp = 4, p = n;
        while (p > 0) {
            if ((p & 1) == 1) {
                ans = ans * tmp % mod;
            }
            tmp = tmp * tmp % mod;
            p >>= 1;
        }

        ans = ans * sum % mod;
        System.out.println(ans);
    }
}

解法三：冲突矩阵的快速幂（AC），长见识了！Σ(⊙▽⊙"a

package sixSession;

import java.util.Map;
import java.util.Scanner;

/*** 2015第六届 9、垒骰子 矩阵乘法 ***/
class M {
    long[][] a = new long[6][6];
    public M() {
        for (int i = 0; i < 6; i++) {
            for (int j = 0; j < 6; j++) {
                a[i][j] = 1;
            }
        }
    }
}

public class test9_3 {
    static final int MOD  = (int)1e9 + 7;
    static final int[] op = {0, 4, 5, 6, 1, 2, 3};


    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), m = sc.nextInt();
        M cMatrix = new M(); // 冲突矩阵
        for (int i = 0; i < m; i++) {
            int x = sc.nextInt(), y = sc.nextInt();
            cMatrix.a[op[x] - 1][y - 1] = 0;
            cMatrix.a[op[y] - 1][x - 1] = 0;
        }
        sc.close();

        M cMatrix_n_1 = mPow(cMatrix, n - 1);
        long sum = 0;
        for (int i = 0; i < 6; i++) {
            for (int j = 0; j < 6; j++) {
                sum = (sum + cMatrix_n_1.a[i][j]) % MOD;
            }
        }

        // 利用快速幂求4的n次幂
        long ans = 1;
        long tmp = 4, p = n;
        while (p > 0) {
            if ((p & 1) == 1) {
                ans = ans * tmp % MOD;
            }
            tmp = tmp * tmp % MOD;
            p >>= 1;
        }

        ans = ans * sum % MOD;
        System.out.println(ans);
    }

    // 利用快速幂求矩阵m的k次方
    private static M mPow(M m, int k) {
        M ans = new M(); // 单位矩阵
        for (int i = 0; i < 6; i++) {
            for (int j = 0; j < 6; j++) {
                ans.a[i][j] = (i == j) ? 1 : 0;
            }
        }
        while (k != 0) {
            if ((k & 1) == 1) {
                ans = mMultiply(ans, m);
            }
            m = mMultiply(m, m);
            k >>= 1;
        }
        return ans;
    }

    private static M mMultiply(M m1, M m2) {
        M ans = new M();

        for (int i = 0; i < 6; i++) {
            for (int j = 0; j < 6; j++) {
                ans.a[i][j] = 0;
                for (int k = 0; k < 6; k++) {
                    ans.a[i][j] = (ans.a[i][j] + m1.a[i][k] * m2.a[k][j]) % MOD;
                }
            }
        }

        return ans;
    }
}

10、灾后重建

解法：最小生成树+并查集+线段树

选择暂时放弃~o(╥﹏╥)o

[参考资料：B站【蓝桥杯JavaA组】2013-2018年试题讲解（附含C语言版）](