S2 初级场第三场 A、B、C题（java版题解）

题目A：https://ac.nowcoder.com/acm/contest/9246/A

题解：首先对数组DEF进行升序排序，对于第i个怪物来说，它的防御值为DEF[i]，如果杀死第i - 1个怪物所需的天数为res，那么杀死第i个怪物的天数为res = Math.max(res + 1, DEF[i]）

java代码实现：

import java.util.*;
public class Solution {
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 * 
 * @param n int整型 
 * @param DEF int整型一维数组 
 * @return int整型
 */
public int Minimumdays (int n, int[] DEF) {
    Arrays.sort(DEF);
    int res = Integer.MIN_VALUE;
    for(int i = 0; i < n; i++){
        res = Math.max(res + 1, DEF[i]);
    }
    return res;
}
}

题目B：https://ac.nowcoder.com/acm/contest/9246/B

题解：由于a[1]=2，a[2]=6，且对于所有的n>=3,a[n] = 2a[n-1] + 3a[n-2]，则观察得出a[2] = 3a[1]，那么a[3] = 2a[2] + 3a[1] = 2a[2] + a[2] = 3[2]，以此类推a[n] = 3a[n-1]，是一个首项为2，公比为3的等比数列，因此a[n] = 2X3^(n - 1)。同理对于b[1]=7,b[2]=35,且所有的n>=3,b[n] = 3b[n-1] + 10b[n-2]来说，b[n] = 7X5^(n - 1)。那么c[n] = a[n]Xb[n]=14X15^(n-1)。
因此可以使用快速幂法求出15^(n-1)，在这里每一步都对mod=1e+9进行取余运算，关于快速幂法的解释可参见算法学习笔记(4):快速幂，这道题也可以使用矩阵快速幂的方法，具体做法可以自己去查下资料

java代码实现：

import java.util.*;
public class Solution {
/**
* 返回c[n]%1000000007的值
* @param n long长整型 即题目中的n
* @return int整型
*/
//快速幂法
int mod = (int)1e9+7;
public long power(long a, long b){
    long res = 1;
    while(b != 0){
        if((b & 1) == 1)
        res = (res * a) % mod;
        a = (a * a) % mod;
        b = b >> 1;
    }
    return res;
}

public int Answerforcn (long n) {
    return (int)(14 * power((long)15, n - 1) % mod);
}
}

题目C：https://ac.nowcoder.com/acm/contest/9246/C

题解：假设数组a[]为完全k叉树的层序遍历(bfs序)，那么a[i]的第j个孩子节点为a[i * k + j]，而题目只给出了先序遍历(dfs序)，由于dfs序不能通过数组下标来判断孩子节点是否存在，同时bfs可以通过bfsOrder * k + i < n是否成立来进行判断，因此可以在进行先序遍历的同时来维护一个层序遍历来进行判断，具体可参见代码

java代码实现：

import java.util.*;
public class Solution {
/**
 *
 * @param k int整型 表示完全k叉树的叉数k
 * @param a int整型一维数组 表示这棵完全k叉树的Dfs遍历序列的结点编号
 * @return long长整型
 */
int dfsOrder = 0;
long res = 0;
//注意这里bfsOrder要使用long，因为bfsOrder * k + i可能会超过int    
public void dfs(int k, int[] a, long bfsOrder, int n){
    if(dfsOrder >= n)
        return;
    int parent = a[dfsOrder];//获得父亲节点的值
    for(int i = 1; i <= k; i++){//依次判断k个孩子节点是否存在
        if(bfsOrder * k + i < n){//通过bfs序来判断第i个孩子节点是否存在
            dfsOrder++;
            res += (parent ^ a[dfsOrder]);
            dfs(k, a, bfsOrder * k + i, n);//递归地对第i个孩子节点进行dfs(先序遍历)
        }else
            break;
    }
}

public long tree6 (int k, int[] a) {
     dfs(k, a, 0, a.length);
     return res;
}
}

这里顺便写下根据完全k叉树的先序遍历创建完全k叉树，然后在进行层序遍历的过程中计算结果，下面贴下代码（只能过80%，可能是在节点过多的情况下超出限制内存）：

import java.util.*;
public class Solution {
    //k叉树节点
    public class Node{
        public int val;
        public Node[] child;
        public Node(int data, int k){
            this.val = data;
            child = new Node[k];
        }
    }

    int dfsOrder = 0;
    //根据先序遍历创建完全k叉树
    public Node createTree(int k, int[] a,int bfsOrder){
        if(dfsOrder >= a.length)
            return null;
        Node head = new Node(a[dfsOrder], k);
        for(int i = 1; i <= k; i++){
            if(bfsOrder * k + i < a.length){
                dfsOrder++;
                head.child[i - 1] = createTree(k, a, bfsOrder * k + i);
            }else{
                break;
            }
        }
        return head;
    }

    /**
     *
     * @param k int整型 表示完全k叉树的叉数k
     * @param a int整型一维数组 表示这棵完全k叉树的Dfs遍历序列的结点编号
     * @return long长整型
     */
    public long tree6 (int k, int[] a) {
        Node head = createTree(k, a, 0);//创建完全k叉树
        long res = 0;
        Queue queue = new LinkedList();
        queue.add(head);
        while(!queue.isEmpty()){
            int size = queue.size();
            for(int i = 0; i < size; i++){
                Node cur = queue.poll();//父亲节点
                for(int j = 0; j < k; j++){
                    if(cur.child[j] != null){
                        res += (long)(cur.val ^ cur.child[j].val);
                        queue.add(cur.child[j]);
                    }
                }
            }
        }
        return res;
    }
}

#笔试题目#