蓝桥杯备赛合集（题目 + 题解）
·
蓝桥杯 - 穿越雷区
解题思路：
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];
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);
}
}
第十四届蓝桥杯JavaA组省赛真题 - 棋盘
解题思路：
暴力
棋盘类题目取反操作：
f[a][b]^=1; 或者f[a][b] = 1 - f[a][b];
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
int m = scan.nextInt();
int[][] f = new int[n][n];
for (int i = 0; i < m; i++) {
int x1 = scan.nextInt();
int y1 = scan.nextInt();
int x2 = scan.nextInt();
int y2 = scan.nextInt();
for (int a = x1 - 1; a < x2; a++) {
for (int b = y1 - 1; b < y2; b++) {
f[a][b] ^= 1;
}
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
System.out.print(f[i][j]);
if ((j + 1) == n)
System.out.println();
}
}
}
}
第十四届蓝桥杯JavaA组省赛真题 - 平均
解题思路：
使用HashMap构造键值对存储
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
Map<Integer, ArrayList<Integer>> map = new HashMap<>();
for (int i = 0; i < 10; i++) {
map.put(i, new ArrayList<Integer>());
}
for (int i = 0; i < n; i++) {
map.get(scan.nextInt()).add(scan.nextInt());
}
int target = n / 10;
int res = 0;
for (int i = 0; i < 10; i++) {
if (map.containsKey(i)) {
Collections.sort(map.get(i));
for (int j = 0; j < map.get(i).size() - target; j++) {
res += map.get(i).get(j);
}
}
}
System.out.print(res);
}
}
第十四届蓝桥杯JavaA组省赛真题 - 互质数的个数
解题思路：
快速幂 + 欧拉函数
快速幂比较常见于数据较大的取模场景，欧拉函数感觉还是有点抽象
注意：
取模的时候就不要简写了，例如：res = res * a % mod;不要写成res *= a % mod;
import java.util.Scanner;
public class Main {
static int mod = 998244353;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
long a = sc.nextLong();
long b = sc.nextLong();
// 如果a等于1，则直接输出0，因为任何数的0次方都是1
if (a == 1) System.out.println(0);
// 初始化结果res为a
long res = a, x = a;
// 循环，从2开始到x的平方根，检查x的因子
for (int i = 2; i <= Math.sqrt(x); i++) {
// 如果i是x的因子
if (x % i == 0) {
// 不断除以i，直到x不能被i整除
while (x % i == 0) x /= i;
// 根据欧拉定理，将res中所有i的因子替换为i-1
res = res / i * (i - 1);
}
}
// 如果x还有大于1的因子，重复上述操作
if (x > 1) res = res / x * (x - 1);
// 输出结果，为res乘以a的b-1次方，并对mod取模
System.out.println(res * qmi(a, b - 1) % mod);
}
// 快速幂运算方法，用于计算a的b次方模mod的值
private static long qmi(long a, long b) {
long res = 1;
while (b > 0) {
if ((b % 2) == 1) res = res * a % mod;
a = a * a % mod;
b /= 2;
}
return res % mod;
}
}
第十四届蓝桥杯JavaA组省赛真题 - 特殊日期
解题思路：
暴力秒了
public class Main {
public static void main(String[] args) {
int cnt = 0;
for (int i = 1900; i <= 9999; i++) {
for (int j = 1; j <= 12; j++) {
for (int k = 1; k <= days(i, j); k++) {
if (sum(i) == sum(j) + sum(k)) cnt++;
}
}
}
System.out.print(cnt);
}
public static int days(int i, int j) {
if (j == 1 || j == 3 || j == 5 || j == 7 || j == 8 || j == 10 || j == 12)
return 31;
if (j == 4 || j == 6 || j == 9 || j == 11)
return 30;
if (j == 2 && i % 400 == 0 || (i % 4 == 0 && i % 100 != 0))
return 29;
return 28;
}
public static int sum(int x) {
int s = 0;
while (x != 0) {
s += x % 10;
x /= 10;
}
return s;
}
}
蓝桥杯 - 小明的背包1（01背包）
解题思路：
本题属于01背包问题，使用动态规划
dp[ j ]表示容量为 j 的背包的最大价值
注意：
需要时刻提醒自己dp[ j ]代表的含义，不然容易晕头转向
注意越界问题，且 j 需要倒序遍历
如果正序遍历
dp[1] = dp[1 - volume[0]] + value[0] = 15
dp[2] = dp[2 - volume[0]] + value[0] = 30
此时dp[2]就已经是30了，意味着物品0，被放入了两次，所以不能正序遍历。
为什么倒叙遍历，就可以保证物品只放入一次呢？
倒叙就是先算dp[2]
dp[2] = dp[2 - volume[0]] + value[0] = 15 （dp数组已经都初始化为0）
dp[1] = dp[1 - volume[0]] + value[0] = 15
所以从后往前循环，每次取得状态不会和之前取得状态重合，这样每种物品就只取一次了。
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int N = scan.nextInt();
int V = scan.nextInt();
int[] volume = new int[N];
int[] value = new int[N];
for (int i = 0; i < N; i++) {
volume[i] = scan.nextInt();
value[i] = scan.nextInt();
}
int[] dp = new int[V + 1];
for (int i = 0; i < N; i++) {
//注意越界问题，且 j 需要从大到小遍历
for (int j = V; j >= volume[i]; j--) {
dp[j] = Math.max(dp[j], dp[j - volume[i]] + value[i]);
}
}
System.out.println(dp[V]);
}
}
蓝桥杯 - 小明的背包2（完全背包）
解题思路：
本题属于完全背包问题，背包内物品可以重复，使用动态规划
dp[ j ]表示容量为 j 的背包的最大价值
注意：
需要时刻提醒自己dp[ j ]代表的含义，不然容易晕头转向
注意越界问题，且 j 需要正序遍历
如果正序遍历
dp[1] = dp[1 - volume[0]] + value[0] = 15
dp[2] = dp[2 - volume[0]] + value[0] = 30
此时dp[2]就已经是30了，意味着物品0，被放入了两次，因为可以重复，所以需要正序遍历。
为什么倒叙遍历，就可以保证物品只放入一次呢？
倒叙就是先算dp[2]
dp[2] = dp[2 - volume[0]] + value[0] = 15 （dp数组已经都初始化为0）
dp[1] = dp[1 - volume[0]] + value[0] = 15
所以从后往前循环，每次取得状态不会和之前取得状态重合，这样每种物品就只取一次了。
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int N = scan.nextInt();
int V = scan.nextInt();
int[] volume = new int[N];
int[] value = new int[N];
for (int i = 0; i < N; i++) {
volume[i] = scan.nextInt();
value[i] = scan.nextInt();
}
int[] dp = new int[V + 1];
for (int i = 0; i < N; i++) {
for (int j = volume[i]; j <= V; j++) {
dp[j] = Math.max(dp[j], dp[j - volume[i]] + value[i]);
}
}
System.out.println(dp[V]);
}
}
蓝桥杯 - 小明的背包3（多重背包）
解题思路：
动态规划
多重背包问题需要在01背包问题（不重复）的基础上多加一层循环进行遍历，并且dp[ j ]的式子也需要修改
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int N = scan.nextInt();
int V = scan.nextInt();
int[] volume = new int[N];
int[] value = new int[N];
int[] s = new int[N];
for (int i = 0; i < N; i++) {
volume[i] = scan.nextInt();
value[i] = scan.nextInt();
s[i] = scan.nextInt();
}
int[] dp = new int[V + 1];
for (int i = 0; i < N; i++) {
//倒序遍历，确保不会重复
for (int j = V; j >= volume[i]; j--) {
//因为至少一个，所以 k 从一开始取
for (int k = 1; k <= s[i] && k * volume[i] <= j; k++)
dp[j] = Math.max(dp[j], dp[j - k * volume[i]] + k * value[i]);
}
}
System.out.println(dp[V]);
}
}
第十二届蓝桥杯JavaB组省赛真题 - 卡片
解题思路：
多列几项，找规律
发现如果有 k 种卡片，那么对应的最大人数是 k * ( k + 1 ) / 2，然后比较 n 和 sum 的大小即可
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
int k = 1;
while (true) {
int sum = k * (k + 1) / 2;
if (n > sum) k++;
else break;
}
System.out.print(k);
}
}
第十二届蓝桥杯JavaB组省赛真题 - 货物摆放
解题思路：
暴力
优化前（代码没有错，但会超时）：
import java.util.*;
public class Main {
public static void main(String[] args) {
long n = 2021041820210418L;
long cnt = 0;
for (long a = 1; a <= n; a++) {
for (long b = 1; b <= n; b++) {
for (long c = 1; c <= n; c++) {
if (a * b * c == n) cnt++;
}
}
}
System.out.print(cnt);
}
}
优化后（先求出目标数字的所有分解因子，再根据这些分解因子暴力求解）：
注意：
list.size()方法返回的是int类型，所以在for循环语句上作为条件比较时，如果不强制转型，
那么a，b，c都要是int类型
import java.util.*;
public class Main {
public static void main(String[] args) {
long n = 2021041820210418L;
long cnt = 0;
List<Long> list = new ArrayList<>();
for (long i = 1; i <= Math.sqrt(n); i++) {
if (n % i == 0) {
list.add(i);
list.add(n / i);
}
}
for (int a = 0; a < list.size(); a++) {
for (int b = 0; b < list.size(); b++) {
for (int c = 0; c < list.size(); c++) {
if (list.get(a) * list.get(b) * list.get(c) == n)
cnt++;
}
}
}
System.out.print(cnt);
}
}
第十二届蓝桥杯JavaB组省赛真题 - 最少砝码
解题思路：
开始以为是一道动态规划，结果是贪心（此题是找规律）
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
int res = 1;
int cur = 1;
int total = 1;
while (total < n) {
res++;
cur *= 3;
total += cur;
}
System.out.print(res);
}
}
第十二届蓝桥杯JavaB组省赛真题 - 路径
解题思路：
动态规划
需要熟练掌握最小公倍数和最大公约数的计算
import java.util.*;
public class Main {
public static void main(String[] args) {
int[] dp = new int[2022];
dp[1] = 0;
for (int i = 2; i <= 2021; i++) {
dp[i] = Integer.MAX_VALUE;
}
for (int i = 1; i <= 2020; i++) {
for (int j = i + 1; j <= 2021 && (j - i <= 21); j++) {
dp[j] = Math.min(dp[i] + le(i, j), dp[j]);
}
}
System.out.print(dp[2021]);
}
public static int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
public static int le(int a, int b) {
return a * b / gcd(a, b);
}
}
第十二届蓝桥杯JavaB组省赛真题 - 时间显示
解题思路：
数量级较大，需要使用long类型
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
long num = scan.nextLong();
long allseconds = num / 1000;
long seconds = allseconds % 60;
long allmins = allseconds / 60;
long mins = allmins % 60;
long allhours = allmins / 60;
long hours = allhours % 24;
String date = String.format("%02d", hours) + ":" + String.format("%02d", mins) + ":" +
String.format("%02d", seconds);
System.out.println(date);
}
}
第十二届蓝桥杯JavaB组省赛真题 - 直线
解题思路：
注意：
1.计算斜率 k 和截距 b 时，因为使用到除法，所以需要使用double类型
2.x1，x2，y1，y2需要初始化为0
3.需要使用List装多个map，这样相同的x可以对应不同的y，仅使用map无法做到一对多
4.需要使用HashSet防止重复
5.截距公式 double b = (x2 * y1 - x1 * y2) / (x2 - x1);由b = y1 - k * x1代入 k 推导而出，但因为小数精度问题，需要人为化简（这里不化简是错的，挺坑的）
6.注意entry的使用
import java.util.*;
public class Main {
public static void main(String[] args) {
List<Map<Integer, Integer>> list = new ArrayList<>();
Set<Map<Double, Double>> res = new HashSet<>();
for (int i = 0; i < 20; i++) {
for (int j = 0; j < 21; j++) {
Map<Integer, Integer> map = new HashMap<>();
map.put(i, j);
list.add(map);
}
}
double x1 = 0, x2 = 0, y1 = 0, y2 = 0;
for (int i = 0; i < list.size(); i++) {
for (int j = i + 1; j < list.size(); j++) {
for (Map.Entry<Integer, Integer> entry : list.get(i).entrySet()) {
x1 = entry.getKey();
y1 = entry.getValue();
}
for (Map.Entry<Integer, Integer> entry : list.get(j).entrySet()) {
x2 = entry.getKey();
y2 = entry.getValue();
}
if (x1 == x2 || y1 == y2) continue;
double k = (y1 - y2) / (x1 - x2);
double b = (x2 * y1 - x1 * y2) / (x2 - x1);
Map<Double, Double> temp = new HashMap<>();
temp.put(k, b);
res.add(temp);
}
}
// 增加水平和垂直的直线条数
System.out.print(res.size() + 21 + 20);
}
}
第十二届蓝桥杯JavaB组省赛真题 - ASC
解题思路：
这是目前为止做到过最简单的了
public class Main {
public static void main(String[] args) {
int res = 'L'-'A' + 65;
System.out.print(res);
}
}
第十三届蓝桥杯JavaB组 - 最大子矩阵
69859241839387868941
17615876963131759284
37347348326627483485
53671256556167864743
16121686927432329479
13547413349962773447
27979945929848824687
53776983346838791379
56493421365365717745
21924379293872611382
93919353216243561277
54296144763969257788
96233972513794732933
81443494533129939975
61171882988877593499
61216868895721348522
55485345959294726896
32124963318242554922
13593647191934272696
56436895944919899246
解题思路：
填空题直接暴力
注意矩阵转换为二维数组的方式即可
public class Main {
public static void main(String[] args) {
String str = "69859241839387868941" + "17615876963131759284" + "37347348326627483485" + "53671256556167864743"
+ "16121686927432329479" + "13547413349962773447" + "27979945929848824687" + "53776983346838791379"
+ "56493421365365717745" + "21924379293872611382" + "93919353216243561277" + "54296144763969257788"
+ "96233972513794732933" + "81443494533129939975" + "61171882988877593499" + "61216868895721348522"
+ "55485345959294726896" + "32124963318242554922" + "13593647191934272696" + "56436895944919899246";
char[] tmp = str.toCharArray();
int[][] arr = new int[20][20];
int k = 0;
for (int i = 0; i < 20; i++) {
for (int j = 0; j < 20; j++) {
arr[i][j] = tmp[k] - '0';
k++;
}
}
int max = 0;
for (int m = 0; m < 15; m++) {
for (int n = 0; n < 15; n++) {
int sum = 0;
for (int i = m; i < 5 + m; i++) {
for (int j = n; j < 5 + n; j++) {
sum += arr[i][j];
}
}
max = Math.max(max, sum);
}
}
System.out.print(max);
}
}
第十三届蓝桥杯JavaB组省赛真题 - 最少刷题数
解题思路：
以中位数为基准，比中位数小的需要在一定条件下增大
注意：
需要特别考虑arr[ i ]等于中位数的情况
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int[] arr = new int[n];
int[] copyarr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = scanner.nextInt();
copyarr[i] = arr[i];
}
// 将新的复制数组进行排序
Arrays.sort(copyarr);
int median = copyarr[copyarr.length / 2];
int[] res = new int[n];
int lage = 0;// 是否加1的控制开关 默认不加
int bigger = 0;
int smaller = 0;
int mid = 0;
// 找出比中间值大的数有多少 比中间值小的数有多少
for (int i = 0; i < arr.length; i++) {
if (copyarr[i] > median) {
bigger++;
} else if (copyarr[i] < median) {
smaller++;
}
}
if (bigger >= smaller) lage = 1;
if (bigger > smaller) mid = 1;
for (int i = 0; i < n; i++) {
if (arr[i] < median) {
res[i] = median + lage - arr[i];
} else if (arr[i] == median && mid == 1) {
res[i] = median + mid - arr[i];
} else {
res[i] = 0;
}
}
for (int i = 0; i < n; i++) {
System.out.print(res[i] + " ");
}
}
}
第十三届蓝桥杯JavaB组省赛真题 - 求阶乘
解题思路：
1.可以看出数量级比较大，需要用long
2.采用二分法求解
3.get_zero()方法用于获取末尾零的数量：
求阶乘末尾0的个数其实就是求阶乘因子中5的个数
5！= 1 * 2 * 3 * 4 * 5 = 120
10！ = 1 * 2 * 3 * 4 * 5 * ... * 9 * 2 * 5 = 3628800
15！= 1 * 2 * 3 * 4 * 5 * ... * 9 * 2 * 5 * ... * 14 * 3 * 5 = 1307674368000
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
long k = scan.nextLong();
long l = 1L;
long r = Long.MAX_VALUE - 1;
while (l < r) {
long mid = (l + r) / 2;
if (k <= get_zero(mid)) r = mid;
else l = mid + 1;
}
//使用r传参，mid在while循环内部，循环外部无法访问
if (k != get_zero(r)) System.out.print(-1);
else System.out.print(r);
}
public static long get_zero(long x) {
long res = 0;
while (x != 0) {
res += x / 5;
x /= 5;
}
return res;
}
}
第十三届蓝桥杯JavaB组 - 字符统计
解题思路：
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
String str = scan.next();
Map<Character, Integer> map = new HashMap<>();
List<Character> list = new ArrayList<>();
for (int i = 0; i < str.length(); i++) {
char s = str.charAt(i);
if (map.containsKey(s)) map.put(s, map.get(s) + 1);
else map.put(s, 1);
}
int max = 0;
for (Character c : map.keySet()) {
if (map.get(c) >= max) max = map.get(c);
}
for (Character c : map.keySet()) {
if (map.get(c) == max) list.add(c);
}
Collections.sort(list);
for (Character c : list) {
System.out.print(c);
}
}
}
第十三届蓝桥杯JavaB组省赛真题 - 山
public class Main {
public static void main(String[] args) {
int sum = 0;
for (int i = 2022; i <= 2022222022; i++) {
if (isUp(i) && isMirror(i)) sum++;
}
System.out.println(sum);
}
public static boolean isUp(int n) {
String num = n + "";
int len = num.length();
int mid = len % 2 == 0 ? len / 2 : len / 2 + 1;
for (int i = 1; i < mid; i++) {
if (num.charAt(i) < num.charAt(i - 1)) return false;
}
return true;
}
public static boolean isMirror(int n) {
StringBuffer s = new StringBuffer(n + "");
if ((s.toString()).equals(s.reverse().toString())) return true;
else return false;
}
}
第十三届蓝桥杯JavaB组省赛真题 - 星期计算
解题思路：
方法一：
20的22次方是一个比较大的数，long和int都装不下这么大的数，因此需要使用下面的方法，如果 a, b, p 都是整数，且 p 是正数，那么：(a * b) % p = (a % p * b % p) % p
public class Main {
public static void main(String[] args) {
int res = 1;
for(int i = 0;i<22;i++)
res = res * 20 % 7;
res = (res + 6) % 7;
if(res == 0) System.out.println(7);
else System.out.println(res);
}
}
方法二：
使用BigInteger（记得引包）
注意：
比较值的时候需要用compareTo
import java.math.BigInteger;
public class Main {
public static void main(String[] args) {
BigInteger res = BigInteger.valueOf(20).pow(22).add(BigInteger.valueOf(6)).mod(BigInteger.valueOf(7));
if (res.compareTo(BigInteger.valueOf(0)) == 0) System.out.println(7);
else System.out.println(res);
}
}
第十四届蓝桥杯JavaB组省赛真题 - 蜗牛
dp[i][0] 状态转移方程：
1. 从上一个竹竿的底部转移过来，即：
dp[i][0]=dp[i−1][0]+x[i]−x[i−1];
2. 从上一个竹竿的传送门转移过来，即：
dp[i][0]=dp[i−1][1]+b[i]/1.3;
dp[i][1] 状态转移方程：
1. 从上一个竹竿的底部转移过来，即：
dp[i][1]=dp[i−1][0]+x[i]−x[i−1]+a[i]/0.7;
2.从上一个竹杠传送门过来：
需要判断上一个竹杠传送门过来后是在当前竹杠传送门上分还是下方，在当前竹杠传送门上分就需要向下移动，否则反之。
a[i]>b[i]
dp[i][1] = Math.min(dp[i-1][0] + x[i]-x[i-1] + a[i]/0.7, dp[i-1][1] + (a[i]-b[i])/0.7);
b[i]>=a[i]
dp[i][1] = Math.min(dp[i-1][0] + x[i]-x[i-1] + a[i]/0.7,dp[i-1][1] + (b[i]-a[i]) /1.3);
注意：
数组a的下标是从一开始的，而数组b的下标是从二开始的。
import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] x = new int[n+1];
int[] a = new int[n+1];
int[] b = new int[n+1];
for(int i = 1;i<=n;i++){
x[i] = sc.nextInt();
}
for(int i = 1;i<n;i++){
a[i] = sc.nextInt();
b[i+1] = sc.nextInt();
}
double[][] dp = new double[n+1][2];
dp[1][0] = x[1];
dp[1][1] = x[1] + a[1]/0.7;
for(int i = 2;i <= n;i++){
if(a[i]>b[i]){
dp[i][1] = Math.min(dp[i-1][0] + x[i]-x[i-1] + a[i]/0.7, dp[i-1][1] + (a[i]-b[i])/0.7);
}else {
dp[i][1] = Math.min(dp[i-1][0] + x[i]-x[i-1] + a[i]/0.7,dp[i-1][1] + (b[i]-a[i]) /1.3);
}
dp[i][0] = Math.min(dp[i-1][1] +b[i]/1.3 ,dp[i-1][0]+x[i]-x[i-1]);
}
System.out.printf("%.2f",dp[n][0]);
}
}
第十四届蓝桥杯JavaB组省赛真题 - 阶乘求和
/ 10^9考虑前九位，% 10^9保留后9位
解题思路:
求获取结果的后九位数字，需要对10^9取余，因为202320232023这个数字的阶乘太大，必须要减少计算量，因为当一个整数乘以10^9后对其取余，那么结果都为0。
所以我们只需要找到从第几个数的阶乘开始乘以了10^9即可，所以说从100开始（实际上最少可以从40左右开始，40及其之后的数字都可以，但我们不可能一下子的精确的通过估算找到40这个数，所以可以取大一些，不过是时间长了点，结果是没问题的），后面的数的阶乘就可以直接省略了。就把问题简化为了从1的阶乘加到100的阶乘，取其后9位数字。
import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改
public class Main {
public static void main(String[] args) {
long sum = 0, num;
int mod = (int) Math.pow(10, 9);
for (int i = 1; i <= 100; i++) {
num = 1;
for (int j = 1; j <= i; j++) {
num *= j;
num %= mod;
}
sum += num;
sum %= mod;
}
System.out.println(sum);
}
}
第十四届蓝桥杯JavaB组省赛真题 - 矩形总面积
测试用例范围比较大，所以全部用long类型，如果用int类型只能通过60%，建议在内存和运行时间允许的情况下，比赛题都用long。
重点在于计算相交的面积，这里找的两个相交点是左上角（m1,n1）和右下角（m2,n2）
import java.util.*;
// 1:无需package
// 2: 类名必须Main, 不可修改
public class Main {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
long x1 = scan.nextInt();
long y1 = scan.nextInt();
long x2 = scan.nextInt();
long y2 = scan.nextInt();
long x3 = scan.nextInt();
long y3 = scan.nextInt();
long x4 = scan.nextInt();
long y4 = scan.nextInt();
long m1 = Math.max(Math.min(x1, x2), Math.min(x3, x4));
long n1 = Math.min(Math.max(y1, y2), Math.max(y3, y4));
long m2 = Math.min(Math.max(x1, x2), Math.max(x3, x4));
long n2 = Math.max(Math.min(y1, y2), Math.min(y3, y4));
long sum = 0;
if (m1 < m2 && n1 > n2)
sum = (m1 - m2) * (n1 - n2);
long res = Math.abs((y2 - y1) * (x2 - x1)) + Math.abs((y3 - y4) * (x3 - x4)) + sum;
System.out.println(res);
}
}
第十四届蓝桥杯JavaB组省赛真题 - 幸运数字
进制转换可以参考如下的十进制，基本一样的，只是把10变成了其他数字，
sum就是各个数位之和。
public static int myUtil(int n) {
int sum = 0;
while(n > 0) {
sum += n % 10;
n /= 10;
}
return sum;
}
注意：
如果写在同一个类里面，main又调用了其他方法，那么除main以外的方法都要加static，因为main由static修饰，静态方法才能调用静态方法。
题解如下：
import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改
public class Main {
public static void main(String[] args) {
int cnt = 0;
int i = 1;
while (true) {
if (cnt != 2023 && i % myUtil(i, 2) == 0 && i % myUtil(i, 8) == 0 && i % myUtil(i, 10) == 0
&& i % myUtil(i, 16) == 0) {
cnt++;
}
if (cnt == 2023)
break;
i++;
}
System.out.println(i);
}
public static int myUtil(int i, int bin) {
int sum = 0;
while (i > 0) {
sum += i % bin;
i /= bin;
}
return sum;
}
}
更多推荐
11
0- 0
已为社区贡献2条内容
所有评论(0)