A 牛牛打怪兽

解题思路
这道题就是一个树上DFS/BFS的问题，但是我在这里犯了一个错误就是没有考虑递归的最大深度，数据范围为，递归的最大深度就是，所以如果使用DFS来做的话一定要加上合理的剪枝，否则就会爆栈，之后改了BFS，就过了。
参考代码

import java.util.*;

/*
 * public class Point {
 *   int x;
 *   int y;
 * }
 */

public class Solution {
    int N = 100010, M = 2 * N;
    int[] h = new int[N];
    int[] e = new int[M];
    int[] ne = new int[M];
    boolean[] st = new boolean[N];
    int[] dp = new int[N]; // 存储从根节点到该点的消耗
    int[] cnt = new int[N]; // 统计每一个节点的子节点的个数
    int idx;

    void add(int a, int b) {
        e[idx] = b;
        ne[idx] = h[a];
        h[a] = idx ++;
    }

    public int solve (int n, Point[] Edge, int[] f) {
        // write code here

        Arrays.fill(h, -1);

        for(Point p : Edge) {
            int a = p.x;
            int b = p.y;
            add(a, b);
            add(b, a);
        }

        int res = 0;

        dp[1] = f[0];
        Queue<Integer> q = new LinkedList<Integer>();

        q.add(1);
        st[1] = true;

        while(!q.isEmpty()) {
            int u = q.poll();

            int son = 0;
            for(int i=h[u]; i!=-1; i=ne[i]) {
                int j = e[i];

                if(st[j]) continue;

                q.add(j);
                st[j] = true;

                son += 1;

                dp[j] = dp[u] + f[j - 1];
            }

            if(son == 0 && dp[u] <= 2) res ++;
        }

        return res;
    }
}

B 牛牛的冰激凌

解题思路
这道题可以使用DP来解，首先要按照所有冰激凌的制作完成时间从小到大排序，然后定义f[i]表示前i个冰激凌运输完成的最短时间，具体的分析过程如下:

这里只是解决了最短时间的问题，而对于最小的运输次数，可以用同样的方式使用DP来解，也可以做一个简单的分析，一次只能运输n个冰激凌，一共m个冰激凌，则最终最少的次数一定为m / n上取整

参考代码

import java.util.*;


public class Solution {
    /**
     * 两个数表示答案
     * @param n int整型 一次运输的冰激凌数量
     * @param m int整型 总冰激凌数
     * @param t int整型 一次运输的时间
     * @param c int整型一维数组 表示每个冰激凌制作好时间<1e4
     * @return int整型一维数组
     */
    public int[] icecream (int n, int m, int t, int[] c) {
        // write code here
        int inf = 0x3f3f3f3f;

        int[] f = new int[m + 1];
        Arrays.fill(f, inf);
        f[0] = -t;

        // 按照冰激凌的制作完成时间进行排序
        Arrays.sort(c, 0, m);

        for(int i=1; i<=m; i++){
            for(int j=1; j<=Math.min(i, n); j++){
                f[i] = Math.min(f[i], Math.max(f[i-j]+t, c[i-1]) + t);
            }
        }

        int[] res = new int[2];
        res[0] = f[m];
        res[1] = m / n + (m % n == 0 ? 0 : 1);

        return res;
    }
}

C 数列求值

解题思路
这道题的的值很大，而一般遇到数列递推的题，首先想到的就是矩阵快速幂，而矩阵快速幂的难点在于一个递推数组的建立，我们将初始时的,看做行向量st = {a0, a1},则如果想得到{a1, a2}, 需要乘上的方阵为{{0, c}, {1, b}},故最终需要求解的

参考代码

import java.util.*;


public class Solution {
    /**
     * 输出序列的第n项
     * @param n long长整型 序列的项数
     * @param b long长整型 系数
     * @param c long长整型 系数
     * @return long长整型
     */
    int N = 2, MOD = (int)1e9 + 7;

    void mul(long[] a, long[][] b){
        long[] tmp = new long[N];

        for(int i=0; i<N; i++){
            for(int j=0; j<N; j++){
                tmp[i] = (tmp[i] + a[j] * b[j][i] % MOD) % MOD;
            }
        }

        for(int i=0; i<N; i++) a[i] = tmp[i];
    }

    void mul(long[][] a, long[][] b){
        long[][] tmp = new long[N][N];

        for(int i=0; i<N; i++){
            for(int j=0; j<N; j++){
                for(int k=0; k<N; k++){
                    tmp[i][j] = (tmp[i][j] + a[i][k] * b[k][j] % MOD) % MOD;
                }
            }
        }

        for(int i=0; i<N; i++){
            for(int j=0; j<N; j++){
                a[i][j] = tmp[i][j];
            }
        }
    }

    public long nthElement (long n, long b, long c) {
        // write code here
        long[] res = {0, 1};
        long[][] A = {{0, c}, {1, b}};

        long t = n;
        while(t != 0){
            if(t % 2 != 0) mul(res, A);
            mul(A, A);
            t /= 2;
        }

        return res[0];
    }
}