蓝桥杯考前复习三

1.约数个数

 由乘法原理可以得出：

import java.util.*;
public class Main{
    static int mod = (int)1e9 + 7;
    public static void main(String[] args){
        Map<Integer,Integer> map = new HashMap<>(); //创建一个哈希表
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        while(n -- > 0){
            int x = scan.nextInt();
            //下面这里是运用了分解质因数的模板，
            for(int i = 2 ; i <= x / i ; i ++ ){
                while(x % i == 0){
                    x /= i;
                    // map.getOrDefault(i,0) 这个是获取对应i位置的values值
                    map.put(i,map.getOrDefault(i,0) + 1); 
                }
            }
            if(x > 1) map.put(x,map.getOrDefault(x,0)  + 1 );
        }
 
        long res = 1;
        //map.keySet()获取所有的key值,map.values()获取所有的values值，两种方法都可以
        for(int key : map.values()){
            res = res * (key + 1) % mod;
        }
        System.out.println(res);
    }
}
 

2.堆优化版的Dijkstra

正好复习一下优先队列和存图方式;

3.贡献法求因数个数和；

题目来源于华北水利水电大学校赛：

7-10 兔丁兴旺的兔子家族 - 2024年第六届华北水利水电大学校赛-正式赛-复盘 (pintia.cn)

import java.util.Scanner;
 
public class Main {
 
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		int n=sc.nextInt();
		long sum=0;
		
		
		for(int i=1;i<=n;i++) {
			sum+=n/i;
		}
        System.out.println(sum);
 
    }
}

4.BFS--青蛙跳杯子

开心开心，一次就ac了，嘿嘿；

11.青蛙跳杯子 - 蓝桥云课 (lanqiao.cn)

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
 
public class Main {
	static String start, end;
	static int[] dx = {-3,-2,-1,1,2,3 };
	static int n;
 
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		start = sc.next();
		end = sc.next();
		n = start.length();
		bfs();
 
	}
 
	public static void bfs() {
		Queue<String>q=new LinkedList<String>();
		q.offer(start);
		
		HashMap<String, Integer>map=new HashMap<String, Integer>();
	    map.put(start, 0);
	    while(!q.isEmpty()) {
	    	String t=q.poll();
	    	if(t.equals(end)) {
	    	   System.out.println(map.get(t));
	    	}
	    	int index=t.indexOf('*');
		for(int i=0;i<6;i++) {
			int x=index+dx[i];
			
			if(x<0||x>=n)continue;
			
			
			
			char[] T = t.toCharArray();
			char tmp=T[x];
			T[x]=T[index];
			T[index]=tmp;
			
			String str=new String(T);
			if(!map.containsKey(str)) {
				map.put(str, map.get(t)+1);
			}else continue;
			
			q.offer(str);
			
		}
		
 
	    }
		
	}
 
}

5.进制转换

1.Excel地址 - 蓝桥云课 (lanqiao.cn)

2.幸运数字 - 蓝桥云课 (lanqiao.cn)

import java.util.Scanner;
 
public class Excel地址 {
 
	
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		
		int n=sc.nextInt();
		int []a=new int[26];
		int i=0;
		while(n!=0) {
			n--;
			a[i++]=n%26;
			n/=26;
			
		}
		
		
 
		for(int j=i-1;j>=0;j--) {
			System.out.print((char)(a[j]+65));
		}
		
		
		
	}
	
	
	
	
}

6.二分答案---

5562. 最大生产 - AcWing题库

import java.util.ArrayList;
import java.util.Scanner;
 
public class Main {
	static int N = 100010;
	static long[] a = new long[N];
	static long[] b = new long[N];
	static int n;
	static int k;
	static int INF = Integer.MAX_VALUE;
 
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
 
		n = sc.nextInt();
		k = sc.nextInt();
		for (int i = 1; i <= n; i++) {
			a[i] = sc.nextLong();
		}
		for (int i = 1; i <= n; i++) {
			b[i] = sc.nextLong();
		}
 
		long l = 0, r =(int)2e9;
		while (l < r) {
			long mid = (l + r + 1) / 2;
			if (check(mid)) {
				l = mid;
			} else
				r = mid - 1;
		}
		System.out.println(l); // 二分逻辑
 
	}
 
	public static boolean check(long x) {
		long m=k;
		for (int i = 1; i <= n; i++) {
			if (b[i] - x * a[i] < 0) {
				m-=(a[i]*x-b[i]);
				if(m<0)return false;
			}
				
		
		}
 
		return true;
 
	}
 
}

7.FloodFill

5565. 残垣断壁 - AcWing题库

 
import java.util.Scanner;
 
public class Main {
	static int n,m;
	static int N=110;
	
	static int[][]g=new int[N][N];
	static boolean[][]st=new boolean[N][N];
	static int res=0;
	static int[] dx = { -1, 0, 1, 0 };
	static int[] dy = { 0, 1, 0, -1 };
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		n=sc.nextInt();
		m=sc.nextInt();
		for(int i=0;i<n;i++) {
			String str = sc.next();
			for(int j=0;j<m;j++) {
				g[i][j]=str.charAt(j);
			}
		}
		for(int i=0;i<n;i++) {
			for(int j=0;j<m;j++) {
				if(g[i][j]=='B'&&!st[i][j]) {
					res++;
					dfs(i,j);
				}
			}
		}
		System.out.println(res);
		
		
		
	}
	
	
	
	
	
	
	
	public static void dfs(int a,int b) {
		st[a][b]=true;
		
		for(int i=0;i<4;i++) {
			int x=a+dx[i];
			int y=b+dy[i];
			
			if(x<0||x>=n||y<0||y>=m||st[x][y]||g[x][y]=='.')
				continue;
			
			dfs(x,y);
			
		}
		
	}
 
}