第九届蓝桥杯JavaB组(2018年)省赛题解

开开心心刷题，快快乐乐学习，踏踏实实工作，路漫漫其修远兮，吾将上下而求索！！！

1.第几天
热身题，注意闰年二月是29天就可以。

public class Main {
    static int days = 0 ;
    static int year = 2000 ;
    public static void main(String[] args) {

        for(int i=1; i<=5; i++) {
            switch (i){
                case 1 : case 3 : days+= 31; break ;
                case 2 : days += (isLeap(year)) ?   29 :  28; break ;
                case 4 : days += 30 ; break;
                case 5 : days += 4 ; break;
            }
        }
        System.out.println(days);
    }

    private static boolean isLeap(int year) {
        if((year % 4 == 0 && year % 100 != 0) || year%400==0){
            return true ;
        }
        return false ;
    }
}

2.方格计数
思想：四个象限，求出一个，然后乘以4即可。
xx+yy<=r*r为满足条件的情况。

public class Main {
    public static void main(String[] args) {
        int r = 1000 ;
        int y = r ;
        int ans = 0 ;
        for(int x=1; x<=r; x++){
            while(y>0 && x*x+y*y>r*r){
                y -- ;
            }
            ans += y ;
        }

        System.out.println(ans*4);
    }
}

3.复数幂
思想：用到了Java的BigInteger，就是如下公式的迭代
（a+bi）* (2+3i)
实部：a * 2-b * 3
虚部：a* 3i + 2 * bi

import java.math.BigInteger;

public class Main {
    static BigInteger aa, bb ;
    public static void main(String[] args) {
        BigInteger a = new BigInteger("2") ;
        BigInteger b = new BigInteger("3") ;
         aa = null;
         bb = null ;
        for(int i=1; i<=123455; i++){
            aa = a.multiply(new BigInteger("2")).subtract(b.multiply(new BigInteger("3"))) ;
            bb = b.multiply(new BigInteger("2")).add(a.multiply(new BigInteger("3"))) ;
            a = aa ;
            b = bb ;
        }
        System.out.println(a + "" + (b.compareTo(BigInteger.ONE)<=0 ? "" : "+") + b + "i");
    }
}

4.测试次数
思想：递推思想，就是动态规划，这题很容易以为是二分思想，其实和二分没有关系。
1，2，3部手机面对n层楼的最佳策略，仔细观察会发现由递推关系，可以得到递推关系式。

当1部手机，n层楼，测试次数如下：
f1[n] = n
当2部手机,n层楼，测试次数如下：
f2[n]=min(for i in n (max(1+f2[n-i],1+f1[i-1]))）
当3部手机,n层楼，测试次数如下：
f3[n]=min(for i in n (max(1+f3[n-i],1+f2[i-1]))）

public class Main {
    static int N = 1000;
    static int [] f1 ;
    static int [] f2 ;
    static int [] f3 ;
    public static void main(String[] args) {
      f1 = new int [N+1] ;
      f2 = new int [N+1] ;
      f3 = new int [N+1] ;
      for(int i=1; i<=N; i++){
          //1部手机测试次数
          f1[i] = i ;
      }
      //2部手机测试次数
      for(int i=1; i<=N; i++){
          int ans = Integer.MAX_VALUE ;
          for(int j=1; j<=i; j++){
              int max = Math.max(1+f2[i-j], 1+f1[j-1]) ;
              ans = Math.min(ans, max) ;
          }
          f2[i] = ans ;
      }
      //3部手机的测试次数
        for(int i=1; i<=N; i++){
            int ans = Integer.MAX_VALUE ;
            for(int j=1; j<=i; j++){
                //第i层运气最差的情况
                int max = Math.max(1+f3[i-j], 1+f2[j-1]) ;
                //每层运气最差的情况下，选个测试次数最少的
                ans = Math.min(max, ans) ;
            }
            f3[i] = ans ;
        }
        System.out.println(f3[N]);
    }
}

5.代码填空：略

6.递增三元组

方法1：暴力枚举

import java.util.Scanner;


public class Main {
    static int N, cnt = 0 ;
    static int [] a ;
    static int [] b ;
    static int [] c ;
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in) ;
        N = input.nextInt() ;
        a = new int [N] ;
        b = new int [N] ;
        c = new int [N] ;

        for(int i=0; i 
方法2：固定b数组，查询a，c数组，查询过的不再需要扫描，节约时间
 
import java.util.Arrays;
import java.util.Scanner;

public class Main1 {
    static int N ;
    static int [] a ;
    static int [] b ;
    static int [] c ;
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in) ;
        N = input.nextInt() ;
        a = new int [N] ;
        b = new int [N] ;
        c = new int [N] ;
        for(int i=0; ia[j]){
                j ++ ;
            }
            while(k=c[k]){
                k ++ ;
            }
            ans += j * (N - k) ;
        }
        System.out.println(ans);

    }
}

 
7.螺旋直线
 思想：这题十分巧妙，可以把左下角的那条线旋转90度，组成正方形，对每个个坐标先判断内部有多少正方形，求正方形的周长area = 4 * n * (n-1) ;，然后再判断坐标在水平方向还是在树枝方向，
 水平方向： sum += (8*n-d1-d2) ;
 竖直方向： sum += (d1+d2) ;
 
import java.util.Scanner;


public class Main1 {
    static long x, y ;
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in) ;
        x = input.nextLong() ;
        y = input.nextLong() ;
        long n = Math.max(x, y) ; //判断在哪个正方形上
        long area = 4 * n * (n-1) ; //已有正方形的周长

        long d1 = x + n ;
        long d2 = y + n ;
        long sum = 0 ;
        if(x < y){
         sum += (d1+d2) ;
        }else{
            sum += (8*n-d1-d2) ;
        }
        System.out.println(sum+area);

    }
}

 
8.日志统计
 
方法1：数组标记法
 
import java.util.Iterator;
import java.util.Scanner;
import java.util.Set;
import java.util.TreeSet;

public class Main {
    static int N, D, K, ts, id ;
    static long [][] a = new long [10000][10000] ;
    static Set set = new TreeSet<>() ;
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in) ;
        N = input.nextInt() ;
        D = input.nextInt() ;
        K = input.nextInt() ;
        for(int i=0; i=0 && j=K){
                set.add(id) ;
            }
        }
        Iterator iterator = set.iterator() ;
        while (iterator.hasNext()){
            System.out.println(iterator.next());
        }

    }
}

 
方法2：排序后，尺取法
 
import java.util.*;

public class Main1 {
    static int N, D, K ;
    static class R{
        int ts, id ;
    }
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in) ;
        N = input.nextInt()  ;
        D = input.nextInt() ;
        K = input.nextInt() ;
        R [] rs = new R[N] ;
        for(int i=0; i() {
            @Override
            public int compare(R r1, R r2) {
                return r1.ts - r2.ts;
            }
        }) ;
        Map map = new HashMap<>() ; //记录id及其出现的次数
        SortedSet set = new TreeSet<>() ; //记录热帖id

        int j = 0;
        for(int i=0; i=K){
                    set.add(id) ;
                }
                j ++ ;
            }
            if(map.get(rs[i].id) != null){ //剪掉上次尺取中的一个
                map.put(rs[i].id, map.get(rs[i].id)-1) ;
            }
        }
        for(Integer res : set){
            System.out.println(res);
        }
    }
}

 
9.全球变暖
 思想：两轮dfs+标记
 第一轮dfs,把所有岛屿都标为’1’,同时记录岛屿数量，即连通块数量cnt1。
 然后把所有岛屿中不会被淹没的标记为’#’。
 然后第二轮dfs判断不会被淹没的岛屿数量，即‘#’的连通块数量cnt2。
 最后cnt1-cnt2即淹没的岛屿数量。
 
import java.util.Scanner;


public class Main {
    static int N ;
    static char [][] c ;
    static int cnt1 = 0, cnt2 = 0 ;
    static int [] offsetX = {-1, 1, 0, 0} ;
    static int [] offsetY = {0, 0, -1, 1} ;
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in) ;
        N = input.nextInt() ;
        c = new char [N][N] ;
        String s = "" ;
        for(int i=0; i=N || ny>=N){
                continue;
            }
            if(c[nx][ny] == '#'){
                dfs(c, nx, ny) ;
            }
        }
    }
}

 
10.堆的计算
 思想：小根堆+完全二叉树+阶乘+快速幂
 
import java.util.Scanner;


public class Main {
    static final int mod = 1000000009 ;
    static int N ;
    static int [] size ; //记录每个节点的size,即它代表的树的元素个数
    static long [] jie ; //记录1-N的阶乘,记忆法减少重复计算
    static long [] ni ; //存放逆值
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in) ;
        N = input.nextInt() ;
        size = new int [N+1] ;
        jie = new long [N+1] ;
        ni = new long [N+1] ;
        initSize() ;
        initJie() ;
        System.out.println(dp());
    }

    private static long dp() {
        long [] d = new long [N+1] ; //d[i]是第i号节点作为根节点时,小根堆的组合数
        for(int x=N; x>=1; x--){
            if(2*x+1<=N){ //左右子树都存在
                d[x] = c(size[x]-1, size[2*x]) * d[2*x]%mod * d[2*x+1]%mod ;
            }else if(2*x<=N){//仅左子树
                d[x] = c(size[x]-1, size[2*x]) * d[2*x]%mod ;
            }else{//叶子
                d[x] = 1 ;
            }
        }
        return d[1] ;
    }

    private static void initJie() {
        jie[0] = 1 ;
        ni[0] = 1 ;
        for(int i=1; i<=N; i++){
            jie[i] = jie[i-1] * i % mod ;
            ni[i] = pow(jie[i], mod-2) ;
        }
    }

    private static long pow(long a, int n) { //快速幂
        if(a == 0) {
            return 0;
        }
        long ans = 1;
        long x = a;
        while(n > 0) {
            if((n & 1) == 1) {
                ans = ans * x % mod;
            }
            n >>= 1;
            x = x * x % mod;
        }
        return ans;
    }

    private static void initSize() {//节点i为根的树有多少个元素
        for(int i=N; i>=1; i--){
            size[i] = (2*i<=N ? size[2*i] : 0) + (2*i+1<=N ? size[2*i+1] : 0) + 1 ;
        }
    }
    private static long c(int n, int r){ //选左子树的集合种数
        return jie[n] * ni[r]%mod * ni[n-r] ;
    }

}