第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。

相关文章

Java中的String.valueOf()和toString()方法区别小结

Java中的String.valueOf()和toString()方法区别小结

《Java中的String.valueOf()和toString()方法区别小结》字符串操作是开发者日常编程任务中不可或缺的一部分,转换为字符串是一种常见需求,其中最常见的就是String.value... 目录String.valueOf()方法方法定义方法实现使用示例使用场景toString()方法方法
阅读更多...
Java中List的contains()方法的使用小结

Java中List的contains()方法的使用小结

《Java中List的contains()方法的使用小结》List的contains()方法用于检查列表中是否包含指定的元素,借助equals()方法进行判断,下面就来介绍Java中List的c... 目录详细展开1. 方法签名2. 工作原理3. 使用示例4. 注意事项总结结论：List 的 contain
阅读更多...
Java实现文件图片的预览和下载功能

Java实现文件图片的预览和下载功能

《Java实现文件图片的预览和下载功能》这篇文章主要为大家详细介绍了如何使用Java实现文件图片的预览和下载功能,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... Java实现文件（图片）的预览和下载 @ApiOperation("访问文件") @GetMapping("
阅读更多...
Spring Boot + MyBatis Plus 高效开发实战从入门到进阶优化(推荐)

Spring Boot + MyBatis Plus 高效开发实战从入门到进阶优化(推荐)

《SpringBoot+MyBatisPlus高效开发实战从入门到进阶优化(推荐)》本文将详细介绍SpringBoot+MyBatisPlus的完整开发流程,并深入剖析分页查询、批量操作、动... 目录Spring Boot + MyBATis Plus 高效开发实战：从入门到进阶优化1. MyBatis
阅读更多...
SpringCloud动态配置注解@RefreshScope与@Component的深度解析

SpringCloud动态配置注解@RefreshScope与@Component的深度解析

《SpringCloud动态配置注解@RefreshScope与@Component的深度解析》在现代微服务架构中,动态配置管理是一个关键需求,本文将为大家介绍SpringCloud中相关的注解@Re... 目录引言1. @RefreshScope 的作用与原理1.1 什么是 @RefreshScope1.
阅读更多...
Java并发编程必备之Synchronized关键字深入解析

Java并发编程必备之Synchronized关键字深入解析

《Java并发编程必备之Synchronized关键字深入解析》本文我们深入探索了Java中的Synchronized关键字,包括其互斥性和可重入性的特性,文章详细介绍了Synchronized的三种... 目录一、前言二、Synchronized关键字2.1 Synchronized的特性1. 互斥2.
阅读更多...
Spring Boot 配置文件之类型、加载顺序与最佳实践记录

Spring Boot 配置文件之类型、加载顺序与最佳实践记录

《SpringBoot配置文件之类型、加载顺序与最佳实践记录》SpringBoot的配置文件是灵活且强大的工具,通过合理的配置管理,可以让应用开发和部署更加高效,无论是简单的属性配置,还是复杂... 目录Spring Boot 配置文件详解一、Spring Boot 配置文件类型1.1 applicatio
阅读更多...
Java中StopWatch的使用示例详解

Java中StopWatch的使用示例详解

《Java中StopWatch的使用示例详解》stopWatch是org.springframework.util包下的一个工具类,使用它可直观的输出代码执行耗时,以及执行时间百分比,这篇文章主要介绍... 目录stopWatch 是org.springframework.util 包下的一个工具类，使用它
阅读更多...
Java进行文件格式校验的方案详解

Java进行文件格式校验的方案详解

《Java进行文件格式校验的方案详解》这篇文章主要为大家详细介绍了Java中进行文件格式校验的相关方案,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录一、背景异常现象原因排查用户的无心之过二、解决方案Magandroidic Number判断主流检测库对比Tika的使用区分zip
阅读更多...
Java实现时间与字符串互相转换详解

Java实现时间与字符串互相转换详解

《Java实现时间与字符串互相转换详解》这篇文章主要为大家详细介绍了Java中实现时间与字符串互相转换的相关方法,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录一、日期格式化为字符串（一）使用预定义格式（二）自定义格式二、字符串解析为日期（一）解析ISO格式字符串（二）解析自定义
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2