首页 > S2 初级场第三场 A、B、C题(java版题解)
头像
点一把🔥炬
编辑于 2020-11-27 19:43
+ 关注

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;
    }
}

全部评论

(0) 回帖
加载中...
话题 回帖

相关热帖

近期精华帖

热门推荐