第15届蓝桥杯国赛JavaA组个人题解

2024-06-03 09:20
文章标签 java 15 蓝桥 个人 题解 杯国赛

本文主要是介绍第15届蓝桥杯国赛JavaA组个人题解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

最后两个概率题不会做, 50分没了
博弈论交了暴力, 30%的分
赛后hack了自己1个填空和一个15分的题
算下来应该是66分, 喜提国一最后一名, rank11

A 田字与直线

题目:

9个点按3*3排成矩阵状, 求恰好经过其中2个点的直线个数

答案

过角的: 4个角, 每个2条

不过角: 4个中点, 4条

ans = 12

B 传送阵

题目

42个传送阵, 长度为42的排列a

第i个传送阵会传送到a[i]

每天执行一次传送, 求 恰好2024天一循环的排列方案数, 模1e9+7

如: 3个传送阵

1 → 2 、 2→3 、3→1, 每3天一循环

1→ 1 、2→3、3→2, 每2天一循环

思路

设 42个传送阵分为k个连通块, 第i个连通块大小为a[i]

则有
l c m ( a [ i ] ) = 2024 ∑ a [ i ] = 42 lcm(a[i])=2024\\ \sum{a[i]}=42 lcm(a[i])=2024∑a[i]=42
枚举连通块个数k, 然后dfs剪枝枚举每一个连通块大小

对于大小为size的块来说, 可形成的不同的环的数量为 A(size-1)

对于枚举的块大小序列(升序): a1,a2…ak
方案数 = C 42 a 1 A a 1 − 1 ∗ C 42 − a 1 a 2 A a 2 − 1 ∗ . . . C 42 − . . . a k A a k − 1 方案数 = C_{42}^{a_1}A_{a_1-1}*C_{42-a_1}^{a_2}A_{a_2-1}*...C_{42-...}^{a_k}A_{a_k-1} 方案数=C42a1​​Aa1​−1​∗C42−a1​a2​​Aa2​−1​∗...C42−...ak​​Aak​−1​

代码(仅供参考)

此代码非赛时代码, 赛时代码被我hack了

import java.util.*;public class Main {static int k;// 连通块个数static int[] arr = new int[50];// 搜索结果, arr[i]:连通块i的大小, 内部全排列static long ans = 0;static int MOD = 10_0000_0007;static long[] A = new long[50];// 阶乘(排列数)static {A[1] = 1;for (int i = 2; i < 50; i++) {A[i] = A[i - 1] * i % MOD;}}public static void main(String[] args) {for (k = 2; k < 42; k++) {Arrays.fill(arr, 0);dfs(0, 1, 1);}System.out.println(ans);//151495483}static long[][] C = new long[50][50];static {for (int i = 0; i < 50; i++) {C[i][0] = 1;}for (int i = 1; i < 50; i++) {for (int j = 1; j < 50; j++) {C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % MOD;}}}static void dfs(int sum, int i, long lcm) {if (sum == 42 && i == k + 1) {if (lcm == 2024) {long res = 1;int m = 42;for (int j = 1; j <= k; j++) {res = res * C[m][arr[j]] % MOD * A[arr[j] - 1] % MOD;m -= arr[j];}ans = (ans + res) % MOD;}return;}if (sum >= 42 || i >= k + 1 || lcm >= 2024) return;//剪枝for (int a = Math.max(1, arr[i - 1]); a + sum <= 42; a++) {// 枚举第i位(块大小升序)arr[i] = a;dfs(sum + a, i + 1, lcm(lcm, a));arr[i] = 0;}}static long gcd(long a, long b) {if (b == 0) return a;return gcd(b, a % b);}static long lcm(long a, long b) {return (a * b) / gcd(a, b);}}

C 进制转换

题目

给出n组数, 第i组位A[i],B[i]

A可能是2,4,8,16中的一种, B是一个十进制数, A转为10进制不超过B

求 A的唯一十进制, 如果没有 或 解不唯一则输出-1

思路

try Integer.parseInt

代码

import java.io.*;public class Main {static BufferedReader bf = new BufferedReader(new InputStreamReader(System.in), 65535);static StreamTokenizer st = new StreamTokenizer(bf);static PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));static int I() throws IOException {st.nextToken();return (int) st.nval;}static String S() throws IOException {String res = bf.readLine();while (res.isEmpty()) res = bf.readLine();return res;}/*21010 23A1 160*/public static void main(String[] args) throws IOException {int n = I();for (int i = 0; i < n; i++) {String[] op = S().split(" ");pw.println(solve(op[0], Long.parseLong(op[1])));}pw.flush();}static int[] JZ = new int[]{2, 4, 8, 16};static long solve(String A, long B) {long ans = -1;for (int jz : JZ) {long r = change(A, jz);if (r > B) continue;if (r != -1) {if (ans != -1) return -1;ans = r;}}return ans;}static long change(String A, int jz) {try {return Long.parseLong(A, jz);} catch (Exception e) {return -1;}}
}

D 栈

题目

n个数依次入栈, 如果数已存在栈中, 则取出放栈顶

每放入一个数, 需要输出栈中相邻数字之和为奇数的组数

思路

双向链表 + 哈希表 进行模拟

哈希表通过key拿到Node对象, 把Node对象从链表中移除, 再添加到末尾

期间维护相邻数字之和为奇数的组数, 取数放数时只有相邻的那几个数字是否和为奇会改变

代码

import java.io.*;
import java.util.*;public class Main {static BufferedReader bf = new BufferedReader(new InputStreamReader(System.in), 65535);static StreamTokenizer st = new StreamTokenizer(bf);static PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));static int I() throws IOException {st.nextToken();return (int) st.nval;} /*
4
1 2 3 2*/public static void main(String[] args) throws IOException {int n = I();HashMap<Integer, Node> map = new HashMap<>();//val->nodeint ans = 0;for (int i = 0; i < n; i++) {int v = I();if (map.containsKey(v)) {Node node = map.get(v);if (node.pre != head && isOdd(node.pre.val + node.val)) {ans--;}if (node.next != head && isOdd(node.val + node.next.val)) {ans--;}if (node.pre != head && node.next != head && isOdd(node.pre.val + node.val + node.next.val)) {ans++;}remove(node);addLast(node);if (node.pre != head && isOdd(node.pre.val + node.val)) {ans++;}} else {Node node = new Node(v);addLast(node);if (node.pre != head && isOdd(node.pre.val + node.val)) {ans++;}map.put(v, node);}pw.println(ans);}pw.flush();}static boolean isOdd(int x) {return (x & 1) == 1;}static Node head = new Node(-1);//哨兵头节点static {head.next = head;head.pre = head;}static class Node {int val;Node pre, next;public Node(int val) {this.val = val;}}static void addLast(Node node) {Node last = head.pre;node.pre = last;node.next = head;head.pre = node;last.next = node;}static void remove(Node node) {Node pre = node.pre, next = node.next;pre.next = next;next.pre = pre;}
}

E 修改数位

题目

给出一个数串a, 可以随意修改数位, 代价为 数字差abs(原数-修改数)

问修改使得数串存在一个子串为0~9的排列的最小代价

(修改前后数串首位不能为0)

思路

枚举

代码(仅供参考)

此代码非赛时代码, 赛时代码被我hack了

import java.io.*; public class Main {static BufferedReader bf = new BufferedReader(new InputStreamReader(System.in), 65535);static String S() throws IOException {String res = bf.readLine();while (res.isEmpty()) res = bf.readLine();return res;}
/*
1023456789    0
2023456789    1
9123456782    2
21123456785   5
55555555555   25*/public static void main(String[] args) throws IOException {char[] s = S().toCharArray();int n = s.length;int[] count = new int[10];int ans = 0x3f3f3f3f;for (int i = 1; i + 9 < n; i++) {Arrays.fill(count, 0);for (int j = i; j < i + 10; j++) {count[s[j] - '0']++;}int op = 0;for (int j = 0; j < 9; j++) {op += getOp(count, j, 1);}ans = Math.min(ans, op);}// 首位特判for (int k = 1; k <= 9; k++) {int op = Math.abs(s[0] - '0' - k);// 后9位, 不要k的操作次数Arrays.fill(count, 0);for (int i = 1; i <= 9; i++) {count[s[i] - '0']++;}for (int j = 0; j <= 9; j++) {if (j == k) {op += getOp(count, j, 0);} else {op += getOp(count, j, 1);}}ans = Math.min(ans, op);}System.out.println(ans);}private static int getOp(int[] count, int j, int x) {if (count[j] == x) return 0;int t = Math.abs(count[j] - x);if (count[j] > x) {count[j + 1] += t;// 移到j+1} else {count[j + 1] -= t;// 从j+1移来}return t;}
}

F 文本编辑

题目

操作:

(1) 光标左/右移动n位

(2) 光标前插入字符串

(3) 删除光标前/后字符n个

求操作后的文本

思路

两个栈模拟

代码

import java.io.*;
import java.util.*; public class Main {static BufferedReader bf = new BufferedReader(new InputStreamReader(System.in), 65535);static StreamTokenizer st = new StreamTokenizer(bf);static int I() throws IOException {st.nextToken();return (int) st.nval;}static String S() throws IOException {String res = bf.readLine();while (res.isEmpty()) res = bf.readLine();return res;}public static void main(String[] args) throws Exception {int n = I();LinkedList<Character> pre = new LinkedList<>(), next = new LinkedList<>();for (int i = 0; i < n; i++) {String op = S();char type = op.charAt(0);int len = op.length();if (type == 'i') {//插入文本// 格式 insert "xxx"String text = op.substring(8, len - 1);for (char ch : text.toCharArray()) {pre.addLast(ch);}} else if (type == 'd') {//删除文本// 格式 dxxxh 或 dxxxlchar t = op.charAt(len - 1);int num = Integer.parseInt(op.substring(1, len - 1));if (t == 'h') {for (int k = 0; k < num && !pre.isEmpty(); k++) {pre.pollLast();}} else {for (int k = 0; k < num && !next.isEmpty(); k++) {next.pollFirst();}}} else {//移动光标// 格式 xxxh 或 xxxlchar t = op.charAt(len - 1);int num = Integer.parseInt(op.substring(0, len - 1));if (t == 'h') {for (int k = 0; k < num && !pre.isEmpty(); k++) {next.addFirst(pre.pollLast());}} else {for (int k = 0; k < num && !next.isEmpty(); k++) {pre.addLast(next.pollFirst());}}}}StringBuilder ans = new StringBuilder();for (char ch : pre) ans.append(ch);for (char ch : next) ans.append(ch);System.out.println(ans);}
}

G 异或博弈

题目

从长度为n的数组a中取2个数字, A希望数字异或尽可能大, B希望尽可能小

问, A先选, B后选, 异或为多少? B先选,A后选,异或为多少?

思路

0/1字典树

A先选: 枚举A的选择vA, 从字典树上移除vA, B希望尽可能小, 所以vB从高位开始应该尽可能与vA相同, 在树上查找即可

B先选: 同理,枚举vB, 移除vB, A希望尽可能大, 就要与vB相反

(没时间了, 没码出来, 交了暴力的30%)

代码(仅供参考)

import java.io.*; public class Main {static BufferedReader bf = new BufferedReader(new InputStreamReader(System.in), 65535);static StreamTokenizer st = new StreamTokenizer(bf);static int I() throws IOException {st.nextToken();return (int) st.nval;}/*
4
2 3 5 6A选6, B需要最小选5, 最小为110^101=3
B选6, A需要最大选3, 最大为110^011=5
输出 3 5*/public static void main(String[] args) throws Exception {int n = I();int[] a = new int[n];Tree tree = new Tree();for (int i = 0; i < n; i++) {a[i] = I();tree.add(a[i]);}//打表(a);int ansAB = Integer.MIN_VALUE, ansBA = Integer.MAX_VALUE;int vA, vB;for (int i = 0; i < n; i++) {// A先选,B后选vA = a[i];tree.remove(vA);vB = tree.find(vA);ansAB = Math.max(ansAB, vA ^ vB);tree.add(vA);//System.out.println("A选" + vA + " B选" + vB + " 最小为" + (vA ^ vB));// B先选,A后选vB = a[i];tree.remove(vB);vA = tree.find(~vB);ansBA = Math.min(ansBA, vA ^ vB);tree.add(vB);//System.out.println("B选" + vB + " A选" + vA + " 最大为" + (vA ^ vB));}System.out.println(ansAB + " " + ansBA);}static void 打表(int[] a) {int n = a.length;int ansAB = Integer.MIN_VALUE, ansBA = Integer.MAX_VALUE;for (int i = 0; i < n; i++) {// vAB:A已选定,由B选,B需要选一个最小的// vBA:B已选定,由A选,A需要选一个最大的int vAB = Integer.MAX_VALUE, vBA = Integer.MIN_VALUE;for (int j = 0; j < n; j++) {if (j == i) continue;int v = a[i] ^ a[j];vAB = Math.min(vAB, v);vBA = Math.max(vBA, v);}System.out.println("A选" + a[i] + " B最小 " + vAB);System.out.println("B选" + a[i] + " A最大 " + vBA);ansAB = Math.max(ansAB, vAB);// A从选择的结果里选最大结果ansBA = Math.min(ansBA, vBA);// B从选择的结果里选最小结果}System.out.println(ansAB + " " + ansBA);}static class Tree {static class Node {int cnt = 0;Node zero, one;}Node root = new Node();void add(int v) {Node p = root;for (int i = 31; i >= 0; i--) {int bit = (v >>> i) & 1;if (p.zero == null) p.zero = new Node();if (p.one == null) p.one = new Node();p = bit == 0 ? p.zero : p.one;p.cnt++;}}void remove(int v) {Node p = root;for (int i = 31; i >= 0; i--) {int bit = (v >>> i) & 1;if (p.zero == null) p.zero = new Node();if (p.one == null) p.one = new Node();p = bit == 0 ? p.zero : p.one;p.cnt--;}}int ans;int find(int v) {//查找最接近v的路径ans = Integer.MAX_VALUE;dfs(root, v, 31, 0);return ans;}void dfs(Node p, int v, int level, int curV) {if (level < 0) {if ((v ^ curV) < ans) ans = curV;//寻找最接近,异或值最小return;}int bit = (v >>> level) & 1;if (bit == 0 && p.zero != null && p.zero.cnt > 0) {dfs(p.zero, v, level - 1, curV);return;}if (bit == 1 && p.one != null && p.one.cnt > 0) {dfs(p.one, v, level - 1, curV + (1 << level));return;}if (p.zero != null && p.zero.cnt > 0) dfs(p.zero, v, level - 1, curV);if (p.one != null && p.one.cnt > 0) dfs(p.one, v, level - 1, curV + (1 << level));}}
}

H 刷墙

题目

n个墙排成一排, 要刷第i个墙,需要保证i+1~n的已刷墙数为偶数

求方案数, 模1e9+7

思路

打表

n012345678910
方案数111241236144576288014400
转移1*1*1*2*2*3*3*4*4*5*5

代码

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;public class Main {static BufferedReader bf = new BufferedReader(new InputStreamReader(System.in), 65535);static StreamTokenizer st = new StreamTokenizer(bf);static int I() throws IOException {st.nextToken();return (int) st.nval;}static int MOD = 10_0000_0007;public static void main(String[] args) throws Exception {int n = I();int k = 0;for (int i = 0; i < n; i++) k += I();//忽略不用刷的墙long ans = 1;int cnt = 0, mul = 1;for (int i = 0; i < k; i++) {ans = ans * mul % MOD;cnt++;if (cnt == 2) {cnt = 0;mul++;}}System.out.println(ans);}
}

I 斗蛐蛐

题目

n个蛐蛐成环, 第i只的攻击力为a[i], 有a[i]的概率杀死被攻击的蛐蛐

从第1只开始攻击

每次攻击会随机选择左边或右边(概率1/2), 如果杀死则环长度-1

求最后存活是第i只的概率(每只的都要求)

J 合并小球

题目

数轴上n个球, 第i个在x[i], 价值y[i]

每秒每个球都有1/2的概率向右移动一位

如果两球相邻, 左球向右, 右球不动, 则它们会合并为一个球, 新球价值为他们的价值之积

当球移动到T位置, 会被立即收走, 统计价值之和

求价值之和的期望

以上代码有任何问题, 欢迎指正

这篇关于第15届蓝桥杯国赛JavaA组个人题解的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


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

相关文章

Spring常见错误之Web嵌套对象校验失效解决办法

Spring常见错误之Web嵌套对象校验失效解决办法

《Spring常见错误之Web嵌套对象校验失效解决办法》：本文主要介绍Spring常见错误之Web嵌套对象校验失效解决的相关资料,通过在Phone对象上添加@Valid注解,问题得以解决,需要的朋... 目录问题复现案例解析问题修正总结  问题复现当开发一个学籍管理系统时，我们会提供了一个 API 接口去
阅读更多...
Java操作ElasticSearch的实例详解

Java操作ElasticSearch的实例详解

《Java操作ElasticSearch的实例详解》Elasticsearch是一个分布式的搜索和分析引擎,广泛用于全文搜索、日志分析等场景,本文将介绍如何在Java应用中使用Elastics... 目录简介环境准备1. 安装 Elasticsearch2. 添加依赖连接 Elasticsearch1. 创
阅读更多...
Spring核心思想之浅谈IoC容器与依赖倒置(DI)

Spring核心思想之浅谈IoC容器与依赖倒置(DI)

《Spring核心思想之浅谈IoC容器与依赖倒置(DI)》文章介绍了Spring的IoC和DI机制,以及MyBatis的动态代理,通过注解和反射,Spring能够自动管理对象的创建和依赖注入,而MyB... 目录一、控制反转 IoC二、依赖倒置 DI1. 详细概念2. Spring 中 DI 的实现原理三、
阅读更多...
SpringBoot 整合 Grizzly的过程

SpringBoot 整合 Grizzly的过程

《SpringBoot整合Grizzly的过程》Grizzly是一个高性能的、异步的、非阻塞的HTTP服务器框架,它可以与SpringBoot一起提供比传统的Tomcat或Jet... 目录为什么选择 Grizzly？Spring Boot + Grizzly 整合的优势添加依赖自定义 Grizzly 作为
阅读更多...
Java后端接口中提取请求头中的Cookie和Token的方法

Java后端接口中提取请求头中的Cookie和Token的方法

《Java后端接口中提取请求头中的Cookie和Token的方法》在现代Web开发中,HTTP请求头（Header）是客户端与服务器之间传递信息的重要方式之一,本文将详细介绍如何在Java后端（以Sp... 目录引言1. 背景1.1 什么是 HTTP 请求头？1.2 为什么需要提取请求头？2. 使用 Spr
阅读更多...
Java如何通过反射机制获取数据类对象的属性及方法

Java如何通过反射机制获取数据类对象的属性及方法

《Java如何通过反射机制获取数据类对象的属性及方法》文章介绍了如何使用Java反射机制获取类对象的所有属性及其对应的get、set方法,以及如何通过反射机制实现类对象的实例化,感兴趣的朋友跟随小编一... 目录一、通过反射机制获取类对象的所有属性以及相应的get、set方法1.遍历类对象的所有属性2.获取
阅读更多...
Java中的Opencv简介与开发环境部署方法

Java中的Opencv简介与开发环境部署方法

《Java中的Opencv简介与开发环境部署方法》OpenCV是一个开源的计算机视觉和图像处理库,提供了丰富的图像处理算法和工具,它支持多种图像处理和计算机视觉算法,可以用于物体识别与跟踪、图像分割与... 目录1.Opencv简介Opencv的应用2.Java使用OpenCV进行图像操作opencv安装j
阅读更多...
java Stream操作转换方法

java Stream操作转换方法

《javaStream操作转换方法》文章总结了Java8中流(Stream)API的多种常用方法,包括创建流、过滤、遍历、分组、排序、去重、查找、匹配、转换、归约、打印日志、最大最小值、统计、连接、... 目录流创建1、list 转 map2、filter（）过滤3、foreach遍历4、groupingB
阅读更多...
SpringBoot如何使用TraceId日志链路追踪

SpringBoot如何使用TraceId日志链路追踪

《SpringBoot如何使用TraceId日志链路追踪》文章介绍了如何使用TraceId进行日志链路追踪,通过在日志中添加TraceId关键字,可以将同一次业务调用链上的日志串起来,本文通过实例代码... 目录项目场景：实现步骤1、pom.XML 依赖2、整合logback，打印日志，logback-sp
阅读更多...
Java操作PDF文件实现签订电子合同详细教程

Java操作PDF文件实现签订电子合同详细教程

《Java操作PDF文件实现签订电子合同详细教程》：本文主要介绍如何在PDF中加入电子签章与电子签名的过程,包括编写Word文件、生成PDF、为PDF格式做表单、为表单赋值、生成文档以及上传到OB... 目录前言：先看效果：1.编写word文件1.2然后生成PDF格式进行保存1.3我这里是将文件保存到本地后
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2