赞
踩
我是大三第一次参加蓝桥杯,也是最后一次参加了(大四应该没时间了)。我参加的是java b组,总体来说赛程挺顺利的,第一次参赛觉得四个小时有点不够哈哈哈。不过蓝桥杯这个比赛我是带着试一下的心态去参加的。话不多说,接下来就是我的赛后总结,能力有限,仅供参考。
**
- 第一题 分组
**【问题描述】
作为篮球队教练,你需要从以下名单中选出 1 号位至 5 号位各一名球员,
组成球队的首发阵容。
每位球员担任 1 号位至 5 号位时的评分如下表所示。请你计算首发阵容 1
号位至 5 号位的评分之和最大可能是多少?
这道题就是从20个人中挑5个参赛。难度不大,有点小坑,就是道热身题。我的答案是490.-
【问题描述】
一个字符串的非空子串是指字符串中长度至少为 1 的连续的一段字符组成
的串。例如,字符串aaab 有非空子串a, b, aa, ab, aaa, aab, aaab,一共 7 个。
注意在计算时,只算本质不同的串的个数。
请问,字符串0100110001010001 有多少个不同的非空子串?
这道题不是很难,用StringBuffer的subString方法截取,然后再放进HashSet中去重。HashSet的长度-1就是答案了。(至于为什么要减一,我也不太清楚,我测试了题目的例子和自己写的例子才发现减一才是正确答案,有大神能告诉我为什么减一吗)
代码如下:
import java.util.HashSet; public class _02子串 { public static void main(String[] args) { StringBuffer s = new StringBuffer("0100110001010001"); HashSet<String> set = new HashSet<String>(); // 双重循环,子串的头是s的第i个,尾是s的第j个 for (int i = 0; i <= s.length(); i++) { for (int j = i; j <= s.length(); j++) { String str = s.substring(i, j); set.add(str); } } System.out.println(set.size() - 1); } }
我最后算的答案是 100
这道题给我的第一印象是大数BigInteger,因为这道题类似于2018年java B组 复数幂的那道题,我做过所以印象特别深刻。这个数列类似于斐波拉契数列,但是如果用整型或者长整型数值肯定会爆。所以我一开始用大数写的,但是运行了十来分钟都没有出答案我就改个思路了。
第二个思路是:既然题目只要求第20190324项的最后4位数字,所以我就把每一项都求余10000,。因为加法是向前进位的,所以后取余对后四位没影响。
代码如下:
public class _03数列求值 {
public static void main(String[] args) {
int[] a = new int[20190324];
a[0] = 1;
a[1] = 1;
a[2] = 1;
for (int i = 3; i < a.length; i++) {
a[i] = (a[i - 1] + a[i - 2] + a[i - 3]) % 10000;
}
System.out.println(a[a.length-1]);
}
}
我的答案是 4659
**
这道题是思路很简单,暴力解!写三个for循环,然后再写一个check方法,检查正整数里是否包含2或者4,把解出来的结果除以6就是正确答案,为什么要除以6呢?因为暴力解出来的答案是所有解的数量。题目中说了“交换 3 个整数的顺序被视为同一种方法”,三个整数交换顺序,那就成了三个数字的全排列问题了,全排列类型有6中,所以结果要除以6。
但是后来我发现事情不简单了。三个for循环,时间复杂度是201920192019,一个程序算出来得十来二十分钟。所以我改成了两个for循环。优化后,答案两秒钟就出来了!
代码如下:
public class _04数的分解 { static int ans = 0; public static void main(String[] args) { for (int a = 1; a < 2019; a++) { for (int b = 1; b < 2019; b++) { int c = 2019 - a - b; if (c > 0 && check(a) && check(b) && check(c)) { ans++; } } } System.out.println(ans/6); } private static boolean check(int A) { // 把要检验的数字转化成字符串 String s = A + ""; for (int i = 0; i < s.length(); i++) { // 逐个字符检查是否含有2或4 if (s.charAt(i) == '2' || s.charAt(i) == '4') return false; } return true; } }
我最后算出来的答案是 40935
接下来难度要逐步增加了!请做好心理准备!
**
实话实说,当我看到这道题的时候我开心得像个两百斤的小孩,练了那么多蓝桥杯题目一看这道题就是用深搜算法解题的,而我深搜是练习得最多了。但是到后来我发现我开心得太早了。。。。我当时的思路是这样的:深搜加回溯,直到终点的时候就记录最小步数和路径。
话不多说,先上代码:
public class _05迷宫 { static int ans = 0; static String res = ""; static int[][] mg; static int max; public static void main(String[] args) { String[] s = { "01010101001011001001010110010110100100001000101010", "00001000100000101010010000100000001001100110100101", "01111011010010001000001101001011100011000000010000", "01000000001010100011010000101000001010101011001011", "00011111000000101000010010100010100000101100000000", "11001000110101000010101100011010011010101011110111", "00011011010101001001001010000001000101001110000000", "10100000101000100110101010111110011000010000111010", "00111000001010100001100010000001000101001100001001", "11000110100001110010001001010101010101010001101000", "00010000100100000101001010101110100010101010000101", "11100100101001001000010000010101010100100100010100", "00000010000000101011001111010001100000101010100011", "10101010011100001000011000010110011110110100001000", "10101010100001101010100101000010100000111011101001", "10000000101100010000101100101101001011100000000100", "10101001000000010100100001000100000100011110101001", "00101001010101101001010100011010101101110000110101", "11001010000100001100000010100101000001000111000010", "00001000110000110101101000000100101001001000011101", "10100101000101000000001110110010110101101010100001", "00101000010000110101010000100010001001000100010101", "10100001000110010001000010101001010101011111010010", "00000100101000000110010100101001000001000000000010", "11010000001001110111001001000011101001011011101000", "00000110100010001000100000001000011101000000110011", "10101000101000100010001111100010101001010000001000", "10000010100101001010110000000100101010001011101000", "00111100001000010000000110111000000001000000001011", "10000001100111010111010001000110111010101101111000" }; mg = new int[30][50]; // 转换为整型数组(个人比较喜欢整型数组) for (int i = 0; i < 30; i++) { for (int j = 0; j < 50; j++) { mg[i][j] = s[i].charAt(j); } } dfs(0, 0, "", 0); System.out.println(res); } /** * * @param x x轴坐标 * @param y y轴坐标 * @param s 路径方向 * @param ans 总步数 */ private static void dfs(int x, int y, String s, int ans) { // 越界返回 if (x > 29 || x < 0 || y > 49 || y < 0) return; // 遇到障碍返回 if (mg[x][y] == 1) return; //出口 if(x == 29 && y == 49) { if(max > ans) { //记录最小值 max = ans; s = res; } return ; } // 向右走 dfs(x, y + 1, s + "R", ans++); ans--;// 回溯 // 向下走 dfs(x + 1, y, s + "D", ans++); ans--;// 回溯 // 向上走 dfs(x - 1, y, s + "U", ans++); ans--;// 回溯 // 向左走 dfs(x, y - 1, s + "L", ans++); ans--;// 回溯 } }
最后控制台爆栈了,请各位大神能帮我看看是哪里出的问题吗?
**
这道题的思路和第三题的差不多,枚举加检查。枚举1-n个数,检查是否符合要求,符合要求的就存储在数组中,最后相加。
我的代码:
import java.util.Scanner;
public class _06特别数的和 {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
int n = input.nextInt();
// 输入结束
input.close();
// 存储结果的数组
int[] res = new int[n];
// 连加结果
int sum = 0;
// 数组指针
int p = 0;
for (int i = 1; i <= n; i++) {
if (check(i)) {
res[p++] = i;
}
}
// 连加
for (int i = 0; i < res.length; i++) {
sum += res[i];
}
System.out.println(sum);
}
private static boolean check(int s) {
String S = s + "";
for (int i = 0; i < S.length(); i++) {
if (S.charAt(i) == '2' || S.charAt(i) == '0' || S.charAt(i) == '1' || S.charAt(i) == '9')
return true;
}
return false;
}
}
这段代码应该不用继续优化了,我测试10000,很快就出答案了。
**
这道题难度就突然上升, 和我一起参赛的朋友卡在这道题,浪费了很多时间。
我的思路是用一个二维数组DD[T][N]存储某时候的订单信息,DD[t][n]表示在t时刻第n家外卖店的订单数,如果订单数为0,且该时刻该商家的的优先级为0,则跳过,如果不为0,则优先级减1;如果订单数不为0,则该商家的优先级增加2*DD[t][n]。时刻数组遍历完后,检查多少家外卖店的优先级达到5。
代码如下:
import java.util.Scanner; public class _07外卖店优先级 { public static void main(String[] args) { Scanner input = new Scanner(System.in); int N = input.nextInt(); int M = input.nextInt(); int T = input.nextInt(); int[][] DD = new int[T + 1][N + 1]; for (int i = 0; i < M; i++) { int t = input.nextInt(); int n = input.nextInt(); DD[t][n]++; } input.close(); // 商家优先级数组 int[] yx = new int[N + 2]; for (int i = 1; i < T + 1; i++) { for (int j = 1; j < N + 1; j++) { if (DD[i][j] == 0) { if (yx[j] == 0) continue; if (yx[j] > 0) yx[j]--; } else if (DD[i][j] > 0) { yx[j] = yx[j] + 2 * DD[i][j]; } } } int sum = 0; for (int i = 0; i < yx.length; i++) { if (yx[i] >= 5) sum++; } System.out.println(sum); } }
**
这道题当时做出来了,但是没有写测试方法。估计也是只有几分。总体的思路还是不太懂。
**
这道题比第八题简单,排序,然后大数相加,小数先减。
import java.util.Arrays; import java.util.Scanner; public class _09后缀表达式 { public static void main(String[] args) { Scanner input = new Scanner(System.in); int add = input.nextInt(); int sub = input.nextInt(); int[] arr = new int[add + sub + 1]; for (int i = 0; i < arr.length; i++) { arr[i] = input.nextInt(); } input.close(); // Arrays的排序算法很好用,不需要自己再写一个排序算法。方法返回的是一个升序序列 Arrays.sort(arr); for (int i = 0; i < arr.length / 2; i++) { int t = arr[i]; arr[i] = arr[arr.length - 1 - i]; arr[arr.length - 1 - i] = t; } int sum = 0; for (int i = 0; i < arr.length; i++) { if (i <= add) { sum += arr[i]; } else { sum -= arr[i]; } } System.out.println(sum); } }
**
这道题题目比较长,而已又是最后一道题。但是完全没有时间去做,所以就空着了。
我来做个总结吧,总得来说,2019的试题比2018的简单很多,至少我和我朋友都是这么认为的。希望这次能那个好的名次吧。做得不好,仅供参考。谢谢各位的耐心阅读。
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。