罗文彬

large picture of the cover

蓝桥杯第12次带练

题目

魔法科考试

题目链接

解题思路

题目要求：从 ​ n 个上半部分口诀 ​ a_i 和 ​ m 个下半部分口诀 ​ b_j 中，任选一个组合成完整口诀 ​ S = a_i + b_j 。​当满足以下两个条件时，魔法有效：

  1. ​ S \leq n + m
  2. ​ S 是质数

问：能组合出多少种不同的有效魔法？

注意：不同组合可能得到相同的 ​ S ，所以要统计的是 不同的 ​ S 的个数。

步骤一：预处理质数

由于 ​ S = a_i + b_j ，最大值不超过 ​ \max(a_i) + \max(b_j) ，而 ​ a_i, b_j \leq 50000 ，但 ​ S \leq n + m \leq 10^5 （因为 ​ n, m \leq 50000 ），所以只需预处理 ​ [2, 100000] 内的质数。

使用埃拉托斯特尼筛法（Sieve of Eratosthenes）生成 isPrime 数组。

✅ 注意：n + m 最大为 100000，所以只需筛到 100000。

步骤二：枚举所有组合

对每个 ​ a_i 和 ​ b_j ，计算 ​ s = a_i + b_j ：

  • 若 ​ s > n + m ，跳过；
  • 否则，若 ​ s 是质数，则加入集合；

用 HashSet<Long> 去重，最后返回集合大小。

参考代码

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
      
        int[] a = new int[n];
        int[] b = new int[m];
      
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }
        for (int i = 0; i < m; i++) {
            b[i] = sc.nextInt();
        }
      
        // 预处理质数，范围 [2, n+m]
        boolean[] isPrime = sieve(n + m);
      
        Set<Long> validSums = new HashSet<>();
      
        // 枚举所有 a[i] + b[j]
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                long sum = (long) a[i] + b[j];
                if (sum <= n + m && isPrime[(int) sum]) {
                    validSums.add(sum);
                }
            }
        }
      
        System.out.println(validSums.size());
    }

    private static boolean[] sieve(int limit) {
        boolean[] isPrime = new boolean[limit + 1];
        Arrays.fill(isPrime, true);
        isPrime[0] = isPrime[1] = false;
      
        List<Integer> primes = new ArrayList<>();
        for (int i = 2; i <= limit; i++) {
            if (isPrime[i]) {
                primes.add(i);
            }
            for (int p : primes) {
                if (i * p > limit) break;
                isPrime[i * p] = false;
            }
        }
        return isPrime;
    }
}

X质数

题目链接

解题思路

一个正整数 ​ N 是 X质数，当且仅当：
我们可以从中删除若干个数字（至少删一个），使得剩下的数字按原顺序组成的数是质数。

例如：

  • 7869 → 删除 7 和 6 → 得到 89，是质数 → 所以 7869 是 X质数；
  • 77 → 删除一个 7 → 得到 7，是质数 → 所以 77 是 X质数。

我们需要统计从 1 到 1000000 中有多少个这样的 X质数。

核心思想

对每个数 ​ N ，我们枚举其所有非空子序列（即保留任意多个数字，保持顺序），判断是否有任何一个子序列构成的数是质数。

由于最多 6 位数，子序列总数为 ​ 2^6 - 1 = 63 ，可以暴力枚举。

✅ 注意：子序列必须是非空的，且不能全删光（即至少保留一个）。

步骤一：预处理质数

使用欧拉筛法预处理出 ​ [2, 1000000] 范围内的所有质数，存入布尔数组 isPrime。

步骤二：判断是否为 X质数

对每个数 ​ i \in [1, 1000000] ：

  1. 将其转为字符串，得到每一位数字；
  2. 枚举所有非空子序列（用位掩码表示）；
  3. 对每个子序列，拼接成一个整数；
  4. 若该整数在范围内且是质数，则 ​ i 是 X质数，计数加一。

参考代码（Java）

import java.util.*;

public class Main {
    public static void main(String[] args) {
        // 预处理质数，范围 [2, 1000000]
        boolean[] isPrime = sieve(1000000);

        long count = 0;
        // 遍历 1 到 1000000
        for (int i = 1; i <= 1000000; i++) {
            if (hasPrimeSubsequence(i, isPrime)) {
                count++;
            }
        }

        System.out.println(count);
    }

    /**
     * 使用欧拉筛法生成质数表
     * @param limit 上限
     * @return isPrime[i] 表示 i 是否为质数
     */
    private static boolean[] sieve(int limit) {
        boolean[] isPrime = new boolean[limit + 1];
        Arrays.fill(isPrime, true);
        isPrime[0] = isPrime[1] = false;

        List<Integer> primes = new ArrayList<>();
        for (int i = 2; i <= limit; i++) {
            if (isPrime[i]) {
                primes.add(i);
            }
            for (int p : primes) {
                if (i * p > limit) break;
                isPrime[i * p] = false;
                if (i % p == 0) break; // 优化：避免重复标记
            }
        }
        return isPrime;
    }

    /**
     * 判断数字 n 是否包含一个质数子序列
     * 即：能否通过删除某些位，得到一个质数
     * @param n 待判断的数字
     * @param isPrime 质数表
     * @return 是否存在质数子序列
     */
    private static boolean hasPrimeSubsequence(int n, boolean[] isPrime) {
        String s = String.valueOf(n);
        int len = s.length();

        // 枚举所有非空子序列（位掩码从 1 到 2^len - 1）
        for (int mask = 1; mask < (1 << len); mask++) {
            long num = 0;
            for (int i = 0; i < len; i++) {
                if ((mask & (1 << i)) != 0) {
                    num = num * 10 + (s.charAt(i) - '0');
                }
            }

            // 如果这个数在范围内且是质数，则返回 true
            if (num <= 1000000 && isPrime[(int) num]) {
                return true;
            }
        }

        return false;
    }
}

关键说明

  • 位掩码枚举：mask 从 1 到 ​ 2^{\text{len}} - 1 ，表示选择哪些位；
  • 子序列拼接：按原顺序拼接选中的数字，形成新数；
  • 剪枝：若拼出的数大于 1000000，直接跳过（因为质数表只到 1000000）；
  • 效率：总枚举次数约为 ​ 10^6 \times 2^6 = 64 \times 10^6 ，在 Java 中可接受。

旅行I

题目链接

解题思路

小蓝初始位于坐标 ​ x ，要访问数轴上的 ​ n 个国家（坐标为 ​ a[i] ）。他可以选择一个固定的移动距离 ​ D ，一旦选定就不能更改。每次移动可以向左或向右走 ​ D 的整数倍。

目标：最小化移动次数，使得能到达所有国家。

关键观察

  1. 最优的 ​ D 是所有相邻国家间距的最大公约数​设国家坐标排序后为 ​ p_0 < p_1 < \cdots < p_{n-1} ，则：

    • 所有国家之间的差值都是 ​ D 的倍数；
    • 因此 ​ D 必须是所有相邻差值的公约数；
    • 最优策略是取最大公约数 ​ D = \gcd(p_1 - p_0, p_2 - p_1, \ldots)

  2. 插入初始位置 ​ x 后再求 GCD​小蓝从 ​ x 出发，所以必须考虑 ​ x 到最近国家的距离是否也能被 ​ D 整除。

    ✅ 正确做法：将 ​ x 插入排序后的数组中，再对所有相邻差值求 GCD。

  3. 最小移动次数计算​设最终确定的 ​ D ，那么：

    • 左边最远国家距离为 ​ l = x - \min(\text{国家})
    • 右边最远国家距离为 ​ r = \max(\text{国家}) - x
    • 总共需要覆盖的范围是 ​ l + r
    • 但我们可以先向一边走完，再返回另一边

    两种策略：

    • 先左后右：走 ​ \lceil l / D \rceil 次到左边，再走 ​ \lceil (l + r) / D \rceil 次到右边
    • 先右后左：走 ​ \lceil r / D \rceil 次到右边，再走 ​ \lceil (l + r) / D \rceil 次到左边

    答案是两者中的较小值。

参考代码（Java）

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long x = sc.nextLong();
      
        long[] nums = new long[n];
        for (int i = 0; i < n; i++) {
            nums[i] = sc.nextLong();
        }
      
        // 插入初始位置并排序
        long[] all = new long[n + 1];
        System.arraycopy(nums, 0, all, 0, n);
        all[n] = x;
        Arrays.sort(all);
      
        // 求所有相邻差值的最大公约数
        long D = all[1] - all[0];
        for (int i = 2; i <= n; i++) {
            D = gcd(D, all[i] - all[i - 1]);
        }
      
        // 计算左右边界距离
        long l = x - all[0];      // 到最左国家的距离
        long r = all[n] - x;      // 到最右国家的距离
      
        // 两种策略：先左后右 或 先右后左
        long leftFirst = (l + r) / D + l / D;
        if ((l + r) % D != 0) leftFirst++;
        if (l % D != 0) leftFirst++;

        long rightFirst = (l + r) / D + r / D;
        if ((l + r) % D != 0) rightFirst++;
        if (r % D != 0) rightFirst++;

        System.out.println(Math.min(leftFirst, rightFirst));
    }

    private static long gcd(long a, long b) {
        while (b != 0) {
            long temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }
}

关键说明

  • GCD 的作用：确保所有国家都能通过步长 ​ D 到达；
  • 插入 ​ x ：因为起点不是国家，必须考虑它与国家的相对位置；
  • 移动次数：由于不能中途改变 ​ D ，只能通过往返策略覆盖左右区域；
  • 向上取整：使用 (a + D - 1) / D 更简洁，但这里手动处理更清晰。

切割

题目链接

解题思路

给定一个 ​ W \times H 的长方形，要求将其无损耗地切割成若干个大小相等、边长为整数且至少为 2 的小正方形。

目标是：最大化正方形的数量。

关键观察

  1. 每个正方形边长为 ​ s ，则必须满足：

    • ​ s \geq 2
    • ​ s \mid W 且 ​ s \mid H （即 ​ s 是 ​ W 和 ​ H 的公约数）

  2. 总数量为：

    \frac{W}{s} \times \frac{H}{s} = \frac{W \cdot H}{s^2}

  3. 要使数量最大，需让 ​ s 尽可能小，但不能小于 2。

  4. 因此，我们应找：

    • ​ \gcd(W, H) 的所有约数；
    • 其中大于等于 2 的最小值 ​ s_{\min} ；
    • 若不存在这样的 ​ s ，返回 0。

  5. 最大数量为：​ \dfrac{W \cdot H}{s_{\min}^2}

算法步骤

  • 计算 ​ g = \gcd(W, H)
  • 找到 ​ g 的最小质因子（即大于 1 的最小约数）作为候选边长 ​ s
  • 如果没有大于 1 的约数（即 ​ g = 1 ），则无法构造边长 ≥ 2 的正方形 → 返回 0
  • 否则，答案为 ​ \dfrac{W \cdot H}{s^2}

✅ 为什么是最小约数？因为越小的 ​ s 能切出越多块。

参考代码（Java）

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long w = sc.nextLong();
        long h = sc.nextLong();

        // 求最大公约数
        long g = gcd(w, h);

        // 找到 g 的最小质因子（即大于1的最小约数）
        long minGcd = g;
        for (long i = 2; i * i <= g; i++) {
            if (g % i == 0) {
                minGcd = i;
                break;
            }
        }

        // 如果最小约数为 g 本身，说明 g 是质数或 1
        // 若 g == 1，则无边长 >= 2 的正方形可切
        if (minGcd == 1) {
            System.out.println(0);
        } else {
            long count = w * h / minGcd / minGcd;
            System.out.println(count);
        }
    }

    private static long gcd(long a, long b) {
        while (b != 0) {
            long temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }
}

关键说明

  • 最小约数查找：枚举从 2 开始的因数，找到第一个能整除 ​ g 的数；
  • 特殊情况处理：若 ​ \gcd(W,H) = 1 ，则无法切出边长 ≥ 2 的正方形；
  • 结果计算：使用 long 避免整型溢出；
  • 优化：无需枚举所有约数，只需找到最小的那个即可。

一个敲代码的

site logo

罗文彬的个人站

© 2025 罗文彬