蓝桥杯| 备赛练习题+知识点合集

约分法： a*b = (这两个数字的最大公因数)* (这两个数的最小公倍数)

假设a=18，b=要求最小公倍数。

最大公因： 6 最小公倍数：90 a*b=540 可见18乘30也是如此 540；

所以 最小公倍数 = a*b / (a最大的最大公共因素) = 90 java 实现：

// 最小公倍数=乘积两个数/最大公共因数两个数。     static int gbs(int a,int b) { 
                 return a*b/gcd(a,b) ;     } // 最大公因数 // 这里最大的公因数算法是辗转相除法： a和b(a>b)最大公因数也等于a除以b获得的余数c和b最大公因数。      static int gcd(int a,int b ){ 
                 return a%b==0?b:gcd(a,a%b) ;     } 

参考1:最小公倍数证明 参考2：最大公因数计算&证明

素数/质数 定义为：指在大于1的自然数中，除1和该数本身外，其他自然数不能排除的数。（也可以定义为只有1和该数本身的两个正因数）

• 0和1既不是质数也不是合数，最小质数是2

容易写的代码是:

public static boolean isPrime(int n) { 
             if (n <= 3) { 
                 return n > 1;     }     int sqrt = (int)Math.sqrt(n);     for (int i = 2; i <= sqrt; i++) { 
        
        if(n % i == 0) { 
        
            return false;
        }
    }
    return true;
}

优化思路： 质数还有一个特点，它总是等于6x+1或者6x-1,其中x>=1 证明：

首先 6x 肯定不是质数，因为它能被 6 整除；其次 6x+2 肯定也不是质数，因为它还能被2整除；依次类推，6x+3 肯定能被 3 整除；6x+4 肯定能被 2 整除。那么，就只有 6x+1 和 6x+5 (即等同于6x-1) 可能是质数了。所以循环的步长可以设为 6，然后每次只判断 6 两侧的数即可。

public static boolean isPrime(int num) { 
        
    if (num <= 3) { 
        
        return num > 1;
    }
    // 不在6的倍数两侧的一定不是质数
    if (num % 6 != 1 && num % 6 != 5) { 
        
        return false;
    }
    int sqrt = (int) Math.sqrt(num);
    for (int i = 5; i <= sqrt; i += 6) { 
        
        if (num % i == 0 || num % (i + 2) == 0) { 
        
            return false;
        }
    }
    return true;
}

给定一个长度为N的数列，A1, A2, … AN，如果其中一段连续的子序列Ai, Ai+1, … Aj(i <= j)之和是K的倍数，我们就称这个区间[i, j]是K倍区间。 你能求出数列中总共有多少个K倍区间吗？ 输入 第一行包含两个整数N和K。(1 <= N, K <= 100000) 以下N行每行包含一个整数Ai。(1 <= Ai <= 100000) 输出 输出一个整数，代表K倍区间的数目。

例如， 输入： 5 2 1 2 3 4 5 程序应该输出： 6 资源约定： 峰值内存消耗（含虚拟机） < 256M CPU消耗 < 2000ms

解题思路 首先是想到暴力法，对每一个下标都往前计算包含它的区间，符合题意就ans++ 这样做的复杂度大概是 O(n^2) 对于本题的数据量就是10^6， 直接超时。

下一步优化策略是前缀和：

下标：   0 1 2 3 4 5
原数组Q：1 2 3 4 5
前缀和S：0 1 3 6 10 15  

对应关系： S[i] - S[j] = Arr[j] 但这样做的复杂度依然会很高，（只是将往前遍历的操作优化了一些）依然会超时。

最终思路：需要数学的知识（蓝桥杯的题很多需要数论知识。。）

一个数mod k 的结果肯定是 [0-k-1] ，我们试着前缀和都模k。

下标：    0 1 2 3 4 5
原数组Q： 1 2 3 4 5
前缀和S： 0 1 3 6 10 15  
(S%k)S'：0 1 1 0 0  1  

这时候需要一个数论的定理了，同余定理：如果两个数a，b的差(a-b)能被k整除，那么就说a，b对模数k同余。

比如说 16和7， （16-7)/3 = 3 …0 , 可以得到 16%3=7%3=1 这样的结论。 我们把这个结论反过来用， 前缀和数组模k的若干个 0-k-1的数，相同余数的任意选两个相减实际上就是原数组的一个区间，同时可以被k整除，我们统计这样的组合，答案就出来了。

比如说 S2=S1=S5=1, 用S5-S2==>[3,4,5]，S2-S1=[2], 从中任意挑两个相减，也就是Cm2(组合）从m个数中任意挑选2个相减 。

实现：使用一个yushu数组，用来统计相同余数的前缀和的个数， 对于例子就是：

  下标    0 1 2 3 4  5 
(S%k)S'  0 1 1 0 0  1
yushu    3 3  

题目的答案就是 C32+C32=3+3=6;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
class Main { 
        
    public static void main(String[] args) throws IOException { 
        
        int n=Reader.nextInt() ,k=Reader.nextInt() ;
        int nums[]=new int[n+1],yushu[]=new int [k+1];
        long pre[]=new long[n+1] ;
        long ans =0,last=0 ;
        yushu[0] = 1 ;//注意这里要手动设置为1，因为下面计算前缀和数组时，是从下标1开始计算的。
        for(int i=1;i<=n;i++){ 
        
            nums[i] = Reader.nextInt() ;
            pre[i] = pre[i-1]+nums[i];
            yushu[(int) (pre[i]%k)]++ ;  // 求余数。
        }

        for(int i=0;i<k;i++){ 
        
            ans += (long) (yushu[i] - 1) *yushu[i]/2;
            // 所有前缀和余k相同的数，从中任意选择2个相减就可以得到一个k倍区间，就是组合问题 如C32
            // Cn2= n(n-1)/2;
        }
        System.out.println(ans);
    }

}

最短路问题：我只会dijistra和floyd。 可以用dp做，更优雅。

class Main { 
        
// 最小公倍数=两个数的乘积/两个数的最大公因数。
    static long gbs(int a,int b) { 
        
        return (long) a *b/gcd(b,a) ;
    }
// 最大公因数
    static long gcd(int a,int b ){ 
        
        return a%b==0?b:gcd(a,a%b) ;
    }
    public static void main(String[] args) { 
        
        int n=2021;
        long[][] node = new long[n+1][n+1];

        for(int i=1;i<n+1;i++) Arrays.fill(node[i],Integer.MAX_VALUE) ;
        for(int i=1;i<=n;i++){ 
        
            for (int j = i; j<=i+21; j++) { 
        
                if(j>2021) break ;
                if(i==j) node[i][j] = node[j][i] = 0;
                else  node[i][j] = node[j][i] = gbs(i,j) ;
            }
        }
//floyd处理
        for(int k=1;k<=n;k++){ 
        
            for(int i=1;i<=n;i++){ 
        
                for(int j=1;j<=n;j++){ 
        
                    node[i][j] =Math.min(node[i][j],node[i][k]+node[k][j]) ;
                }
            }
        }
        System.out.println(node[1][2021]) ;
    }
}

A,2,3,4,5,6,7,8,9 共9张纸牌排成一个正三角形（A按1计算）。要求每个边的和相等。 下图就是一种排法 这样的排法可能会有很多。 如果考虑旋转、镜像后相同的算同一种，一共有多少种不同的排法呢？ 请你计算并提交该数字。 注意：需要提交的是一个整数，不要提交任何多余内容。

解题思路

这是一类全排列的题目， 本题就是将9个数字全排列，然后看哪一种组合符合要求。

如何求一组数字的全排列

C++是有全排列的函数的 next_permutation ，我们java党就自己造一个把！

1. 如果只有一个数字，全排列就是他自己。
2. 如果有两个数字，那就每次固定一个数字的位置，然后看下一个怎么排（回到第一点了） 写到这里，就明白是递归了，第一点就是全排列的终止条件，第二点就是每次递归要做的处理。

再仔细讲讲。懂了的可以直接跳过了。看这样一个例子 ： [1,2,3] [1,3,2] [2,3,1] [2,1,3] [3,1,2] [3,2,1] 可以看到数组里的每一个数字都有机会做开头数字，我们递归的过程就是不去思考后面怎么排，函数要处理的就是让将[1,2,3]三个数字逐一拉到开头，再递归下去做全排列（考虑后面的数字）

    //arr：待排列的数组。参数p：数组中要实现全排列的下标开头。 q：要实现全排列的结尾下标
    static void perm(int []arr,int p,int q) { 
        
        if(p==q) { 
        
            for(int i:arr) System.out.println(i);//打印排列好的数组。
            return ;
        }
        for(int i=p;i< q;i++){ 
        
            swap(arr,p,i); //交换函数：第i个数和第p个数交换
            perm(arr,p+1,q) ;
            swap(arr,p,i); // 换回来。 
        }
    }

回到题目：全排列做好了，只需要检查一下结果是否符合题意。

class Main { 
        
    static int ans=0 ;
    public static void main(String[] args) throws IOException { 
        
         int [] arr=new int[]{ 
        1,2,3,4,5,6,7,8,9} ;
         perm(arr,0,arr.length) ;
        System.out.println(ans / 6);
    }
    static void check3(int []arr){ 
        
    //计算三角形的三条边。 
        int r1= arr[0]+arr[1]+arr[3]+arr[5] ;
        int r2= arr[0]+arr[2]+arr[4]+arr[8] ;
        int r3= arr[5]+arr[6]+arr[7]+arr[8] ;
        if(r1==r2&&r2==r3) { 
        //是否为正三角形。
            ans++;
        }
    }
    //arr：待排列的数组。参数p：数组中要实现全排列的下标开头。 
    //q：要实现全排列的结尾下标
    static void perm(int []arr,int p,int q) { 
        
    //递归终止条件：p==q说明要排序的只有一个数，就是它自己。
        if(p==q) { 
        
            check3(arr) ;
            return ;
        }
        for(int i=p;i< q;i++){ 
        
            swap(arr,p,i);
            perm(arr,p+1,q) ;
            swap(arr,p,i);
        }
    }
}

注意：题目中说了旋转，镜像后相同的序列也相同，需要去重，所以答案要/6 旋转有3种，三角形的顶点可以是三个角 /3 镜像两种： 对称轴 /2

答案： 144

结语： 相似题目还有蛮多的，可以找来做做： 2014 JavaA组 ： 6角填数

题目：

小蓝要用七段码数码管来表示一种特殊的文字。

上图给出了七段码数码管的一个图示，数码管中一共有 7 段可以发光的二 极管，分别标记为 a, b, c, d, e, f, g。

小蓝要选择一部分二极管（至少要有一个）发光来表达字符。在设计字符 的表达时，要求所有发光的二极管是连成一片的。

例如：b 发光，其他二极管不发光可以用来表达一种字符。 例如：c 发光，其他二极管不发光可以用来表达一种字符。 这种方案与上一行的方案可以用来表示不同的字符，尽管看上去比较相似。

例如：a, b, c, d, e 发光，f, g 不发光可以用来表达一种字符。 例如：b, f 发光，其他二极管不发光则不能用来表达一种字符，因为发光 的二极管没有连成一片。

请问，小蓝可以用七段码数码管表达多少种不同的字符？

解题思路

dfs搜索，每一段二极管选择点亮或者不点亮，到最后检查一下符不符合条件：