蓝桥杯考前复习三

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;} elser = 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);}}}