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]; } }
以上就是小王同学给大家带来考前常考的一些题型
