本文共 3447 字，大约阅读时间需要 11 分钟。

Day1

第一题 第十二届2021年国赛 C++B组第2题 填空题 只有每一位都由数字2、3、5、7组成的质数才是纯质数。

解题思路

我们需要编写一个程序，统计在2021年1月1日至2021年6月5日之间所有满足纯质数条件的质数的数量。

代码解析

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);
    }
    // 判断是否为质数，时间复杂度为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时，只需1个重量为1的砝码； 当n=2时，使用1和3两个砝码（最大可表示范围扩展至4）； 当n=5时，使用1、3、9三个砝码（最大可表示范围扩展至13）； 当n=14时，使用1、3、9、27四个砝码（最大可表示范围扩展至40）。

砝码选择规律

下一个砝码重量 - 当前所有砝码能表示的最大重量 = 当前砝码表示不出来的最小数量。

代码实现

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;
            sum += weight;
            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();
            int 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 };
        int[] 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];
                    int 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;
        }
    }
}
   

以上代码均为具体实现，涵盖了各题的关键逻辑与实现细节。

转载地址：http://skhfk.baihongyu.com/