蓝桥杯最后的冲刺篇（JAVA）
蓝桥杯最后的冲刺篇（JAVA）
王同学要努力
发布于 2022-12-21 20:20:20
发布于 2022-12-21 20:20:20
目录 1.路径 题目要求： 解题思路： 源码附上： 2.夺宝奇兵 题目要求： 解题思路： 源码附上： 3. 七星填数 题目要求： 解题思路： 代码附上： 4.蓝桥幼儿园 题目要求： 解题思路： 源码附上：
友友们 又见面啦 我是你们的小王同学 你们的三连是我写作最大的动力！！（doge） 小王的gitee： 比特王信哲 (bitewang) - Gitee.com
1.路径
题目要求：
解题思路：
- 先写出求最大公约数的方法 进而推导出求最小公倍数的方法
- 从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.夺宝奇兵
题目要求：
解题思路：
这道题是一道经典的动态规划（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. 七星填数
题目要求：
解题思路：
在其他没有标注节点的地方标注 不重复的数字 然后回溯排出全部情况 在判断是否满足 每条边上的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.蓝桥幼儿园
题目要求：
解题思路：
这就是一道经典的并查集 的题 模板的话 可以参考这位博主写的：并查集模板_算法小猪的博客-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];
}
}以上就是小王同学给大家带来考前常考的一些题型
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2022-04-08，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录