【蓝桥日记②】2018第九届省赛（软件类）JavaA组★答案解析

news/2025/2/13 6:08:42/

【蓝桥日记②】2018第九届省赛（软件类）JavaA组🏅答案解析

文章目录

    • 【蓝桥日记②】2018第九届省赛（软件类）JavaA组🏅答案解析
      • 1、分数
      • 2、星期一
      • 3、复数幂
      • 4、方格计数
      • 5、打印图形
      • 6、航班时间
      • 7、三体攻击
      • 8、全球变暖
      • 9、倍数问题
      • 10、付账问题

题目链接：第九届蓝桥杯大赛个人赛省赛（软件类）Java大学A组

官网题库中搜索相应题目

1、分数

考点：等比数列求和

  • 等差数列求和公式
    Sn=n(a1+an)2=na1+n(n−1)d2,n∈N∗S_n = \frac{n(a_1+a_n)}{2}=na_1+\frac{n(n-1)d}{2},n ∈ N^* Sn​=2n(a1​+an​)​=na1​+2n(n−1)d​,n∈N∗

  • 等比数列求和公式
    an=a1qn−1Sn=1−qn1−q,q≠1a_n=a_1q^{n-1} \\ S_n=\frac{1-q^n}{1-q}, q\neq1 an​=a1​qn−1Sn​=1−q1−qn​,q=1

方法一：Java大整数运算

package nineSession;
import java.math.BigInteger;/*** 2017第九届  1、分数 ***/
public class test1 {public static void main(String[] args) {// 等比数列通项和 S = a1(1 - q^n) / (1 - q)// 将a1 = 1, q = 1 / 2, n = 20 代入化解BigInteger e = BigInteger.TWO;  // BigInteger.valueOf(2)BigInteger a = e.pow(20).subtract(BigInteger.ONE);BigInteger b = e.pow(19);BigInteger g = a.gcd(b);a.divide(g);b.divide(g);System.out.println(a + "/" + b);}
}

方法二：位运算

package nineSession;/*** 2017第九届  1、分数 ***/
public class test1_3 {private static long gcd(long a, long b) {return b == 0 ? a : gcd(b, a % b);}public static void main(String[] args) {long a = (1 << 20) - 1;long b = (1 << 19);long g = gcd(a, b);System.out.println(a / g + "/" + b / g);}
}

方法三：快速幂+最大公约数

package nineSession;/*** 2017第九届  1、分数 ***/
public class test1_2 {private static long gcd(long a, long b) {return b == 0 ? a : gcd(b, a % b);}private static long fastPow(long e, int q) {long res = 1;while (q > 0) {if ((q & 1) == 1) res = res * e;e = e * e;q >>= 1;}return res;}public static void main(String[] args) {long a = fastPow(2, 20) - 1;long b = fastPow(2, 19);long g = gcd(a, b);a /= g;b /= g;System.out.println(a + "/" + b);}
}

答案：1048575/524288

2、星期一

package nineSession;/*** 2017第九届  2、星期一 ***/
public class test2 {private static boolean isLeap(int y) {return y % 400 == 0 || (y % 4 == 0 && y % 100 != 0);}public static void main(String[] args) {int t = -6; // 2000-12-31 为星期日for (int i = 1901; i <= 2000; i++) {t += isLeap(i) ? 366 : 365;}int res = 0;for (int i = t; i > 0; i -= 7) res += 1;System.out.println(res);}
}

答案：5217

3、复数幂

考点：BigInteger

package nineSession;import java.math.BigInteger;/*** 2017第九届  3、复数幂 ***/
public class test3 {public static void main(String[] args) {// (a + bi)(x + yi) = ax - by + (ay + bx)iBigInteger a = BigInteger.valueOf(2);BigInteger b = BigInteger.valueOf(3);BigInteger x = BigInteger.valueOf(2);BigInteger y = BigInteger.valueOf(3);for (int i = 1; i < 123456; i++) {BigInteger a1 = a.multiply(x).subtract(b.multiply(y));BigInteger b1 = a.multiply(y).add(b.multiply(x));a = a1;b = b1;}String sign = b.compareTo(BigInteger.ZERO) > 0 ? "+" : "";System.out.println(a + sign + b + "i");}
}

答案：太长了~

4、方格计数

考点：计算点到圆心距离是否小于半径

package nineSession;/*** 2017第九届  4、方格计数 ***/
public class test4 {public static void main(String[] args) {long res = 0, range = 50000 * 50000L;for (int i = 1; i < 50000; i++) {for (int j = 1; j < 50000; j++) {if ((long)i * i + (long)j * j <= range) res += 4;}}System.out.println(res);}
}

答案：7853781044

5、打印图形

考点：递归

package nineSession;/*** 2017第九届  5、打印图形 ***/
public class test5 {static void show(byte[][] buf) {for (int i = 0; i < buf.length; i++) {for (int j = 0; j < buf[i].length; j++) {System.out.print(buf[i][j] == 0 ? ' ' : 'o');}System.out.println();}}static void draw(byte[][] buf, int x, int y, int size) {if (size == 1) {buf[y][x] = 1;return;}int n = size / 3;draw(buf, x, y, n);draw(buf, x - n, y, n);draw(buf, x + n, y, n);draw(buf, x, y - n, n);draw(buf, x, y + n, n);}public static void main(String[] args) {final int N = 3;int t = 1;for (int i = 0; i < N; i++) t *= 3;byte[][] buf = new byte[t][t];draw(buf, t / 2, t / 2, t);show(buf);}
}

答案：size / 3

6、航班时间

考点：时间函数+字符串处理

package nineSession;
import java.text.ParseException;
import java.text.SimpleDateFormat;
import java.util.Date;
import java.util.Scanner;/*** 2017第九届  6.航班时间 ***/
public class test6 {public static void main(String[] args) throws ParseException {Scanner sc = new Scanner(System.in);int T = sc.nextInt();sc.nextLine();String[] lines = new String[T * 2];for (int i = 0; i < T * 2; i++) {lines[i] = sc.nextLine();}sc.close();for (int i = 0; i < T; i++) {long time1 = getTime(lines[i * 2]);long time2 = getTime(lines[i * 2 + 1]);long t = (time1 + time2) / 2;System.out.printf("%02d:%02d:%02d\n", t / 3600, t / 60 % 60, t % 60);}}private static long getTime(String line) throws ParseException {String[] split = line.split(" ");SimpleDateFormat format = new SimpleDateFormat("HH:mm:ss");Date t1 = format.parse(split[0]);Date t2 = format.parse(split[1]);long d = 0l;if (split.length == 3) {d = (long)(split[2].charAt(2) - '0');}return d * 24 * 3600 + t2.getTime() / 1000 - t1.getTime() / 1000;}
}

7、三体攻击

方法一：暴力模拟（超时 3/4）

package nineSession;
import java.util.Scanner;/*** 2017第九届  7.三体攻击 ***/
public class test7 {static int A, B, C, m;static int[][][] warships;static int[][] attacks;private static int startWar() {for (int t = 0; t < m; t++) {for (int i = attacks[t][0]; i <= attacks[t][1]; i++) {for (int j = attacks[t][2]; j <= attacks[t][3]; j++) {for (int k = attacks[t][4]; k <= attacks[t][5]; k++) {warships[i - 1][j - 1][k - 1] -= attacks[t][6];if (warships[i - 1][j - 1][k - 1] < 0) return t + 1;}}}}return -1;}public static void main(String[] args) {Scanner sc = new Scanner(System.in);A = sc.nextInt();B = sc.nextInt();C = sc.nextInt();m = sc.nextInt();warships = new int[A][B][C];for (int i = 0; i < A; i++) {for (int j = 0; j < B; j++) {for (int k = 0; k < C; k++) {warships[i][j][k] = sc.nextInt();}}}attacks = new int[m][7];for (int i = 0; i < m; i++) {for (int j = 0; j < 7; j++) {attacks[i][j] = sc.nextInt();}}int times = startWar();System.out.println(times);}
}

方法二：三维差分+二分

总结一下一维至三维的差分

  • 一维 x1, x2
    dis[x1]+=vdis[x2+1]−=vdis[x1]+= v \\ dis[x2 + 1] -= v dis[x1]+=vdis[x2+1]−=v

  • 二维(x1, y1)，（x2,y2）
    dis[x1][y1]+=vdis[x2+1][y1]−=vdis[x1][y2+1]−=vdis[x2+1][y2+1]+=vdis[x1][y1] +=v \\ dis[x2 + 1][y1] -= v\\ dis[x1][y2 + 1] -= v\\ dis[x2 + 1][y2+1] += v dis[x1][y1]+=vdis[x2+1][y1]−=vdis[x1][y2+1]−=vdis[x2+1][y2+1]+=v

  • 三维(x1,y1,z1)，(x2,y2,z2)
    dis[x1][y1][z1]+=vdis[x2+1][y1][z1]−=vdis[x1][y2+1][z1]−=vdis[x1][y1][z2+1]−=vdis[x2+1][y2+1][z1]+=vdis[x2+1][y1][z2+1]+=vdis[x1][y2+1][z2+1]+=vdis[x2+1][y2+1][z2+1]−=vdis[x1][y1][z1] += v \\ dis[x2 + 1][y1][z1] -= v \\ dis[x1][y2 + 1][z1] -= v \\ dis[x1][y1][z2 + 1] -= v \\ dis[x2 + 1][y2 + 1][z1] += v \\ dis[x2 + 1][y1][z2 + 1] += v \\ dis[x1][y2 + 1][z2 + 1] += v \\ dis[x2 + 1][y2 + 1][z2 + 1] -= v dis[x1][y1][z1]+=vdis[x2+1][y1][z1]−=vdis[x1][y2+1][z1]−=vdis[x1][y1][z2+1]−=vdis[x2+1][y2+1][z1]+=vdis[x2+1][y1][z2+1]+=vdis[x1][y2+1][z2+1]+=vdis[x2+1][y2+1][z2+1]−=v

不知道错在哪儿了，真的找不出了

package nineSession;
import java.util.Scanner;/*** 2017第九届  7.三体攻击 ***/
public class test7_2 {static int A, B, C, m;static int[][][] warships;static int[][] attacks;static int[][][] dis; // 差分数组static int[][][] sum; // 辅助求和数组private static int binarySearch() {int le = 0, ri = m - 1, lastMid = -1;int times = 0;while (le <= ri) {int mid = le + (ri - le) / 2;// 上一次攻击在mid左边，则在 lastMid + 1 处继续攻击// 上一次攻击在mid右边，则撤销 mid + 1 ~ lastmid 间的攻击if (lastMid < mid) {for (int i = lastMid + 1; i <= mid; i++) {int[] cur = attacks[i];op(cur[0], cur[2], cur[4], cur[1], cur[3], cur[5], cur[6]);}}if (lastMid > mid) {for (int i = mid + 1; i <= lastMid; i++) {int[] cur = attacks[i];op(cur[0], cur[2], cur[4], cur[1], cur[3], cur[5], -cur[6]);}}if (check()) {times = mid;ri = mid - 1;} else {le = mid + 1;}lastMid = mid;}return times + 1;}private static boolean check() {// copy warships 数组至 sum 数组中for (int i = 0; i <= A; i++) {for (int j = 0; j <= B; j++) {for (int k = 0; k <= C; k++) sum[i][j][k] = dis[i][j][k];}}for (int i = 0; i < A; i++) {for (int j = 0; j < B; j++) {for (int k = 0; k < C; k++) {sum[i + 1][j + 1][k + 1] += sum[i][j][k];sum[i + 1][j + 1][k + 1] -= sum[i + 1][j][k];sum[i + 1][j + 1][k + 1] -= sum[i][j + 1][k];sum[i + 1][j + 1][k + 1] -= sum[i][j][k + 1];sum[i + 1][j + 1][k + 1] += sum[i + 1][j + 1][k];sum[i + 1][j + 1][k + 1] += sum[i + 1][j][k + 1];sum[i + 1][j + 1][k + 1] += sum[i][j + 1][k + 1];if (sum[i + 1][j + 1][k + 1] > warships[i][j][k]) return true;}}}return false;}private static void op(int x1, int y1, int z1, int x2, int y2, int z2, int v) {dis[x1][y1][z1] += v;dis[x2 + 1][y1][z1] -= v;dis[x1][y2 + 1][z1] -= v;dis[x1][y1][z2 + 1] -= v;dis[x2 + 1][y2 + 1][z1] += v;dis[x2 + 1][y1][z2 + 1] += v;dis[x1][y2 + 1][z2 + 1] += v;dis[x2 + 1][y2 + 1][z2 + 1] -= v;}public static void main(String[] args) {Scanner sc = new Scanner(System.in);A = sc.nextInt();B = sc.nextInt();C = sc.nextInt();m = sc.nextInt();warships = new int[A][B][C];dis = new int[A + 1][B + 1][C + 1];sum = new int[A + 1][B + 1][C + 1];for (int i = 0; i < A; i++) {for (int j = 0; j < B; j++) {for (int k = 0; k < C; k++) {warships[i][j][k] = sc.nextInt();;}}}attacks = new int[m][7];for (int i = 0; i < m; i++) {for (int j = 0; j < 7; j++) {attacks[i][j] = sc.nextInt() - 1;}attacks[i][6] += 1;}sc.close();int times = binarySearch();System.out.println(times);}
}

8、全球变暖

考点：DFS

package nineSession;
import java.util.Arrays;
import java.util.Scanner;/*** 2017第九届  8.全球变暖 ***/
public class test8 {static int n;static char[][] grid;static boolean hasCover;static int[] dirs = new int[]{-1, 0, 1, 0, -1};private static void countIsland(int x, int y, boolean[][] mark) {mark[x][y] = true;if (grid[x - 1][y] == '#' && grid[x + 1][y] == '#' && grid[x][y - 1] == '#' && grid[x][y + 1] == '#') {hasCover = false;}for (int i = 0; i < 4; i++) {int x1 = x + dirs[i], y1 = y + dirs[i + 1];if (!mark[x1][y1] && grid[x1][y1] == '#'){countIsland(x1, y1, mark);}}}public static void main(String[] args) {Scanner sc = new Scanner(System.in);n = sc.nextInt();grid = new char[n][n];for (int i = 0; i < n; i++) {grid[i] = sc.next().toCharArray();}sc.close();int res = 0;boolean[][] mark = new boolean[n][n];for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {if (!mark[i][j] && grid[i][j] == '#') {hasCover = true;countIsland(i, j, mark);if (hasCover) res += 1;}}}System.out.println(res);}
}

需要考虑的点还是很多啊，哎~

9、倍数问题

考点：

方法一：暴力解法(5/10)

package nineSession;
import java.util.Scanner;/*** 2017第九届  9.倍数问题 ***/
/*** 暴力解法 ***/
public class test9 {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt(), K = sc.nextInt();int[] nums = new int[n];for (int i = 0; i < n; i++) nums[i] = sc.nextInt();sc.close();int res = 0;for (int i = 0; i < n - 2; i++) {for (int j = i + 1; j < n - 1; j++) {for (int k = j + 1; k < n; k++) {if ((nums[i] + nums[j] + nums[k]) % K == 0) {res = Math.max(res, nums[i] + nums[j] + nums[k]);}}}}System.out.println(res);}
}

方法二：字典保存余数(6/10)

package nineSession;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.Scanner;/*** 2017第九届  9.倍数问题 ***/
/*** 对余数利用字典进行预处理 ***/
public class test9_2 {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt(), K = sc.nextInt();int[] nums = new int[n];for (int i = 0; i < n; i++) nums[i] = sc.nextInt();sc.close();HashMap<Integer, ArrayList<Integer>> map = new HashMap();for (int num : nums) {int r = num % K;if (!map.containsKey(r)) map.put(r, new ArrayList());map.get(r).add(num);}int res = 0;for (int i = 0; i < n - 1; i++) {for (int j = i + 1; j < n; j++) {int r = (nums[i] + nums[j]) % K;if (!map.containsKey(K - r)) continue;ArrayList<Integer> list = map.get(K - r);Collections.sort(list, (a, b) -> b - a);for (int k = 0; k < list.size(); k++) {if (k >= 2 || list.get(k) != nums[i] && list.get(k) != nums[j]) {res = Math.max(res, nums[i] + nums[j] + list.get(k));break;}}}}System.out.println(res);}
}

方法三：哈希拉链法

package nineSession;
import java.util.Scanner;/*** 2017第九届  9.倍数问题 ***/
/*** 对余数利用字典进行预处理2 ***/
public class test9_3 {static int[][] group;public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt(), K = sc.nextInt();group = new int[K][3];for (int i = 0; i < n; i++) {int x = sc.nextInt();int r = x % K;if (x > group[r][0]) {group[r][2] = group[r][1];group[r][1] = group[r][0];group[r][0] = x;} else if (x > group[r][1]) {group[r][2] = group[r][1];group[r][1] = x;} else {group[r][2] = Math.max(group[r][2], x);}}sc.close();int res = 0;for (int x = 0; x < K; x++) {for (int y = x; y < K; y++) {int z = (K + K - x - y) % K;// 分情况讨论， x, y, z 的分组情况// 首先选出组中最大的数int v1 = group[x][0], v2 = 0, v3 = 0;if (y == x) {v2 = group[x][1];if (z == y) {v3 = group[x][2];} else {v3 = group[z][0];}} else {v2 = group[y][0];if (z == x) {v3 = group[x][1];} else if(z == y){v3 = group[y][1];} else {v3 = group[z][0];}}res = Math.max(res, v1 + v2 + v3);}}System.out.println(res);}
}

10、付账问题

贪心法：（8/10）超时2个

package nineSession;import java.util.Arrays;
import java.util.Scanner;/*** 2017第九届  10.付账问题 ***/
public class test10 {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();double S = sc.nextDouble();long[] nums = new long[n];for (int i = 0; i < n; i++) {nums[i] = sc.nextLong();}sc.close();Arrays.sort(nums);double res = 0;double avg = (double)S / n;for (int i = 0; i < n; i++) {// 钱的数额 * 分摊人数 < 总额, 当前数额小于均值的全部贡献出来if (nums[i] * (n - i) < S) {res += Math.pow(avg - nums[i], 2);S -= nums[i];} else {res += Math.pow((double)S / (n - i) - avg, 2) * (n - i);break;}}res = Math.sqrt(res / n);System.out.printf("%.4f", res);}
}

参考资料

【蓝桥杯JavaA组】2013-2018年试题讲解（附含C语言版）

二维差分和三维差分

元宵佳节，愿我们今后万事圆满！


http://www.ppmy.cn/news/22295.html

相关文章

【自动驾驶100问】第一问到第三问

【自动驾驶100问】第一问到第三问

配套视频&#xff1a; 自动驾驶100问第三问 1、四元数在表示空间旋转时的优势是什么&#xff1f; &#xff08;1&#xff09;四元数解决了其他3维空间旋转算法会遇到的恼人的问题&#xff0c;比如使用欧拉角来表示旋转操作时会遇到的万向节锁问题(Gimbal lock)&#xff1b; …
阅读更多...
第九章（13）：STL之常用排序算法

第九章（13）：STL之常用排序算法

文章目录前情回顾常用排序算法sortrandom_shufflemergereverse下一座石碑&#x1f389;welcome&#x1f389; ✒️博主介绍&#xff1a;一名大一的智能制造专业学生&#xff0c;在学习C/C的路上会越走越远&#xff0c;后面不定期更新有关C/C语法&#xff0c;数据结构&#xff0…
阅读更多...
OpenCV 图像形态学处理

OpenCV 图像形态学处理

本文是OpenCV图像视觉入门之路的第11篇文章&#xff0c;本文详细的在图像形态学进行了图像处理&#xff0c;例如&#xff1a;腐蚀操作、膨胀操作、开闭运算、梯度运算、Top Hat Black Hat运算等操作。 OpenCV 图像形态学处理目录 1 腐蚀操作 2 膨胀操作 3 开闭运算 4 梯度运…
阅读更多...
【博客608】源ip是本地网卡ip的流量都发往lo网卡的原因剖析

【博客608】源ip是本地网卡ip的流量都发往lo网卡的原因剖析

源ip是本地网卡ip的流量都发往lo网卡的原因剖析 场景&#xff1a;本地ip之间通信&#xff0c;流量都会发现lo&#xff0c;不会发往本地ip所在device example&#xff1a; ubuntu10.200.60.4:~$ ip a 1: lo: <LOOPBACK,UP,LOWER_UP> mtu 65536 qdisc noqueue state UNK…
阅读更多...
CQF项目课程学习介绍（三）—— 高级选修课

CQF项目课程学习介绍（三）—— 高级选修课

✏️写作&#xff1a;个人博客&#xff0c;InfoQ&#xff0c;掘金&#xff0c;知乎&#xff0c;CSDN &#x1f4e7;公众号&#xff1a;进击的Matrix &#x1f6ab;特别声明&#xff1a;原创不易&#xff0c;未经授权不得转载或抄袭&#xff0c;如需转载可联系小编授权。 概述 …
阅读更多...
【算法基础】高精度减法

【算法基础】高精度减法

&#x1f466;个人主页&#xff1a;Weraphael ✍&#x1f3fb;作者简介&#xff1a;目前是C语言学习者 ✈️专栏&#xff1a;【C/C】算法 &#x1f40b; 希望大家多多支持&#xff0c;咱一起进步&#xff01;&#x1f601; 如果文章对你有帮助的话 欢迎 评论&#x1f4ac; 点赞…
阅读更多...
ESP-IDF:模板函数测试

ESP-IDF:模板函数测试

模板函数测试 template //告诉编译器下面使用函数模板T,仅仅对下面这个函数有效 void swap22(T &a, T &b) { T temp a; a b; b temp; } void test22() { cout<<“--------模板函数测试--------”<<endl; int a 2; int b 9; cout<<“before sw…
阅读更多...
索命一问：一个SQL ，怎么分析加了哪些锁？

索命一问：一个SQL ，怎么分析加了哪些锁？

背景说明&#xff1a; 美团问数据库应该是非常多的&#xff0c;尤其喜欢考手写 SQL 然后问你这个 SQL 语句上面加了哪些锁&#xff0c; 你会发现其他厂面试基本很少会这样考&#xff0c;所以很多小伙伴遇到这种问题的时候都是一脸懵逼&#xff0c; 可以说是“夺命一问” 此…
阅读更多...
最新文章

Copyright @ 2022~2023