devbox
知新_RL
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

蓝桥杯考前复习一

作者：知新_RL | 2024-04-09 06:35:26

赞

踩

蓝桥杯考前复习一

目录

被蓝桥杯整的焦虑死了，我要复习复习！！！

1.二维前缀和

2.BigIntenger常用方法

3.差分

4.DFS

5.01背包

6.并查集

7.BFS

 8.最短路模板

9.分解质因数

10.两个小结论：

1.二维前缀和

1.统计子矩阵 - 蓝桥云课 (lanqiao.cn)

  1. import java.util.Scanner;
  2.  
  3. public class 统计子矩阵 {
  4.     static int N=510;
  5.     static int[][]g=new int[N][N];
  6.     static int[][]s=new int[N][N];
  7.     static int res=0;
  8.     public static void main(String[] args) {
  9.         Scanner sc = new Scanner(System.in);
  10.         int n = sc.nextInt();
  11.         int m = sc.nextInt();
  12.         int K = sc.nextInt();
  13.         for(int i=1;i<=n;i++){
  14.             for(int j=1;j<=m;j++){
  15.                 g[i][j] = sc.nextInt();
  16.                 s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+g[i][j];
  17.             }
  18.         }
  19.  
  20.         //枚举子矩阵
  21.         //矩阵左上角
  22.         for(int i=1;i<=n;i++){
  23.             for(int j=1;j<=m;j++){
  24.                 for(int k=i;k<=n;k++){
  25.                     for(int l=j;l<=m;l++){
  26.                         int sum=s[k][l]-s[k][j-1]-s[i-1][l]+s[i-1][j-1];
  27.                         if(sum<=K){
  28.                             res++;
  29.                         }
  30.                     }
  31.                 }
  32.             }
  33.         }
  34.         System.out.println(res);
  35.  
  36.  
  37.  
  38.     }
  39.  
  40. }

2.BigIntenger常用方法

快速幂取模：  

  1.         BigInteger a=new BigInteger("2");
  2.         BigInteger b=new BigInteger("6");
  3.         BigInteger p=new BigInteger("10");
  4.  
  5.         BigInteger bigInteger = a.modPow( b,p);
  6.         System.out.println(bigInteger);

最大公约数，最小公倍数数据较大的时候（高精度）

0最小公倍数 - 蓝桥云课 (lanqiao.cn)

  1. import java.math.BigInteger;
  2. import java.util.Scanner;
  3.  
  4. public class Main {
  5.  
  6.     public static void main(String[] args) {
  7.         Scanner sc = new Scanner(System.in);
  8.         int n = sc.nextInt();
  9.         BigInteger a=new BigInteger("1");
  10.         BigInteger b=new BigInteger("2");
  11.         BigInteger c=new BigInteger("1");
  12.         for(int i=2;i<=n;i++) {
  13.             a=lcm(a,b);
  14.             
  15.             b=b.add(c);
  16.             
  17.         }
  18.         
  19.         System.out.println(a);
  20.         
  21.         
  22.         
  23.         
  24.         
  25.         
  26.         
  27.  
  28.     }
  29.     
  30.     
  31.     public static BigInteger lcm(BigInteger a,BigInteger b) {
  32.         return a.multiply(b).divide(a.gcd(b));
  33.     }
  34.  
  35.  
  36. }

3.差分

4.DFS

4498. 指针 - AcWing题库

  1. import java.util.Scanner;
  2.  
  3. public class Main {
  4. 	static int N=20;
  5. 	static int[]a=new int[N];
  6. 	static int n;
  7.     static boolean flag=false;
  8.  
  9. 	public static void main(String[] args) {
  10. 		Scanner sc=new Scanner(System.in);
  11. 		 n=sc.nextInt();
  12. 		for(int i=1;i<=n;i++) {
  13. 			a[i]=sc.nextInt();
  14. 		}
  15. 		
  16. 		dfs(1,0);
  17. 		
  18. 		if(flag) {
  19. 			System.out.println("YES");
  20. 		}else {
  21. 			System.out.println("NO");
  22. 		}
  23. 		
  24. 	}
  25. 	
  26. 	
  27. 	
  28. 	public static void dfs(int u,int res) {
  29. 		if(u>n) {
  30. 			if(res==0||res%360==0) {
  31. 				flag=true;
  32. 			}
  33. 			
  34. 			return ;
  35. 		}
  36. 		
  37. 		dfs(u+1,res+a[u]);
  38. 		
  39. 		dfs(u+1,res-a[u]);
  40. 		
  41. 	
  42. 	}
  43. }

5.01背包

278. 数字组合 - AcWing题库

  1. import java.util.Scanner;
  2.  
  3. public class Main {
  4.     static int N=1000010;
  5.     static int[]p=new int[N];
  6.  
  7.     
  8.     
  9.     public static void main(String[] args) {
  10.         int ans=0;
  11.         Scanner sc=new Scanner(System.in);
  12.         int m=sc.nextInt();
  13.         int n=sc.nextInt();
  14.         
  15.         for(int i=1;i<=m*n;i++) {
  16.             p[i]=i;
  17.         }
  18.         
  19.         int k=sc.nextInt();
  20.         while(k--!=0) {
  21.             
  22.             int a=sc.nextInt();
  23.             int b=sc.nextInt();
  24.             
  25.             p[find(a)]=find(b);    
  26.         }
  27.         
  28.         for(int i=1;i<=m*n;i++) {
  29.             if(p[i]==i) {
  30.                 ans++;
  31.             }
  32.         }
  33.         
  34.         System.out.println(ans);
  35.         
  36.  
  37.     }
  38.     
  39.     
  40.     
  41.     
  42.     public static int find(int x) {
  43.         if(p[x]!=x) p[x]=find(p[x]);
  44.         return p[x];
  45.     }
  46. }

6.并查集

1.合根植物 - 蓝桥云课 (lanqiao.cn)

  1. import java.util.Scanner;
  2.  
  3. public class Main {
  4.     static int N=1000010;
  5.     static int[]p=new int[N];
  6.  
  7.     
  8.     
  9.     public static void main(String[] args) {
  10.         int ans=0;
  11.         Scanner sc=new Scanner(System.in);
  12.         int m=sc.nextInt();
  13.         int n=sc.nextInt();
  14.         
  15.         for(int i=1;i<=m*n;i++) {
  16.             p[i]=i;
  17.         }
  18.         
  19.         int k=sc.nextInt();
  20.         while(k--!=0) {
  21.             
  22.             int a=sc.nextInt();
  23.             int b=sc.nextInt();
  24.             
  25.             p[find(a)]=find(b);    
  26.         }
  27.         
  28.         for(int i=1;i<=m*n;i++) {
  29.             if(p[i]==i) {
  30.                 ans++;
  31.             }
  32.         }
  33.         
  34.         System.out.println(ans);
  35.         
  36.  
  37.     }
  38.     
  39.     
  40.     
  41.     
  42.     public static int find(int x) {
  43.         if(p[x]!=x) p[x]=find(p[x]);
  44.         return p[x];
  45.     }
  46. }

7.BFS

有一个整数 A=2021，每一次，可以将这个数加 1 、减 1 或除以 2，其中除以 2 必须在数是偶数的时候才允许。
例如，2021 经过一次操作可以变成 2020、2022。
再如，2022 经过一次操作可以变成 2021、2023 或 1011。
请问，2021 最少经过多少次操作可以变成 1。

  1. public class Main3 {
  2. 	public static void main(String[] args) {
  3. 		//数组开个10000完全够用了
  4. 		boolean[] visit=new boolean[10000];
  5. 		Queue<Integer> queue=new LinkedList<>();
  6. 		queue.offer(2021);
  7. 		visit[2021]=true;
  8. 		int time=0;
  9. 		while(!queue.isEmpty()) {
  10. 			int size=queue.size();
  11. 			while(size-->0) {
  12. 				int curr=queue.poll();
  13. 				//判断curr如果是1则直接输出time就是我们的答案
  14. 				if(curr==1) {
  15. 					System.out.println(time);//14
  16. 					return;
  17. 				}
  18. 				if(!visit[curr+1]) {
  19. 					visit[curr+1]=true;
  20. 					queue.offer(curr+1);
  21. 				}
  22. 				if(!visit[curr-1]) {
  23. 					visit[curr-1]=true;
  24. 					queue.offer(curr-1);
  25. 				}
  26. 				//一定要记住,只有偶数才可以选择除以2的操作
  27. 				if(curr%2==0&&!visit[curr/2]) {
  28. 					visit[curr/2]=true;
  29. 					queue.offer(curr/2);
  30. 				}
  31. 			}
  32. 			time++;
  33. 		}
  34. 	}
  35. }

 8.最短路模板

  1. import java.util.*;
  2. public class Main{
  3.     static int N = 510,n,m, max = 0x3f3f3f3f;
  4.     static int[][] g = new int[N][N];//存每个点之间的距离
  5.     static int[] dist = new int[N];//存每个点到起点之间的距离
  6.     static boolean[] st = new boolean[N];//存已经确定了最短距离的点
  7.     public static int dijkstra(){
  8.         Arrays.fill(dist,max);//将dist数组一开始赋值成较大的数
  9.         dist[1] = 0; //首先第一个点是零
  10.  
  11.         //从0开始,遍历n次，一次可以确定一个最小值
  12.         for(int i = 0 ; i < n ; i ++ ){ 
  13.             int t = -1; //t这个变量,准备来说就是转折用的
  14.             for(int j = 1 ; j <= n ; j ++ ){
  15.                 /***
  16.                  * 因为数字是大于1的，所以从1开始遍历寻找每个数
  17.                  * 如果s集合中没有这个数
  18.                  * 并且t == -1，表示刚开始 或者 后面的数比我心找的数距离起点的距离短
  19.                  * 然后将j 的值赋值给 t
  20.                  ***/
  21.                 if(!st[j] && (t == -1 || dist[j] < dist[t])){
  22.                     t = j; 
  23.                 }
  24.             }
  25.  
  26.             st[t] = true;//表示这个数是已经找到了确定了最短距离的点
  27.  
  28.             //用已经确认的最短距离的点来更新后面的点
  29.             //就是用1到t的距离加上t到j的距离来更新从1到j的长度
  30.             for(int j = 1 ; j <= n ; j ++ ){
  31.                 //
  32.                 dist[j] = Math.min(dist[j],dist[t] + g[t][j]);
  33.             }
  34.         }
  35.         //如果最后n的长度没有改变，输出-1，没有找到；否则输出最短路n
  36.         if(dist[n] == max) return -1;
  37.         else return dist[n];
  38.  
  39.     }
  40.     public static void main(String[] args){
  41.         Scanner scan = new Scanner(System.in);
  42.         n = scan.nextInt();
  43.         m = scan.nextInt();
  44.         //将他们每个点一开始赋值成一个较大的值
  45.         for(int i = 1 ; i <= n ; i ++ ){
  46.             Arrays.fill(g[i],max);
  47.         }
  48.         while(m -- > 0){
  49.             int a = scan.nextInt();
  50.             int b = scan.nextInt();
  51.             int c = scan.nextInt();
  52.             g[a][b] = Math.min(g[a][b],c);//这个因为可能存在重边，所以泽出最短的
  53.         }
  54.         int res = dijkstra();
  55.         System.out.println(res);
  56.     }
  57. }
  58.

9.分解质因数

1.质因数个数 - 蓝桥云课 (lanqiao.cn)

  1. import java.util.Scanner;
  2.  
  3. public class Main {
  4.     public static void main(String[] args) {
  5.        Scanner sc=new Scanner(System.in);
  6.        long n=sc.nextLong();
  7.        long res=0;
  8.  
  9.        for(long i=2;i<=n/i;i++){
  10.            if(n%i==0){
  11.                while(n%i==0){
  12.                    n/=i;
  13.                }
  14.                 res++;
  15.            }
  16.        }
  17.        //39===3
  18.        if(n>1) res++;
  19.         System.out.println(res);
  20.  
  21.  
  22.     }
  23.  
  24. }

10.两个小结论：

    已知a,b为质数，则不能由a,b凑出来的最大的数是（a-1)(b-1)-1  ;

一段子数组在包含一段连续的自然数时，会有什么性质？设区间[ L , R ][L,R]的值域为[ m i n , m a x ] ，不难发现如果该区间是一段连续自然数时，将会满足:

max−min=j-i;

今天就复习到这里吧，回去吃我的塔斯丁去啦！

声明：本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：【wpsshop博客】
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号