蓝桥杯最后的冲刺篇（JAVA）_蓝桥杯 省赛最后冲刺思路

目录

                1.路径​

         题目要求：

                 解题思路：​

                源码附上：

 

                2.夺宝奇兵​

                 题目要求：

                 解题思路：

                源码附上： 

                3. 七星填数

                题目要求：

                 解题思路：

                 代码附上：

                 4.蓝桥幼儿园​

                题目要求：

                 解题思路：

                源码附上：

---

 

 

友友们  又见面啦 我是你们的小王同学

 

 

 

 

蓝桥杯的正式比赛时间就是明天了，今天小王同学给大家带来几道比较经典的大题 希望能

在最后的阶段  帮助友友们 

如果写的对大家有帮助的话 还可以关注小王的主页：学好c语言的小王同学的博客_CSDN博客-领域博主 

 

你们的三连是我写作最大的动力！！（doge）

小王的gitee： 比特王信哲 (bitewang) - Gitee.com

 

 

1.路径

路径 - 蓝桥云课 (lanqiao.cn)

 题目要求：

 解题思路：

•  先写出求最大公约数的方法  进而推导出求最小公倍数的方法
• 从1到2021，那么我只要走得尽量少，且边尽量短就好。
• 当两个结点差的绝对值小于21的时候 公式为：

  dp[j]=Math.min(dp[j],dp[i]+gb(i,j));

源码附上：

import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改
 
public class 最短路径 {
    public static void main(String[] args) {
        int dp[]=new int[2022];
        dp[1]=0;
        for(int i=2;i<=2021;i++){
            dp[i]=Integer.MAX_VALUE;
         //dp  
        //当前q[j] 表示 从 1~j的最短距离
        //q[j] 可以是 当前 1~j的最短距离 或者 前一状态 到 该点的最短距离
        }
        for(int i=1;i<=2020;i++){
            for(int j=i+1;j<=2021&&j-i<=21;j++){
                dp[j]=Math.min(dp[j],dp[i]+gb(i,j));
 
            }
        }
        System.out.println(dp[2021]);
 
 
    }
    public static int gcd(int a,int b){ //最大公约数
        return b==0?a:gcd(b,a%b);
    }
    public static int gb(int a,int b){ //最小公倍数
        return a*b/gcd(a,b);
    }
}

 

2.夺宝奇兵

蓝桥杯算法提高VIP-夺宝奇兵 - C语言网

 题目要求：

 

 解题思路：

这道题是一道经典的动态规划（dp）的题

找到状态转移方程式是最为关键的 

这道题 小王同学是从最小面走到最上面

源码附上： 

import java.util.Scanner;
 
public class Main {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int A[][]=new int[n][];
        for(int i=0;i<n;i++){
            A[i]=new int[i+1];
            for(int j = 0;j<i+1;j++){
                A[i][j]=sc.nextInt();
            }
        }
        System.out.println(maxt(A,0,0));
    }
    public  static int maxt(int [][]t,int i,int j){
        int rowcount=t.length;//行数
        int colcount=t[rowcount-1].length;//最后一行的列数
        int [][]dp=new int[rowcount][colcount];
        for(int k = 0;k<colcount;k++){
            dp[rowcount-1][k]=t[rowcount-1][k]; //初始化最后一行
 
        }
        for(int k=rowcount-2;k>=0;k--){
            for(int l=0;l<=k;l++){
                dp[k][l]=t[k][l]+Math.max(dp[k+1][l],dp[k+1][l+1]);
            }
        }
        return dp[0][0];  //从下找到最上面一个
    }
}

 

3. 七星填数

七星填数 - 蓝桥云课 (lanqiao.cn)

题目要求：

 解题思路：

在其他没有标注节点的地方标注 不重复的数字

然后回溯排出全部情况 在判断是否满足 每条边上的4个数字之和相等就行

 代码附上：

import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改
 
public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int arr[]={1,2,3,4,5,7,8,9,10,12,13};//将剩余没有标记的节点标记数字
        dfs(arr,0);
    }
    public static void dfs(int []arr,int index){
        if(index==arr.length){
            int sum1=arr[0]+arr[1]+arr[2]+arr[3];
            int sum2=arr[2]+arr[4]+6+11;
            int sum3=arr[3]+arr[4]+arr[5]+arr[6];
            int sum4=6+arr[1]+arr[9]+14;
            int sum5=arr[0]+arr[9]+arr[8]+arr[10];
            int sum6=arr[10]+arr[7]+arr[5]+11;
            int sum7=arr[6]+arr[7]+arr[8]+14;
            if(sum1==sum2&&sum1==sum3&&sum1==sum4&&sum1==sum5&&sum1==sum6&&sum1==sum7){             //判断七条边之和是否相等
                System.out.println(arr[0]+" "+arr[1]+" "+arr[2]+" "+arr[3]);
                return ;
            }
        
        return ;
    }
    for (int i=index;i<arr.length;i++){ //交换元素
        int temp=arr[i];
        arr[i]=arr[index];
        arr[index]=temp;
        dfs(arr,index+1);
        temp=arr[i];
        arr[i]=arr[index];
        arr[index]=temp;
    }
}
}

 

 4.蓝桥幼儿园

 蓝桥幼儿园 - 蓝桥云课 (lanqiao.cn)

题目要求：

 

 解题思路：

这就是一道经典的并查集 的题 模板的话 可以参考这位博主写的：并查集模板_算法小猪的博客-CSDN博客 写的很详细哦！

源码附上：

import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改
 
public class Main {
    static Scanner sc = new Scanner(System.in);
    static int n=sc.nextInt();
    static int m=sc.nextInt();
    static int arr[]=new int[n+1];//记录 学生1~n的编号
    public static void main(String[] args) {
        for(int i=1;i<=n;i++){
            arr[i]=i;
        }
        int t;
        for(int i=0;i<m;i++){
            t=sc.nextInt();
 
            if(t==1){
                lj(sc.nextInt(),sc.nextInt());
            }
            else{
                System.out.println(pd(sc.nextInt())==pd(sc.nextInt())?"YES":"NO");
            }
        }
 
 
    }
  public   static void lj(int a,int b){ //连接关系
        int arr1=pd(a);
        int arr2=pd(b);
        arr[arr1]=arr2;
 
    }
    static int pd(int a){ //判断是否关联
        if(arr[a]==a){
            return a;
        }
        arr[a]=pd(arr[a]);
        return arr[a];
 
    }
}

 

以上就是小王同学给大家带来考前常考的一些题型

祝友友们在明天都可以发挥自己最好的状态 

取得理想的名次！！