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

第十届2019年蓝桥杯省赛

第一题

题目名称：二分搜索应用于机器人扫格问题

我们需要解决的问题是：给定N个方格和K个机器人，如何让每个机器人扫描的范围最小，同时确保所有方格都被扫到。

方法思路

这道题可以通过二分搜索来解决。我们希望每个机器人扫描的范围最小，因此需要找到一个合适的搜索范围x。我们可以编写一个check(x)函数来判断是否可以用x作为每个机器人扫描的范围。

解决代码

import java.util.Arrays;
import java.util.Scanner;
public class Main {
    static int N, K;
    static int[] robot;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        K = sc.nextInt();
        robot = new int[K];
        for (int i = 0; i < K; i++) {
            robot[i] = sc.nextInt();
        }
        Arrays.sort(robot);
        int l = 0, r = N, ans = 0;
        while (l < r) {
            int mid = (l + r) / 2;
            if (check(mid)) {
                r = mid - 1;
                ans = mid;
            } else {
                l = mid + 1;
            }
        }
        System.out.print((ans - 1) * 2);
    }
    private static boolean check(int x) {
        int total = 0;
        for (int i = 0; i < K; i++) {
            if (robot[i] - x <= total) {
                if (total >= robot[i]) {
                    total = robot[i] + x - 1;
                } else {
                    total += x;
                }
            } else {
                return false;
            }
        }
        return total >= N;
    }
}

第二题

题目名称：路径计算

给定一个字符串表示路径，计算路径的最短距离。

方法思路

我们可以模拟路径的移动，并计算每个移动的距离。对于每个方向字符，计算其对应的移动距离，然后累加总距离。

解决代码

import java.util.Scanner;
public class Main {
    static String left = "ULDR";
    static String right = "URDL";
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        double[] result = new double[n];
        for (int i = 0; i < n; i++) {
            String s = sc.next();
            result[i] = getResult(s);
        }
        for (int i = 0; i < n; i++) {
            System.out.printf("%.2f\n", result[i]);
        }
    }
    private static double getResult(String s) {
        double r = 0, x = 0, y = 0;
        char way = 'U';
        for (int i = 0; i < s.length(); i++) {
            int start = i;
            if (Character.isDigit(s.charAt(i))) {
                while (start < s.length() && Character.isDigit(s.charAt(start))) {
                    start++;
                }
                int num = Integer.parseInt(s.substring(i, start));
                if (way == 'U') {
                    y += num;
                } else if (way == 'L') {
                    x -= num;
                } else if (way == 'D') {
                    y -= num;
                } else if (way == 'R') {
                    x += num;
                }
                i = start - 1;
            } else {
                char temp = s.charAt(i);
                if (temp == 'L') {
                    int p = left.indexOf(way + "");
                    p = (p + 1) % 4;
                    way = left.charAt(p);
                } else if (temp == 'R') {
                    int p = right.indexOf(way + "");
                    p = (p + 1) % 4;
                    way = right.charAt(p);
                }
            }
        }
        return Math.sqrt(x * x + y * y);
    }
}

第三题

题目名称：模拟题

方法思路

这道题需要模拟一个复杂的系统行为，通过给定的规则逐步计算结果。

解决代码

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        double[] result = new double[n];
        for (int i = 0; i < n; i++) {
            String s = sc.next();
            result[i] = getResult(s);
        }
        for (int i = 0; i < n; i++) {
            System.out.println(result[i]);
        }
    }
    private static double getResult(String s) {
        double x = 0, y = 0;
        for (char c : s.toCharArray()) {
            switch (c) {
                case 'U':
                    x += 10;
                    break;
                case 'D':
                    x -= 10;
                    break;
                case 'L':
                    y -= 10;
                    break;
                case 'R':
                    y += 10;
                    break;
            }
        }
        return Math.sqrt(x * x + y * y);
    }
}

第四题

题目名称：快速幂

方法思路

我们需要计算一个大数的快速幂模运算。通过逐步分解指数，利用模运算的性质，逐步计算结果。

解决代码

import java.io.*;
import java.util.Stream;
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StreamTokenizer IN = new StreamTokenizer(br);
    public static void main(String[] args) throws IOException {
        int t = nextInt();
        while (t-- > 0) {
            long n = nextInt();
            long m = nextInt();
            long p = nextInt();
            long res = 1;
            while (m > 0) {
                if (m % 2 == 1) {
                    res = (res * n) % p;
                }
                m /= 2;
                n = (n * n) % p;
            }
            System.out.println(res % p);
        }
    }
    private static int nextInt() throws IOException {
        return (int) IN.nextToken();
    }
}

这些题目展示了不同类型的编程问题，包括二分搜索应用、路径计算、模拟题和快速幂算法。每个问题都有详细的解释和解决方案，适合不同层次的学习者。

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