蓝桥杯备赛合集

蓝桥杯 - 穿越雷区

解题思路：

dfs

方法一：

import java.util.Scanner;

public class Main {
    static char[][] a;
    static int[][] visited;
    static int[] dx = { 0, 1, 0, -1 };
    static int[] dy = { 1, 0, -1, 0 };
    static long min = Long.MAX_VALUE;
    static long count = 0;

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        a = new char[n][n];
        visited = new int[n][n];
        int startx = 0;
        int starty = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                a[i][j] = in.next().charAt(0);
                if (a[i][j] == 'A') {
                    startx = i;
                    starty = j;
                }
            }
        }
        dfs(startx, starty, n);
        if(min == Integer.MAX_VALUE) min = -1;
        System.out.println(min);

    }

    public static void dfs(int x, int y, int n) {
        visited[x][y] = 1;
        if (a[x][y] == 'B') {
            min = Math.min(min, count);
            return;
        }
        for (int i = 0; i < 4; i++) {
            int xx = x + dx[i];
            int yy = y + dy[i];
            if (xx >= 0 && xx < n && yy >= 0 && yy < n && a[xx][yy] != a[x][y] && visited[xx][yy] == 0) {
                count++;
                dfs(xx, yy, n);
                visited[xx][yy] = 0;
                count--;
            }
        }

    }

}

方法二：

时间复杂度更低，不易超时

import java.util.Scanner;

public class Main {
    static char[][] a;
    static int[][] visited;
    static int[] dx = { 0, 1, 0, -1 };
    static int[] dy = { 1, 0, -1, 0 };
    static int min = Integer.MAX_VALUE;
    static int n;

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        a = new char[n][n];
        visited = new int[n][n];
        String str[] = new String[n];
        int startx = 0;
        int starty = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                a[i][j] = in.next().charAt(0);
                visited[i][j] = Integer.MAX_VALUE;
                if (a[i][j] == 'A') {
                    startx = i;
                    starty = j;
                }
            }
        }
        dfs(startx, starty, 0);
        if (min == Integer.MAX_VALUE)
            min = -1;
        System.out.println(min);
    }

    public static void dfs(int x, int y, int step) {
        visited[x][y] = step;
        if (a[x][y] == 'B') {
            min = Math.min(min, step);
            return;
        }
        for (int i = 0; i < 4; i++) {
            int xx = x + dx[i];
            int yy = y + dy[i];
            if (xx >= 0 && xx < n && yy >= 0 && yy < n && a[xx][yy] != a[x][y] && visited[x][y] + 1 < visited[xx][yy]) {
                dfs(xx, yy, step + 1);
            }
        }
    }
}

蓝桥杯 - 玩具蛇

解题思路：

dfs

public class Main {
    static final int N = 4;
    static int[][] visited = new int[N][N];
    static int count = 0;
    
    public static void main(String[] args) {
        for (int i = 0; i < N; i++) { //16种位置开始的可能
            for (int j = 0; j < N; j++) {
                dfs(i, j, 1);
            }
        }
        System.out.println(count);
    }
    
    public static void dfs(int x, int y, int step) {
        if (visited[x][y] == 0) {
            visited[x][y] = 1;
            dfs_two(x, y, step + 1);
            visited[x][y] = 0;
        }
    }
    
    public static void dfs_two(int x, int y, int step) {
        if (step == 17) {
            count++;
            return;
        }
        if (x > 0) dfs(x - 1, y, step); //上
        if (x + 1 < N) dfs(x + 1, y, step); //下
        if (y > 0) dfs(x, y - 1, step); //左
        if (y + 1 < N) dfs(x, y + 1, step); //右
    }
    
}

蓝桥杯 - 受伤的皇后

解题思路：

递归 + 回溯（n皇后问题的变种）

在 N 皇后问题的解决方案中，我们是从棋盘的顶部向底部逐行放置皇后的，这意味着在任何给定时间，所有未来的行（即当前行之下的所有行）都还没有被探查或放置任何皇后。因此，检查下方行是没有意义的，因为它们总是空的。所以只需要检查左上45°和右上45°。

import java.util.Scanner;

public class Main {
    static int count = 0;

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int[][] arr = new int[n][n];
        dfs(arr, 0);
        System.out.println(count);
    }

    public static void dfs(int[][] arr, int row) {
        if (row == arr.length) {
            count++;
            return;
        }
        // 遍历列,因为n行n列，所以arr.length和arr[0].length是一样的
        for (int j = 0; j < arr.length; j++) {
            if (checkValid(arr, row, j)) {
                arr[row][j] = 1;
                dfs(arr, row + 1);
                // 回溯
                arr[row][j] = 0;
            }
        }
    }

    public static boolean checkValid(int[][] arr, int row, int col) {
        // 检查列,因为n行n列，所以row既是行的长度又是列的长度
        for (int i = 0; i < row; i++) {
            if (arr[i][col] == 1) {
                return false;
            }
        }
        // 检查左上45°
        for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
            if (arr[i][j] == 1 && Math.abs(row - i) < 3) {
                return false;
            }
        }
        // 检查右上45°
        for (int i = row - 1, j = col + 1; i >= 0 && j < arr.length; i--, j++) {
            if (arr[i][j] == 1 && Math.abs(row - i) < 3) {
                return false;
            }
        }
        return true;
    }
}

蓝桥杯 - 小朋友崇拜圈

解题思路：

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        // 由题意，下标从1开始比较好
        int[] arr = new int[n + 1];
        for (int i = 1; i < arr.length; i++) {
            arr[i] = scan.nextInt();
        }

        int maxLen = 0;
        // 从每个人开始遍历一次取最大值
        for (int i = 1; i < arr.length; i++) {
            int len = circle(arr, i, 0);
            if (maxLen < len) {
                maxLen = len;
            }
        }
        System.out.println(maxLen);
    }

    public static int circle(int[] arr, int i, int len) {
        int key = arr[i];
        len++;
        //崇拜对象不是自己时
        while (key != i) {
            //一直追踪崇拜对象的崇拜对象
            key = arr[key];
            len++;
        }
        return len;
    }
}

蓝桥杯 - 走迷宫

解题思路：

经典dfs题目，需要重点掌握。

养成好习惯，静态方法都要用到的变量提前想到定义为静态常量。

import java.util.Scanner;

public class Main {
    //注意加static，经常忘记导致编译错误
    static int N, M, x1, x2, y1, y2, min = Integer.MAX_VALUE;
    static int[][] a, v;

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        N = scan.nextInt();
        M = scan.nextInt();
        
        // 初始化网格，注意题目条件，出发点和终点的坐标都是从1开始，所以我们的下标不能像往常一样从0开始
        a = new int[N + 1][M + 1];
        //初始化记录最少步数的访问数组
        v = new int[N + 1][M + 1];

        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= M; j++) {
                a[i][j] = scan.nextInt();
                //赋最大值，代表没有被访问过
                v[i][j] = Integer.MAX_VALUE;
            }
        }

        x1 = scan.nextInt();
        y1 = scan.nextInt();
        x2 = scan.nextInt();
        y2 = scan.nextInt();
        
        dfs(0, x1, y1);
        
        // 如果找不到路径，则输出-1，否则输出最短路径长度
        if (min == Integer.MAX_VALUE) {
            min = -1;
        }
        System.out.println(min);
    }

    public static void dfs(int step, int x, int y) {
        v[x][y] = step;
        if (x == x2 && y == y2) {
            min = Math.min(min, step);
            return;
        }
        
        // 方向数组
        int[] dx = { 1, -1, 0, 0 };
        int[] dy = { 0, 0, 1, -1 };
        
        // 尝试向四个方向搜索
        for (int i = 0; i < 4; i++) {
            int xx = x + dx[i];
            int yy = y + dy[i];
            //注意v[x][y] + 1 < v[xx][yy]，我们继续dfs的前提是v[xx][yy]没有被访问，
            //或当前路径长度加1到达v[xx][yy]后比v[xx][yy]本身的路径更短
            if (xx > 0 && yy > 0 && xx <= N && yy <= M && v[x][y] + 1 < v[xx][yy] && a[xx][yy] == 1) {
                dfs(step + 1, xx, yy);
            }
        }
    }
}

蓝桥杯 - 正则问题

解题思路：

dfs

import java.util.Scanner;

public class Main {
    static int pos = -1; // 充当charAt下标
    static String s;// 字符串型的静态变量

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        s = scanner.nextLine();
        System.out.println(dfs());
    }

    private static int dfs() {
        int current = 0;// 目前x的最大个数
        int max = 0;// 最终x的最大个数
        while (pos < s.length() - 1) {// 遍历整个正则表达式，这里length()-1是为了防止最后一次pos=s.length时导致s.charAt(pos)越界
            pos++;
            if (s.charAt(pos) == '(') { // 进入下一层
                current += dfs(); // 叠加长度，利用了回溯的方法
            } else if (s.charAt(pos) == 'x') {// 累计x的个数
                current++;
            } else if (s.charAt(pos) == '|') {// 取最大值
                max = Math.max(current, max);
                current = 0;// 但是目前的x最大值变为0
            } else { // 遇到) 跳出本轮循环
                break;
            }
        }
        return Math.max(max, current);// 输出最大的x个数
    }

}

蓝桥杯 - 九宫幻方

解题思路：

枚举法

import java.util.Scanner;

//枚举法，采用枚举的方式存储不同的九宫格排列
public class Main {
    // 定义九个不同的九宫格排列
    public static int[][] exp = {
            { 4, 9, 2, 3, 5, 7, 8, 1, 6 },
            { 8, 3, 4, 1, 5, 9, 6, 7, 2 },
            { 6, 1, 8, 7, 5, 3, 2, 9, 4 },
            { 2, 7, 6, 9, 5, 1, 4, 3, 8 },
            { 2, 9, 4, 7, 5, 3, 6, 1, 8 },
            { 6, 7, 2, 1, 5, 9, 8, 3, 4 },
            { 8, 1, 6, 3, 5, 7, 4, 9, 2 },
            { 4, 3, 8, 9, 5, 1, 2, 7, 6 }
    };

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int[] arr = new int[9];
        // 读取用户输入的九宫格数字
        for (int i = 0; i < 9; i++) {
            arr[i] = scan.nextInt();
        }
        int cnt = 0;
        int position = 0;

        // 遍历不同的九宫格排列，查看是否和用户输入一致
        for (int i = 0; i < 8; i++) {
            int flag = 1;
            for (int j = 0; j < 9; j++) {
                if (arr[j] != 0 && arr[j] != exp[i][j]) {
                    flag = 0;
                    break;
                }
            }
            if (flag == 1) {
                cnt++;
                position = i;
            }
        }
        
        //输出
        if (cnt == 1) {
            for (int i = 0; i < 9; i++) {
                System.out.print(exp[position][i]);
                //i从0开始，判断换行时需要加1
                if ((i + 1) % 3 == 0) System.out.println();
                else System.out.print(" ");
            }
        } else {
            System.out.print("Too Many");
        }
    }
}

第十二届蓝桥杯JavaA组省赛真题 - 相乘

解题思路：

暴力

public class Main {
    public static void main(String[] args) {
        for (long i = 1; i <= 1000000007; i++) {
            if (i * 2021 % 1000000007 == 999999999) System.out.print(i);
            else System.out.print(0);
        }
    }
}

第十二届蓝桥杯JavaA组省赛真题 - 左孩子右兄弟

解题思路：

动态规划

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int[] father = new int[n + 1];
        int[] cnt = new int[n + 1];
        int[] dp = new int[n + 1];

        for (int i = 2; i <= n; i++) {
            int f = scan.nextInt();
            father[i] = f;
            //记录父节点出现的次数
            cnt[f]++;
        }
        int max = 0;
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[father[i]] + cnt[father[i]];
            max = Math.max(max, dp[i]);
        }
        System.out.print(max);
    }
}

第十三届蓝桥杯JavaA组省赛真题 - 蜂巢

解题思路：

注意：

1.静态方法只能访问静态变量

static int[] x = new int[] { -2, -1, 1, 2, 1, -1 };
static int[] y = new int[] { 0, 1, 1, 0, -1, -1 };

或者

static int[] x = { -2, -1, 1, 2, 1, -1 };

static int[] y = { 0, 1, 1, 0, -1, -1 };

都可以

2.并且在Java中，static变量不能在方法内部声明，它们必须作为类的成员变量声明。

import java.util.Scanner;

public class Main {
    static int[] x = new int[] { -2, -1, 1, 2, 1, -1 };
    static int[] y = new int[] { 0, 1, 1, 0, -1, -1 };

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int d1 = scan.nextInt();
        long p1 = scan.nextLong();
        long q1 = scan.nextLong();
        int d2 = scan.nextInt();
        long p2 = scan.nextLong();
        long q2 = scan.nextLong();
        long[] pos1 = new long[2];
        long[] pos2 = new long[2];

        getPositon(d1, p1, q1, pos1);
        getPositon(d2, p2, q2, pos2);
        System.out.print(getWay(pos1, pos2));
    }

    public static void getPositon(int d, long p, long q, long[] pos) {
        pos[0] = p * x[d] + q * x[(d + 2) % 6];
        pos[1] = p * y[d] + q * y[(d + 2) % 6];
    }

    public static long getWay(long[] pos1, long[] pos2) {
        long dx = Math.abs(pos1[0] - pos2[0]);
        long dy = Math.abs(pos1[1] - pos2[1]);
        if (dx >= dy) return (dx + dy) / 2;
        else return dy;
    }
}

第十三届蓝桥杯JavaA组省赛真题 - 求和

解题思路：

这，真的是，省赛真题吗...

public class Main {
    public static void main(String[] args) {
        long res = 0;
        for (int i = 1; i <= 20230408; i++) {
            res += i;
        }
        System.out.print(res);
    }
}

第十三届蓝桥杯JavaA组省赛真题 - GCD

解题思路：

找规律

最大的最小公因数就是两数的差值
5 7 gcd=2
1 3 gcd=2
1 4 gcd=3

import java.util.Scanner;

public class Main {
       public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        long a = scan.nextLong();
        long b = scan.nextLong();
        long c = Math.abs(a - b);
        long k = 0;

        //逆推
        k = c - (a % c);
        System.out.println(k);
    }
    
}

第十三届蓝桥杯JavaA组省赛真题 - 寻找整数

解题思路：

找规律：

n mod 2=1时，n只能等于 1 3 5 7 9 11 13，中间的间隔为2 。

在上面的基础上n mod 3=2时，n只能等于 5 11 17 23 29，中间间隔为6（2和3的最小公倍数）。

在上面的基础上n mod 4=1时，n只能等于 29 41 53 65 77 89 91 103 115 127 139，中间间隔为12（2和3和4的最小公倍数）。

在上面的基础上n mod 5=4时，n只能等于 139 199 259 319，中间间隔为60 （2和3和4和5的最小公倍数）。

由此可以发现中间间隔的规律。

第一个数只能通过上一轮第一个数不断加上之前几轮的最小公倍数的方式来遍历得到。

public class Main {
    public static void main(String[] args) {
        int[] mod = { 0, 0, 1, 2, 1, 4, 5, 4, 1, 2, 9, 0, 5, 10, 11, 14,
                9, 0, 11, 18, 9, 11, 11, 15, 17, 9, 23, 20, 25, 16, 29, 27, 25,
                11, 17, 4, 29, 22, 37, 23, 9, 1, 11, 11, 33, 29, 15, 5, 41, 46 };
        long res = 0;
        long step = 1; // 记录步长
        for (int i = 2; i <= 49; i++) {
            // 由小到大寻找满足模数的答案
            while (res % i != mod[i]) {
                res += step;
            }
            step = lcm(step, i); // 增加步长
        }
        System.out.println(res);
    }

    public static long gcd(long a, long b) {
        return b == 0 ? a : gcd(b, a % b);
    }
    public static long lcm(long a, long b) {
        return a * b / gcd(a, b);
    }
}

第十三届蓝桥杯JavaA组省赛真题 - 青蛙过河

解题思路：

定义一个累和数组arr，我们可以比较arr[ i ]和arr[ l ]之间的差值看是否大于等于2倍的x，满足则证明这两点之间可以跳满所有实际过河次数，此时记录最大距离，并移动左边界 l

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int x = sc.nextInt();
        int[] arr = new int[n + 1];
        // 注意范围，arr[0]是起始岸，arr[n]是对岸
        for (int i = 1; i < n; i++) {
            arr[i] = sc.nextInt() + arr[i - 1];
        }
        // 对岸可以跳无数次
        arr[n] = arr[n - 1] + 99999999;
        
        int res = 0;
        int l = 0;
        for (int i = 1; i <= n; i++) {
            if (arr[i] - arr[l] >= 2 * x) {
                res = Math.max(res, i - l);
                // 遇到的第一个max就要让l++，因为求的是最低跳跃能力,青蛙往距离最近且石头高度不为0的地方跳就行
                l++;
            }
        }
        System.out.print(res);
    }
}

第十三届蓝桥杯JavaA组省赛真题 - 裁纸刀

解题思路：

一道简单的数学题

先看例子，边缘必须裁四次，然后得到两行三列共六张二维码。

横线5裁一次，竖线6 7 8 9各裁一次，加上裁边缘的四次，共九次。

也就是说，横向裁剪次数为【行数 - 1】。竖向裁剪次数为【(列数 - 1) * 行数】。

题目共20行22列，则次数为：4 + 19 + (21*20) = 443次。

public class Main {
    public static void main(String[] args) {
        int res = 4 + (20 - 1) + 20 * (22 - 1);
        System.out.print(res);
    }
}