蓝桥算法省赛真题总结

发表于 | 分类于 ， | 热度: ℃
字数统计: 3.1k | 阅读时长 ≈ 12

🌸记录蓝桥杯javaB组省赛题目解题方法总结对比

🌸解题方法汇总（java B组省赛）

1 2 3 4 5 6 7 8 9 10
第四届 日期(API)、吉姆拉尔森公式 暴力枚举 暴力深搜 递归、大数类 逻辑模拟 逻辑模拟 暴力查找(类集框架) 模拟过程 全排列、逻辑判断、逻辑枚举的条件判断，枚举所有情况 题意理解，思维的巧妙运用
第五届 数学逻辑 数学逻辑 字符串、暴力模拟 数学、奇偶数 数学逻辑 暴力枚举 全排列、逻辑检查 模拟过程 深度优先、过程模拟搜索、记忆化递归 -1
第六届 简单数学计算 暴力枚举 暴力枚举 模拟过程发现小技巧 全排列 数学规律 递归 模拟过程 递归、动态规划、矩阵快速幂 递归最多一万层
第七届 数学规律 暴力枚举 暴力全排列 组合，规律 递归、组合 暴力、全排列 组合、深搜、图、联通分量 首先暴力、暴力优化（四层到两层）哈希 递归模拟过程、细节很重要 -1
第八届 Excel、耐心敲代码计算、暴力计算器、 全排列 二维数组找规律 -1 过程模拟分析 动态规划 API、日期的细心判断（主要是细心找到每一个满足的条件） 动态规划、扩展欧几里得、完全背包 数学规律、模拟过程 暴力、前缀和优化、取模运算
第九届 日期、计算器（注意加一天） 暴力计算、勾股定理 大数类、数很大输入到文件 动态规划、递归、二分 随机快速排序、递归 暴力、优化（二分）、（双指针） 画图、画过程模拟、找出数学规律、等差数列求和、绝对值的消去 面向对象的思维模拟、类的自定义排序、思维逻辑的严密性 暴力深搜、DFS查找联通分量的个数 -1（乘法逆元）
第十届 综合分析、求最大值 暴力求子串、Set集合 暴力求值、有坑（只需要关注数的后四位，不然数字太大存不了） 暴力分解、条件判断 求最短路径、广度优先、深度优先、节点判断 暴力破解 模拟过程、注意合理运用变量和数组，利用二维数组和多个一维数组可以代替复杂的数据结构 逻辑分析与严密性、字符串正则以及API的使用 逻辑思维的分析与严密性、需要去考虑繁杂的所有可能的情况然后写出结果 -1
第十一届 手工计算、代码计算时注意减法时的边界不能减到负数 日期、计算器、日期类 数学求最值、求算数不等式相等时的边界情况 -1（找规律，用代码去模拟题目要求程序计算的过程） 动态规划、找出存放规律与状态的转移方程 暴力取模、优化（位运算>>取代 / ）(即n = n>> 1 相当于 n = n / 2) 熟练使用API、StringBuilder以及字符串的判断、总的来说就是暴力模拟 深度优先搜索、动态规划 暴力拼接（双重for）、优化（二维数组、位数取取余等） -1
第十二届

🌸黄金分割数与斐波那契数列的关系

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
比较简单的一种是用连分数：
                                   1
    黄金数 = ------------------------------
                                     1
                    1 + ---------------------
                                        1
                           1 + -------------
                                          1
                                 1 + -------
                                       1 + ...
                         
    这个连分数计算的“层数”越多，它的值越接近黄金分割数。
    请你利用这一特性，求出黄金分割数的足够精确值，要求四舍五入到小数点后100位。
    小数点后3位的值为：0.618
    小数点后4位的值为：0.6180
    小数点后5位的值为：0.61803
    小数点后7位的值为：0.6180340

可以分析得出

1
2
3
4
5
6
7
第二层      1/2    后两位
第三层      2/3    后三位
第四层      3/5	后四位
第五层      5/8	后五位
.....
以此类推
即后100位为稳定的100多位的斐波那契数相除，则可以得出代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
import java.math.BigDecimal;
import java.math.BigInteger;

public class Main {
	public static void main(String[] args) {
          
        BigInteger a = BigInteger.ONE;
        BigInteger b = BigInteger.ONE;
        for(int i = 3; i < 500; i++) {
        	BigInteger t = b;
        	b = a.add(b);
        	a = t;
        }
        BigDecimal divide = new BigDecimal(a, 110).divide(new BigDecimal(b, 110), BigDecimal.ROUND_HALF_DOWN);
        System.out.println(divide.toPlainString().substring(0, 103));
	
	}
    //求斐波那契
    static BigDecimal fb(int n){
        BigDecimal a = BigDecimal.ONE;
        BigDecimal b = BigDecimal.ONE;
        for (int i = 0; i < n; i++) {
            BigDecimal t = b;
            b = a.add(b);
            a=t;
        }
        return b;
    }
}

🌸圆周率与连分数

1
2
3
4
5
6
7
8
 4                               1
----   = 1 +  ------------------------------
 N(圆周率)                            9
                 1 + ---------------------
                                       25
                        2 + -----------------
                                         
                              2 + .............
1
2
3
4
5
6
7
double x = 111; 
    for(int n = 10000; n>=0; n--){
        int i = 2 * n + 1;
        x = 2 + (i*i / x);
    }
   
    System.out.println(String.format("%.4f", 4/ (x - 1)));

🌸吉姆拉尔森公式

1
2
3
4
5
6
7
8
9
10
11
private static int whatday(int y, int m, int d) {
	if(m == 1) {
		y--;
		m = 13;
	}
	if(m == 2) {
		y--;
		m = 14;
	}
	return (d + 2 * m + 3 * (m + 1) / 5 + y + y / 4 - y / 100 + y / 400) % 7 + 1;
}

🌸复数幂（复数的阶乘）(了解打印流的使用文本)

复数计算的规律 尝试用 (a+bi)(c+di) = (ac - bd) + (ad + b*c)i 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
import java.io.File;
import java.io.FileNotFoundException;
import java.io.PrintStream;
import java.math.BigInteger;

public class Main {
	public static void main(String[] args) throws FileNotFoundException {
		//System.out.println(getNum(new BigInteger("2"), new BigInteger("3"), new BigInteger("2"), new BigInteger("3")));
		
		BigInteger a = new BigInteger("2");
		BigInteger b = new BigInteger("3");
		BigInteger c = new BigInteger("2");
		BigInteger d = new BigInteger("3");
		int n = 1;
		BigInteger shi;
		BigInteger xu;
		
		while(n < 123456) {
			shi = a.multiply(c).subtract((b.multiply(d)));
			xu = a.multiply(d).add(b.multiply(c));
			n++;
			a = shi;
			b = xu;
		}
		
		if(b.compareTo(new BigInteger("0")) == 1) {
			System.out.println(a + "+" + b + "i");
		}else if(b.compareTo(new BigInteger("0")) == 0) {
			System.out.println(a + "");
		}else {
			System.out.println(a + "" + b + "i");
		}
		
		PrintStream out = System.out;
		PrintStream ps = new PrintStream(new File("ans.txt"));
		System.setOut(ps);;//输出在ans.txt
		System.out.println(a.toString() +b.toString() + "i");
		System.setOut(out);
		System.out.println(a.toString() + b.toString() + "i");
	}

🌸扔鸡蛋问题（摔手机）（面试题）（动态规划）

你将获得 K 个鸡蛋，并可以使用一栋从 1 到 N 共有 N 层楼的建筑。

每个蛋的功能都是一样的，如果一个蛋碎了，你就不能再把它掉下去。

你知道存在楼层 F ，满足 0 <= F <= N 任何从高于 F 的楼层落下的鸡蛋都会碎，从 F 楼层或比它低的楼层落下的鸡蛋都不会破。

每次移动，你可以取一个鸡蛋（如果你有完整的鸡蛋）并把它从任一楼层 X 扔下（满足 1 <= X <= N）。

你的目标是确切地知道 F 的值是多少。

无论 F 的初始值如何，你确定 F 的值的最小移动次数是多少？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
class 鸡蛋解法力扣 {
    static Integer[][] memo = null;
    static public int superEggDrop(int K, int N) {
        memo = new Integer[K+1][N+1];
        return dp(K,N);
    }

    /**
     *当前K个鸡蛋共有N层楼状态时 返回这个状态下确定 F的值的最小移动次数
     */
    static private int dp(int k,int n){
        //base case 层数N等于0时不需要扔鸡蛋,当鸡蛋数K为1时，只能每层逐个尝试剩下所有楼层
        if(k==1)return n;
        if(n<=0)return 0;

        //添加一个备忘录 消除之前算过的重叠子问题
        if(memo[k][n]!=null)
            return memo[k][n];

        int tmp = Integer.MAX_VALUE;

         //第一种 从第1层楼到第n层楼每层楼开始逐个尝试作为切入点 (会超时)
         for(int i=1;i<=n+1;i++){
             //当选择在第i层楼扔了鸡蛋之后 可能出现鸡蛋碎了和鸡蛋没碎两种情况：
             //当鸡蛋碎了 问题状态转嫁为求k-1个鸡蛋 搜索的楼层区间变为1~i-1共i-1层楼时求解
             int eggBreak=dp(k-1,i-1);
             //当鸡蛋没碎 问题状态转嫁为鸡蛋的个数K不变 搜索楼层区间变为i+1~N共N-i层楼时求解
             int eggUnBreak=dp(k,n-i);
             //最终以i层为切入点求解的答案 为两种状态的最坏情况 并加上i层时操作1 并更新最小值
             tmp = Math.min(tmp,Math.max(eggBreak,eggUnBreak)+1);
         }

        //第二种 利用二分查找的方式直接找到对应点(AC通过)
        //第一种线性逐个尝试切入点 然后求每个切入点两种状态的较大值 再求这些最大值之中的最小值 其实就是求这两条单调递增和单调递减直线的交点 相当于求上半部V形山谷值 二分查找来快速寻找这个点
//        int lo=1,hi =n;
//        while(lo<=hi){
//            int mid =(lo+hi)/2;
//            int eggBreak = dp(k-1,mid-1);
//            int eggUnBreak = dp(k,n-mid);
//            if(eggBreak>eggUnBreak){
//                hi = mid-1;
//                tmp = Math.min(tmp,eggBreak+1);
//            }else{
//                lo = mid+1;
//                tmp = Math.min(tmp,eggUnBreak+1);
//            }
    //    }

        //添加到备忘录里
        memo[k][n]=tmp;
        //返回当前k个鸡蛋n层楼时求解的子问题的结果
        return tmp;
    }
    public static void main(String[] args) {
        System.out.println(dp(3,1000));
    }
}

x星球的居民脾气不太好，但好在他们生气的时候唯一的异常举动是：摔手机。

各大厂商也就纷纷推出各种耐摔型手机。x星球的质监局规定了手机必须经过耐摔测试，并且评定出一个耐摔指数来，之后才允许上市流通。

x星球有很多高耸入云的高塔，刚好可以用来做耐摔测试。塔的每一层高度都是一样的，与地球上稍有不同的是，他们的第一层不是地面，而是相当于我们的2楼。

如果手机从第7层扔下去没摔坏，但第8层摔坏了，则手机耐摔指数=7。

特别地，如果手机从第1层扔下去就坏了，则耐摔指数=0。

如果到了塔的最高层第n层扔没摔坏，则耐摔指数=n

为了减少测试次数，从每个厂家抽样3部手机参加测试。

某次测试的塔高为1000层，如果我们总是采用最佳策略，在最坏的运气下最多需要测试多少次才能确定手机的耐摔指数呢？

请填写这个最多测试次数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
public class Main{
 
    public static void main(String[] args) {
        for(int i=0;i<10;i++)
            for(int j=0;j<10000;j++)
                memo[i][j] = 99999999;//找最小,初始化INF
        System.out.println(f(3,1000));
        //f(k,n)  当前的鸡蛋数  k
        //        需要测试的楼层数  n
    }

    static int[][] memo = new int[10][10000];

    static int f(int k,int n) {
        if(k==1) //当鸡蛋数只有1时，只能线性扫描所有的楼层 n 有多少层就得扔多少次 注意题目条件是运气差。
            return n;

        if(n<=0) //当楼层数0是 没法扔鸡蛋
            return 0;

        if(memo[k][n]!=99999999)  //避免重复计算
            return memo[k][n];

        int result=99999999;
        for(int i=1;i<=n;i++) {  //穷举所有的可能选择
            //当选择在第i层楼扔了鸡蛋之后 可能出现鸡蛋碎了和鸡蛋没碎两种情况：
            //当鸡蛋碎了 问题状态转嫁为求k-1个鸡蛋 搜索的楼层区间变为1~i-1共i-1层楼时求解
            int eggBreak=f(k-1,i-1);
            //当鸡蛋没碎 问题状态转嫁为鸡蛋的个数K不变 搜索楼层区间变为i+1~N共N-i层楼时求解
            int eggUnBreak=f(k,n-i);
            //最终以i层为切入点求解的答案 为两种状态的最坏情况 并加上i层时操作1 并更新最小值

            result= Math.min(result,
                    Math.max(
                            eggBreak,eggUnBreak
                    )+1    //1表示在i层时要扔一次
            );

        }
        memo[k][n]=result;
        return memo[k][n];
    }
 
}

🌸日期类（SimpleDateFormat +Date)

1
2
3
4
5
6
7
8
public static class Main{
    public static void main(){
        SimpleDateFormat format = new SimpleDateFormat("yyyy-mm-dd");
        Date date1 = format.parse("1921-7-23");
        Date date2 = format.parse("2020- 7-1");
        int a = (int)((date2.getTime() - date1.getTime()) / 1000 * 60);//相隔多少分钟
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
//直接使用 Date
public static class Main{
    public static void main(){
        long sum = 36138 * 24 * 60L;
        System.out.println(sum);
        System.out.println(36138 * 24 * 60);
        // long型变量在定义的时候，如果不加“L”,则默认为int型变量
        Date date1 = new Date(21, 7, 23, 12, 0, 0); // 1921
        Date date2 = new Date(120, 7, 1, 12, 0, 0); // 2020
        long time = date2.getTime() - date1.getTime();
        System.out.println(time / (60000));
    }
}

🍁

🍂 fff

-------------本文结束感谢您的阅读-------------
云澈 wechat
扫一扫，用手机访问哦
坚持原创技术分享，您的支持将鼓励我继续创作！
0%