2021年第十二届蓝桥杯大赛软件赛省赛第二场JavaB组C++B组全部题目以及题目解析

2024-02-01 20:38
文章标签 java c++ 题目 软件 蓝桥 解析 2021 全部 大赛 第十二届 第二场 赛省赛

本文主要是介绍2021年第十二届蓝桥杯大赛软件赛省赛第二场JavaB组C++B组全部题目以及题目解析，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

本人参加的就是第二场比赛，感觉比第一场的题目简单一些，在这里记录一下。
喜欢本文的小伙伴，别忘了点赞、收藏一波哦~
如果有什么问题，欢迎在评论区讨论交流~
好像C++B组的题目和JavaB组的题目是一样，所以C的同学也可以看看说不定有些启发~

在这里插入图片描述

【分析】
签到题，复制粘贴运行，一气呵成。

答案：1

public class A_求余 {public static void main(String[] args) {System.out.println(2021%20);}
}

在这里插入图片描述

【分析】
模拟一下计算过程，但如果直接循环计算，最后结果一定会是一个超级大的数字，容易溢出，而且时间也会比较久。
观察题目只需要我们输出最后5位数，假设当前数字是1234567，乘上89，打个草稿手动计算时，你会发现百万位的1和十万位的2对结果的最后5位数，没有任何影响，所以我们对每次乘积结果模上100000即可。

答案：59375

public class B_双阶乘 {public static void main(String[] args) {int n = 2021;int ans = 1;for (int i = n; i > 0; i -= 2) {ans *= i;ans %= 100000;}System.out.println(ans);}
}

在这里插入图片描述
【分析】
没什么好说的，两重循环，乘积小于等于2021即可

答案：15698

public class C_格点 {public static void main(String[] args) {int n = 2021;int ans = 0;for (int i = 1; i <= n; i ++) {for (int j = 1; j <= n; j ++) {if (i * j <= n) ans ++;}}System.out.println(ans);}
}

在这里插入图片描述
【分析】
n是2021时，暴力思想五重循环肯定过不了，优化后的四重循环加剪枝也很难运行出来。
我这里用的是哈希表预处理，空间换时间。
假设a + b + c + d + e == 2021。
先预处理a + b的所有组合情况，存放入哈希表中。哈希表中k为数值，v为组合个数。
再两重循环遍历哈希表，如果两个数值相加小于2021，则答案加上组合数相乘。

答案：691677274345

import java.util.HashMap;
import java.util.Map;public class D_整数分解 {public static void main(String[] args) {int n = 2021;// k为数值，v为组合个数Map<Integer, Integer> h = new HashMap<Integer, Integer>();for (int i = 1; i <= n; i ++) {for (int j = 1; j <= n; j ++) {h.put(i + j, h.getOrDefault(i + j, 0) + 1);}}long ans = 0;for (Map.Entry<Integer, Integer> m1 : h.entrySet()) {int k1 = m1.getKey();int v1 = m1.getValue();for (Map.Entry<Integer, Integer> m2 : h.entrySet()) {int k2 = m2.getKey();int v2 = m2.getValue();if (k1 + k2 < n) ans += v1 * v2;}}System.out.println(ans);}
}

在这里插入图片描述
【分析】
这题没什么好说的，先按照题目处理两两个点的距离，再用Kruskal算法求最小生成树。
（PS:这题不算难，但如果你不会求最小生成树就比较难搞了。。。）

答案：4046

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;public class E_城邦 {static int n = 2021;static int[] p = new int[n + 1];public static void main(String[] args) {	List<Line> list = new ArrayList<Line>();for (int i = 1; i <= n; i ++) {for (int j = i + 1; j <= n; j ++) {int a = i;int b = j;int w = 0;while (a != 0 || b != 0) {if (a % 10 != b % 10) {w += a % 10;w += b % 10;}a /= 10;b /= 10;}list.add(new Line(i, j, w));}}Collections.sort(list);for (int i = 1; i <= n; i ++) p[i] = i;long ans = 0;for (Line line : list) {int u = line.u;int v = line.v;int w = line.w;if (find(u) != find(v)) {p[find(u)] = find(v);ans += w;}}System.out.println(ans);}public static int find(int x) {if (x != p[x]) p[x] = find(p[x]);return p[x];}
}class Line implements Comparable<Line>{int u;int v;int w;public Line(int u, int v, int w) {super();this.u = u;this.v = v;this.w = w;}@Overridepublic int compareTo(Line o) {return Integer.compare(this.w, o.w);}@Overridepublic String toString() {return "Line [u=" + u + ", v=" + v + ", w=" + w + "]";}}

在这里插入图片描述
【分析】
模拟一下，取出千位百位十位个位，判断一下即可~

import java.util.Scanner;public class F_特殊年份 {static Scanner in = new Scanner(System.in);static int n;public static void main(String[] args) {int ans = 0;for (int i = 0; i < 5; i ++) {n = in.nextInt();int q = n / 1000;int b = n / 100 % 10;int s = n / 10 % 10;int g = n % 10;if (q == s && g - b == 1) ans ++;}System.out.println(ans);}
}

在这里插入图片描述
【分析】
数据范围只有10000，也模拟运算一下就行了，我这里用两边乘2代替了除2，因为java里奇数除以2比较蛋疼，例如9/2==4，个人感觉容易误判。。。

import java.util.Scanner;public class G_小平方 {static Scanner in = new Scanner(System.in);static int n ;public static void main(String[] args) {n = in.nextInt();int ans = 0;for (int i = 1; i < n; i ++) {if (i * i % n * 2 < n) ans ++;}System.out.println(ans);}
}

在这里插入图片描述
在这里插入图片描述
【分析】
约定：这里用sqrt表示代表根号（根号符号实在不懂怎么打出来QAQ）
简化题目：给定一个n，让你求最小的一个x，使得sqrt(n*x)计算结果是一个整数。
主要思想：分解n的质因数，只有有两个相同的质因数就可以开出一个整数，也就相当于消掉了。
举个例子：n等于96时，sqrt(96) 等价于 sqrt(2 * 2 * 2 * 2 * 2 * 3），里面有5个2，所以可以消掉4个2，只剩sqrt(2 * 3)，答案就是6了。验算一下96×6等于576，开根号刚好是整数24。
时间复杂度：整体时间复杂度O(sqrt(n))，而n<=10^12，所以完全足够。

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;public class H_完全平方数 {static Scanner in = new Scanner(System.in);static long n;public static void main(String[] args) {n = in.nextLong();Map<Long, Integer> h = new HashMap<Long, Integer>();for (long i = 2; i <= n / i; i ++) {while (n % i == 0) {h.put(i, h.getOrDefault(i, 0) + 1);n /= i;}}if (n > 1) h.put(n, h.getOrDefault(n, 0) + 1);long ans = 1;for (Map.Entry<Long, Integer> m : h.entrySet()) {long k = m.getKey();int v = m.getValue();if (v % 2 == 1) ans *= k;}System.out.println(ans);}
}

在这里插入图片描述
在这里插入图片描述
【分析】
（哭死，这题字母有点多，再加上有点紧张，有点乱了，还以为很难，都没怎么考虑做，结果距离比赛还有5分钟才突然想到解法，敲了两三分钟，实在没时间了就放弃了。。。呜呜呜）
思路：用一个优先队列保存正在运行的任务，每次输入一个任务分情况判断就行了。
时间复杂度：遍历的复杂度是n，优先队列的复杂度是logn，所以整体时间复杂度O(nlogn)，n最多2*10^5，完全足够。
（由于输入的数据量非常大，快到1百万了，Java建议使用快速输入输出，不然OJ上可能过不了~~）

import java.io.BufferedReader;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.PriorityQueue;
import java.util.StringTokenizer;public class I_负载均衡 {static In in = new In(System.in);static PrintWriter out = new PrintWriter(System.out);static int N = 200010;static int n, m, a, b, c, d;static int[] v = new int[N];static PriorityQueue<Task> q = new PriorityQueue<Task>();public static void main(String[] args) throws Exception {n = in.nextInt();m = in.nextInt();for (int i = 1; i <= n; i ++) v[i] = in.nextInt();while (m -- > 0) {a = in.nextInt();b = in.nextInt();c = in.nextInt();d = in.nextInt();// 检查是否有任务结束while (!q.isEmpty()) {Task t = q.poll();if (a >= t.time) {	// 任务结束v[t.id] += t.d;	} else {			// 未结束q.add(t);break;}}// 执行任务if (d <= v[b]) {		// 算力足够v[b] -= d;out.println(v[b]);q.add(new Task(b, a + c, d));} else {				// 算力不足out.println(-1);}}out.flush();out.close();}
}class Task implements Comparable<Task>{int id;		// 运行的计算机编号int time;	// 任务结束时间int d;		// 占用算力public Task(int id, int time, int d) {super();this.id = id;this.time = time;this.d = d;}@Overridepublic int compareTo(Task o) {return Integer.compare(this.time, o.time);}
}class In {BufferedReader reader;StringTokenizer tokenizer;In(InputStream inputStream) {reader = new BufferedReader(new InputStreamReader(inputStream));tokenizer = null;}public String next() throws Exception {while (tokenizer == null || !tokenizer.hasMoreTokens()) {tokenizer = new StringTokenizer(reader.readLine());}return tokenizer.nextToken();}public int nextInt() throws Exception {return Integer.parseInt(next());}
}

在这里插入图片描述
在这里插入图片描述
【分析】
这是一道状态压缩DP，枚举每一列的状态，而当前列的状态只会与前两列有关，所以考虑前两列和当前列的状态情况。
状态表示：f(i,a,b,k)表示已经放好前i-1列，第i-2列状态是a，第i-1列状态是b，一共放了k匹马的方案集合。
“日”字冲突判断：例如a & (b << 2) 表示b状态左移2位（格子），是否与a状态存在重合，重合即冲突。如果不等于0，表示存在至少某一位（格子）是冲突的。

import java.util.Scanner;public class J_国际象棋 {/*** 	状态压缩dp*/static Scanner in = new Scanner(System.in);static int N = 110, M = 1 << 6, K = 30, MOD = (int)1e9+7;static int n, m, k;static long[][][][] f = new long[N][M][M][K];public static void main(String[] args) {n = in.nextInt();m = in.nextInt();k = in.nextInt();f[0][0][0][0] = 1;for (int i = 1; i <= m; i ++) {				// 从列开始枚举for (int a = 0; a < 1 << n; a ++) {		// 枚举前两列ab的状态for (int b = 0; b < 1 << n; b ++) {if ((a & (b << 2)) != 0 || (b & (a << 2)) != 0) continue;	// 有冲突for (int c = 0; c < 1 << n; c ++) {	// 枚举当前c列的状态if ((a & (c << 1)) != 0 || (c & (a << 1)) != 0) continue;if ((b & (c << 2)) != 0 || (c & (b << 2)) != 0) continue;int t = get_count(c);			// 当前c列可以存放t匹马，for (int j = t; j <= k; j ++) {f[i][b][c][j] = (f[i][b][c][j] + f[i - 1][a][b][j - t]) % MOD;}}}}}long ans = 0;for (int i = 0; i < 1 << n; i ++) {for (int j = 0; j < 1 << n; j ++) {ans = (ans + f[m][i][j][k]) % MOD;}}System.out.println(ans);}// 返回x状态中有多少个1public static int get_count(int x) {int res = 0;while (x != 0) {if ((x & 1) == 1) res ++;x >>= 1;}return res;}
}

以上就是全部的题目和题解，感觉写得不错的话，就点个赞吧~~

这篇关于2021年第十二届蓝桥杯大赛软件赛省赛第二场JavaB组C++B组全部题目以及题目解析的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/668401。

相关文章

Java中流式并行操作parallelStream的原理和使用方法

Java中流式并行操作parallelStream的原理和使用方法

《Java中流式并行操作parallelStream的原理和使用方法》本文详细介绍了Java中的并行流（parallelStream）的原理、正确使用方法以及在实际业务中的应用案例,并指出在使用并行流... 目录Java中流式并行操作parallelStream0. 问题的产生1. 什么是parallelS
阅读更多...
C++中unordered_set哈希集合的实现

C++中unordered_set哈希集合的实现

《C++中unordered_set哈希集合的实现》std::unordered_set是C++标准库中的无序关联容器,基于哈希表实现,具有元素唯一性和无序性特点,本文就来详细的介绍一下unorder... 目录一、概述二、头文件与命名空间三、常用方法与示例1. 构造与析构2. 迭代器与遍历3. 容量相关4
阅读更多...
Java中Redisson 的原理深度解析

Java中Redisson 的原理深度解析

《Java中Redisson的原理深度解析》Redisson是一个高性能的Redis客户端,它通过将Redis数据结构映射为Java对象和分布式对象,实现了在Java应用中方便地使用Redis,本文... 目录前言一、核心设计理念二、核心架构与通信层1. 基于 Netty 的异步非阻塞通信2. 编解码器三、
阅读更多...
C++中悬垂引用(Dangling Reference) 的实现

C++中悬垂引用(Dangling Reference) 的实现

《C++中悬垂引用(DanglingReference)的实现》C++中的悬垂引用指引用绑定的对象被销毁后引用仍存在的情况,会导致访问无效内存,下面就来详细的介绍一下产生的原因以及如何避免,感兴趣... 目录悬垂引用的产生原因1. 引用绑定到局部变量，变量超出作用域后销毁2. 引用绑定到动态分配的对象，对象
阅读更多...
SpringBoot基于注解实现数据库字段回填的完整方案

SpringBoot基于注解实现数据库字段回填的完整方案

《SpringBoot基于注解实现数据库字段回填的完整方案》这篇文章主要为大家详细介绍了SpringBoot如何基于注解实现数据库字段回填的相关方法,文中的示例代码讲解详细,感兴趣的小伙伴可以了解... 目录数据库表pom.XMLRelationFieldRelationFieldMapping基础的一些代
阅读更多...
一篇文章彻底搞懂macOS如何决定java环境

一篇文章彻底搞懂macOS如何决定java环境

《一篇文章彻底搞懂macOS如何决定java环境》MacOS作为一个功能强大的操作系统,为开发者提供了丰富的开发工具和框架,下面：本文主要介绍macOS如何决定java环境的相关资料,文中通过代码... 目录方法一：使用 which命令方法二：使用 Java_home工具（Apple 官方推荐）那问题来了，
阅读更多...
Java HashMap的底层实现原理深度解析

Java HashMap的底层实现原理深度解析

《JavaHashMap的底层实现原理深度解析》HashMap基于数组+链表+红黑树结构,通过哈希算法和扩容机制优化性能,负载因子与树化阈值平衡效率,是Java开发必备的高效数据结构,本文给大家介绍... 目录一、概述：HashMap的宏观结构二、核心数据结构解析1. 数组（桶数组）2. 链表节点（Node
阅读更多...
Java AOP面向切面编程的概念和实现方式

Java AOP面向切面编程的概念和实现方式

《JavaAOP面向切面编程的概念和实现方式》AOP是面向切面编程,通过动态代理将横切关注点（如日志、事务）与核心业务逻辑分离,提升代码复用性和可维护性,本文给大家介绍JavaAOP面向切面编程的概... 目录一、AOP 是什么？二、AOP 的核心概念与实现方式核心概念实现方式三、Spring AOP 的关
阅读更多...
详解SpringBoot+Ehcache使用示例

详解SpringBoot+Ehcache使用示例

《详解SpringBoot+Ehcache使用示例》本文介绍了SpringBoot中配置Ehcache、自定义get/set方式,并实际使用缓存的过程,文中通过示例代码介绍的非常详细,对大家的学习或者... 目录摘要概念内存与磁盘持久化存储：配置灵活性：编码示例引入依赖：配置ehcache.XML文件：配置
阅读更多...
Java 虚拟线程的创建与使用深度解析

Java 虚拟线程的创建与使用深度解析

《Java虚拟线程的创建与使用深度解析》虚拟线程是Java19中以预览特性形式引入,Java21起正式发布的轻量级线程,本文给大家介绍Java虚拟线程的创建与使用,感兴趣的朋友一起看看吧... 目录一、虚拟线程简介1.1 什么是虚拟线程？1.2 为什么需要虚拟线程？二、虚拟线程与平台线程对比代码对比示例：三
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2