#|蓝桥杯31天冲刺打卡题解（Day1）蓝桥杯|java|算法|贪心算法|bf

Day1 第一题第十二届2021年国赛
C++B组第2题
填空题
【#|蓝桥杯31天冲刺打卡题解（Day1）】纯质数
只有每一位是由2，3，5，7凑成的质数才是纯质数。

public class Main { public static void main(String[] args) { int cnt = 0; for(int i = 2; i <= 20210605; i++){ if(check(i) && isPrime(i)) cnt++; } System.out.println(cnt); }// 求质数 O(sqrt(n))会快很多 private static boolean isPrime(int n){ for(int i = 2; i <= Math.sqrt(n); i++){ if(n % i == 0) return false; } return true; }// 将不满足纯质数的条件筛出去 private static boolean check(int n){ while(n != 0){ // 枚举每一位判断 int temp = n % 10; if(temp == 0 || temp == 1 || temp == 4 || temp == 6 || temp == 8 || temp == 9) return false; n /= 10; } return true; } }

第二题第十二届2021年省赛
JavaB组第7题
找规律/贪心思想
最少砝码
天平是两边都可以放砝码的，我们表示重量不仅仅是放在一边相加重量，我们可以用一边减去另一边的重量来表示，选择更少的砝码来贪心的表示更大的范围。
n是需要称出1 ~ n的重量。
当n == 1时，只用1个重量为1的砝码即可。
当n == 2时，我们可以用2个重量为1的砝码，但我们可以基于贪心的思想，第1个用重量为1的砝码，第2个用重量为3的砝码，，3 - 1 = 2，此时也可以表示3 + 1 = 4，所以可以表示(1, 2, 3, 4)这四个重量，最大可以表示的重量是4。
当n == 5时，就需要用3个砝码了，同样基于贪心，9 - 3 - 1 = 5，此时第3个砝码重量我们选择9，9 + 3 + 1 = 13，最大可以表示的重量是13。
当n == 14时，用4个砝码，27 - 13 = 14，此时第4个砝码选择27。
此时我们已经找到砝码选择的规律，就是 ( 3 0 , 3 1 , 3 2 . . . 3 k ) (3^{0},3^{1},3^{2}... 3^{k}) (30,31,32...3k)
公式：下一个砝码重量 - 当前所有砝码能表示的最大重量 = 当前砝码表示不出来的最小数量

import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int cnt = 1, weight = 1, sum = 1; // 砝码个数选择的砝码重量砝码最大能表示的重量 while (true) { if (sum >= n) break; weight *= 3; // 1 3 9 27 sum += weight; // 1 4 13 27 cnt++; } System.out.print(cnt); } }

第三题 2021年模拟赛
灌溉
bfs模板。

import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; public class Main {static final int N = 110; static int[][] a = new int[N][N]; static int n, m, T; static Queue q = new LinkedList<>(); // 灌溉队列public static void main(String[] args) { Scanner sc = new Scanner(System.in); n = sc.nextInt(); m = sc.nextInt(); T = sc.nextInt(); while (T-- > 0) { int x = sc.nextInt(), y = sc.nextInt(); int k = sc.nextInt() - 1; while (k-- > 0) { bfs(x, y); } }int cnt = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (a[i][j] == 1) cnt++; } }System.out.print(cnt); }private static void bfs(int sx, int sy) {int[] dx = new int[]{-1, 0, 1, 0}, dy = new int[]{0, 1, 0, -1}; while (T-- > 0) { a[sx][sy] = 1; // 水管处已经灌溉好 q.offer(new PII(sx, sy)); while (!q.isEmpty()) { PII t = q.poll(); for (int i = 0; i < 4; i++) { int x = t.x + dx[i], y = t.y + dy[i]; if (x < 0 || x >= n || y < 0 || y >= n) continue; // 出界 if (a[x][y] == 1) continue; // 已被灌溉 a[x][y] = 1; q.offer(new PII(x, y)); } } } }static class PII { int x; int y; public PII(int x, int y) { this.x = x; this.y = y; } } }