2024 第十五届蓝桥杯 Java A 组：全题解

分类:热门推荐日期:2024-05-05浏览:1评论:0

目前，C ~ F 题已经在 dotcpp 取得 AC：

A. 拼正方形

题目描述

有 7385137888721 个 2 × 2 2 \times 2 2×2 的方块和 10470245 个 1 × 1 1 \times 1 1×1 的方块，求能拼出的正方形的最大边长。

解题思路

用 1 × 1 1 \times 1 1×1 的方块给已经用 2 × 2 2 \times 2 2×2 的方块拼成的大正方形“镶边”，每次使其边长加 1 1 1。

public class Main { public static void main(String[] args) { final long SQ2 = 7385137888721L;
        final long SQ1 = 10470245L;
        
        // 用 2x2 的方块拼成一个大正方形
        long ans = (long) Math.sqrt(SQ2) * 2;
        
        // 用 1x1 的方块镶边
        long sq1 = SQ1;
        while (true) { if ((sq1 -= ans * 2 + 1) < 0) break;
            ans++;
        }
        
        System.out.println(ans);
    }
}

输出：

5435122
答案

5435122

B. 召唤数学精灵

题目描述

计算 i i i 的数量，满足：

  • 1 ≤ i ≤ \leq i \leq ≤i≤ 2024041331404202
  • A ( i ) − B ( i )   m o d   100 = 0 A(i) - B(i) \space {\rm mod} \space 100 = 0 A(i)−B(i) mod 100=0

    其中， A ( x ) = s u m ( 1 ,   x ) A(x) = {\rm sum}(1,\space x) A(x)=sum(1, x)， B ( x ) = x ! B(x) = x! B(x)=x!。

    解题思路

    观察到 ∀ i ≥ 100 \forall i \geq 100 ∀i≥100， B ( i )   m o d   100 = 0 B(i) \space {\rm mod} \space 100 = 0 B(i) mod 100=0（赛后发现 ∀ i ≥ 10 \forall i \geq 10 ∀i≥10 即可），那么算式 A ( i ) − B ( i )   m o d   100 = 0 A(i) - B(i) \space {\rm mod} \space 100 = 0 A(i)−B(i) mod 100=0 就化简为 A ( i )   m o d   100 = 0 A(i) \space {\rm mod} \space 100 = 0 A(i) mod 100=0。

    考虑 s u m ( 1 ,   200 ) = 20100 {\rm sum}(1,\space 200) = 20100 sum(1, 200)=20100， 20100   m o d   100 = 0 20100 \space {\rm mod} \space 100 = 0 20100 mod 100=0，可以以 200 200 200 为一个周期，计算一个周期内 A ( i )   m o d   100 = 0 A(i) \space {\rm mod} \space 100 = 0 A(i) mod 100=0 的次数，与周期数相乘。

    将 1 ~ 2024041331404202 拆成 1 ~ 200 和 201 ~ 2024041331404202 两部分：

    • 第一部分的特殊之处在于 i = 1 i = 1 i=1 和 i = 3 i = 3 i=3，它们都满足要求，而之后的例如 i = 201 i = 201 i=201 和 i = 203 i = 203 i=203 都不满足要求，因此额外加 2 2 2。
    • 第二部分以每 200 200 200 一个周期，算得周期内有 4 4 4 个 i i i 满足要求（代码略），乘以总周期数。 
      public class Main { public static void main(String[] args) { final long ed = 2024041331404202L;
        
        // 分别计算两部分答案
        long ans1 = 4 + 2;
        long ans2 = (ed - 200) / 200 * 4;
        
        System.out.println(ans1 + ans2);
    }
}

      输出：

      40480826628086
      答案

      40480826628086

      C. 数字诗意

      题目描述

      输入 n 个数字，输出其中无法被表示为连续多个（至少 2 个）正整数之和的数字个数。

      输入输出示例

      输入共 2 行，第 1 行含一个正整数 n，第 2 行含 n 个正整数 x：

      3
3 6 8

      范围：

      • 1 ≤ 1 \leq 1≤ n ≤ 2 × 1 0 5 \leq 2 \times 10^5 ≤2×105
      • 1 ≤ 1 \leq 1≤ x ≤ 1 × 1 0 16 \leq 1 \times 10^{16} ≤1×1016

        输出一个整数表示答案：

        1

        解释：

        • 3 = 1 + 2
        • 6 = 1 + 2 + 3
        • 8 无法表示为连续多个正整数之和
          解题思路

          手写 / 暴力打一个小表，下划线 _ 表示无法表出的数字：

           _  _  3  _  5
 6  7  _  9 10
11 12 13 14 15
_  17 18 19 20

          找规律，发现只有 2 n 2^n 2n 无法表出。

          记 long 内最大的 2 n 2^n 2n 为 POW，对输入的每个数 x，POW % x == 0 时答案加 1。

          答案
          import java.util.*;
import java.io.*;
public class Main { public static void main(String[] args) throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(System.out);
        
        final long POW = 1L << 62;
        int n = Integer.parseInt(in.readLine());
        
        StringTokenizer st = new StringTokenizer(in.readLine());
        int ans = 0;
        while (n-- > 0) { if (POW % Long.parseLong(st.nextToken()) == 0) ans++;
        }
        out.println(ans);
        
        out.flush();
        out.close();
    }
}

          D. 回文数组

          题目描述

          输入一个长为 n 的数组，输出使其变得回文的最少操作次数。

          在 1 次操作中，可以二选一：

          • 选择一个元素，对其增减 1 1 1
          • 选择相邻的两个元素，对其增减 1 1 1
            输入输出示例

            输入共 2 行，第 1 行含一个正整数 n，第 2 行含 n 个正整数 x：

            4
1 2 3 4

            范围：

            • 1 ⩽ 1 \leqslant 1⩽ n ⩽ 1 × 1 0 5 \leqslant 1 \times 10^5 ⩽1×105
            • − 1 × 1 0 6 ⩽ -1 \times 10^6 \leqslant −1×106⩽ x ⩽ 1 × 1 0 6 \leqslant 1 \times 10^6 ⩽1×106

              输出一个整数表示答案：

              3

              解释：

              • 第 1 次操作后：[2, 3, 3, 4]
              • 第 2 次操作后：[3, 3, 3, 4]
              • 第 3 次操作后：[4, 3, 3, 4]，已经是回文
                解题思路

                双指针 i、j 从两端向中间看，每次先用“操作 1”使 arr[i] == arr[j]，然后看 arr[i+1] 和 arr[j-1] 是否与它们同号，如果同号，可以将一部分操作改为“操作 2”，从而节约操作次数。

                实现时，可以先一次遍历，更新 arr[i] -= arr[j]，再次遍历时仅比较 arr[i] 和 arr[i+1] 是否同号即可。

                答案
                import java.util.*;
import java.io.*;
public class Main { public static void main(String[] args) throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(System.out);
        
        int n = Integer.parseInt(in.readLine());
        int[] arr = new int[n];
        StringTokenizer st = new StringTokenizer(in.readLine());
        for (int i = 0; i < n; i++) { arr[i] = Integer.parseInt(st.nextToken());
        }
        
        // 预处理
        for (int i = 0, j = n - 1; i < j; i++, j--) { arr[i] -= arr[j];
        }
        
        // 遍历前一半
        long ans = 0;
        for (int i = 0; i < n / 2; i++) { if (arr[i] == 0) continue;
            // 先用 "操作 1" 变 arr[i]
            ans += Math.abs(arr[i]);
            // 再看能否顺便变一下 arr[i+1]
            if (i + 1 < n / 2 && arr[i] > 0 == arr[i + 1] > 0) { arr[i + 1] = Math.abs(arr[i]) > Math.abs(arr[i + 1]) ? 0 : arr[i + 1] - arr[i];
            }
        }
        out.println(ans);
        
        out.flush();
        out.close();
    }
}

                E. 吊坠

                题目描述

                输入 n 个长为 m 的字符串，作为图的结点，每两个结点间都有一条带权边，权值为两字符串的最长公共 子串 的长度。

                注意，本题中的字符串都可以旋转，如 "abba" 可以旋转变换为 "aabb"，从而 "abba" 和 "acca" 之间的边权值为 2。

                选出 最少 的边让所有结点连通，且成本 最大，输出这个成本。

                输入输出示例

                输入共 n + 1 行，第 1 行含两个正整数 n、m，随后 n 行各含一个长为 m 的字符串：

                4 4
aabb
abba
acca
abcd

                范围：

                • 1 ⩽ 1 \leqslant 1⩽ n ⩽ 200 \leqslant 200 ⩽200
                • 1 ⩽ 1 \leqslant 1⩽ x ⩽ 50 \leqslant 50 ⩽50

                  输出一个整数表示答案：

                  8

                  解释：连接 <1, 2>，<2, 3>，<2, 4>，边权和为 4 + 2 + 2 = 8 4 + 2 + 2 = 8 4+2+2=8。

                  解题思路

                  分 2 大步：

                  1. 求出所有边的边权，如：
                  [0, 4, 2, 2]
[0, 0, 2, 2]
[0, 0, 0, 1]
[0, 0, 0, 0]

                  本题中的字符串可旋转，考虑在每个字符串后重复一次自身，如 "abcd" 变为 "abcdabcd"，这样遍历每个长为 m 的窗口就得到了自身的全部旋转结果。

                  用动态规划，对两个字符串滑一次，求得它们的最长公共子串长度，即边权。

                  1. 用 kruskal 算法——原本求最小生成树的算法——求 最大生成树。

                  所有边入堆，并查集判环，无环时加入边并 union()。

                  答案
                  import java.util.*;
import java.io.*;
public class Main { private static char[][] arr;
    
    public static void main(String[] args) throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(System.out);
        
        StringTokenizer st = new StringTokenizer(in.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        
        // 每个字符串重复自己
        arr = new char[n][m * 2];
        for (int i = 0; i < n; i++) { char[] s = in.readLine().toCharArray();
            for (int j = 0; j < m; j++) { arr[i][j] = arr[i][j + m] = s[j];
            }
        }
        
        // 求所有边权
        int[][] dist = new int[n][n];
        for (int i = 0; i < n - 1; i++) { for (int j = i + 1; j < n; j++) { dist[i][j] = lcs(i, j);
            }
        }
        
        // 所有边入堆
        Queue pq = new PriorityQueue<>(Comparator.comparingInt((int[] a) -> -a[2]));
        for (int i = 0; i < n - 1; i++) { for (int j = i + 1; j < n; j++) { pq.offer(new int[]{i, j, dist[i][j]});
            }
        }
        
        // Kruskal 算法
        int[] root = new int[n];
        Arrays.setAll(root, a -> a);
        int take = 0;
        int ans = 0;
        while (take < n - 1) { int[] p = pq.poll();
            if (find(root, p[0]) != find(root, p[1])) { union(root, p[0], p[1]);
                take++;
                ans += p[2];
            }
        }
        out.println(ans);
        
        out.flush();
        out.close();
    }
    
    // 求两旋转字符串的最长公共子串长度
    private static int lcs(int x, int y) { int m = arr[0].length;
        int max = 0;
        int[][] dp = new int[m + 1][m + 1];
        for (int i = 1; i <= m; i++) { for (int j = 1; j <= m; j++) { if (arr[x][i - 1] == arr[y][j - 1]) { dp[i][j] = Math.max(dp[i - 1][j - 1] + 1, dp[i][j]);
                    max = Math.max(dp[i][j], max);
                }
            }
        }
        return Math.min(max, m / 2);
    }
    
    // 并查集
    private static int find(int[] root, int i) { return root[i] == i ? i : (root[i] = find(root, root[i]));
    }
    
    // 并查集
    private static void union(int[] root, int x, int y) { root[find(root, x)] = find(root, y);
    }
}

                  F. 砍柴

                  题目描述

                  A、B 两人轮流砍柴，轮到某一方砍柴时，设原木剩余长度为 x：

                  • 如果 x 为 0 0 0 或 1 1 1，本方无法继续砍柴，从而输掉比赛。
                  • 如果 x ⩾ 2 \geqslant 2 ⩾2，本方可选择一个长度 2 ⩽ 2 \leqslant 2⩽ p ⩽ \leqslant ⩽ x，砍掉长为 p 的一段。

                    共 n 段原木（n 局游戏），每局 A 先手，双方都采用最佳策略。

                    对每局游戏，如果 A 能够取胜，输出 1，否则输出 0。

                    输入输出示例

                    输入共 n + 1 行，第 1 行含一个正整数 n，随后 n 行各含一个正整数 x：

                    3
1
2
6

                    范围：

                    • 1 ⩽ 1 \leqslant 1⩽ n ⩽ 1 0 4 \leqslant 10^4 ⩽104
                    • 1 ⩽ 1 \leqslant 1⩽ x ⩽ 1 0 5 \leqslant 10^5 ⩽105

                      输出 n 行，每行含一个整数 0 或 1：

                      0
1
1

                      解释：

                      • 对 x = 1 = 1 =1，A 已无法砍柴，A 失败。
                      • 对 x = 2 = 2 =2，A 砍掉 p = 2 = 2 =2，轮到 B 时 x = 0 = 0 =0，已无法砍柴，A 获胜。
                      • 对 x = 6 = 6 =6，A 砍掉 p = 5 = 5 =5，轮到 B 时 x = 1 = 1 =1，已无法砍柴，A 获胜。
                        解题思路

                        典型的博弈问题，预处理范围内的质数集，boolean win(int x) 用 DFS 判断当前剩余长度能否获胜，递归交换对手。

                        剪枝：对 win(x)，二分质数集查询 ⩽ \leqslant ⩽ x 的最大位置，倒序遍历，更快接近 DFS 基态，否则 1 0 5 10^5 105 容易栈溢出。

                        答案
                        import java.util.*;
import java.io.*;
public class Main { private static int[] primes;
    private static int[] memo;
    
    public static void main(String[] args) throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(System.out);
        
        int n = Integer.parseInt(in.readLine());
        int[] arr = new int[n];
        
        // 取输入的最大值
        int max = 0;
        for (int i = 0; i < n; i++) { arr[i] = Integer.parseInt(in.readLine());
            max = Math.max(arr[i], max);
        }
        
        // 预处理质数
        getPrimes(max);
        memo = new int[max + 1];
        for (int x : arr) { out.println(win(x) ? 1 : 0);
        }
        
        out.flush();
        out.close();
    }
    
    // 筛法预处理得到范围内所有质数
    private static void getPrimes(int max) { boolean[] v = new boolean[max + 1];
        Arrays.fill(v, true);
        for (int x = 2; x <= max; x++) { if (!v[x]) continue;
            for (int y = x * 2; y <= max; y += x) { v[y] = false;
            }
        }
        int n = 0;
        for (int x = 2; x <= max; x++) { if (v[x]) n++;
        }
        primes = new int[n];
        int i = 0;
        for (int x = 2; x <= max; x++) { if (v[x]) primes[i++] = x;
        }
    }
    
    // DFS 博弈
    private static boolean win(int x) { if (memo[x] != 0) return memo[x] == 1;
        if (x <= 1) return false;
        // 剪枝: 倒序遍历质数集, 更快接近 DFS 基态
        for (int i = bis(x); i >= 0; i--) { if (!win(x - primes[i])) { memo[x] = 1;
                return true;
            }
        }
        memo[x] = -1;
        return false;
    }
    
    // 二分, 从质数集中查找 <= x 的最大位置
    private static int bis(int x) { int l = 0;
        int r = primes.length - 1;
        while (l <= r) { int m = l + r >> 1;
            if (primes[m] <= x) l++;
            else r--;
        }
        return r;
    }
}

相关推荐

关于我们常见问题广告服务免责声明联系我们
Powered By Z-BlogPHP 1.7.3 Theme By 优美主题
Copyright Your WebSite.Some Rights Reserved. 浙ICP备2023018783号