【蓝桥杯 第十三届省赛Java B组】真题训练(A - F)

news/2025/2/14 15:43:27/

目录

A、星期计算 - BigInteger

B、山 - 暴力判断 + 字符串

C、字符统计 - 简单哈希

D、最少刷题数 - 排序 + 思维 + 二分 + 分情况讨论

(1)(错误)自写哈希表

(2)正解 

E、求阶乘 - 数学思维 + 二分

F、最大子矩阵 - (没过)暴力


A、星期计算 - BigInteger

思路:

20^22用电脑自带的计算器也可以算,用Math.pow也可以,这里运用BigInteger

答案:7

import java.math.BigInteger;
import java.util.*;public class abc {public static void main(String[] args){Scanner sc=new Scanner(System.in);BigInteger n=new BigInteger("20");BigInteger res=new BigInteger("1");for(int i=0;i<22;i++) res=res.multiply(n);res=res.mod(new BigInteger("7"));System.out.print(res.intValue()+6);}
}

B、山 - 暴力判断 + 字符串

 思路:

暴力枚举【2022,2022222022】,用long,然后判断回文和单调性即可

用StringBuilder的reverse判断回文也是可以的

答案:3138

import java.math.BigInteger;
import java.util.*;public class abc {public static void main(String[] args){Scanner sc=new Scanner(System.in);long res=0;for(long i=2022;i<=2022222022;i++)if(ck(String.valueOf(i))) res++;System.out.print(res);}public static boolean ck(String s){boolean f=true;int n=s.length();for(int i=0;i<n/2;i++)if(s.charAt(i)!=s.charAt(n-1-i)){f=false;return f;}for(int i=1;i<=n/2;i++)if(s.charAt(i)<s.charAt(i-1)) {f=false;break;}return f;}}
import java.math.BigInteger;
import java.util.*;public class abc {public static void main(String[] args){Scanner sc=new Scanner(System.in);long res=0;for(long i=2022;i<=2022222022;i++)if(ck(String.valueOf(i))) res++;System.out.print(res);}public static boolean ck(String s){int n=s.length();StringBuilder ss=new StringBuilder(s);if(s.compareTo(ss.reverse().toString())!=0) return false;for(int i=1;i<=n/2;i++)if(s.charAt(i)<s.charAt(i-1)) return false;return true;}}

C、字符统计 - 简单哈希

import java.util.*;public class abc {public static void main(String[] args){Scanner sc=new Scanner(System.in);TreeMap<Character,Integer> mp=new TreeMap<>();String s=sc.next();int maxx=0;for(int i=0;i<s.length();i++){char c=s.charAt(i);mp.put(c,mp.getOrDefault(c, 0)+1);if(mp.get(c)>maxx) maxx=mp.get(c);}String res=""; for(Map.Entry<Character,Integer> x:mp.entrySet())if(x.getValue()==maxx) res+=x.getKey();System.out.print(res);}}

D、最少刷题数 - 排序 + 思维 + 二分 + 分情况讨论

 

(1)(错误)自写哈希表

思路:

排序找出mid=a[n/2],然后小于mid的元素要么=mid要么=mid+1,这时候就要看情况了

我自己写的这个如果遇到

8
1 1 3 3 3 10 20 30

这个样例,答案输出的是:

2 2 0 0 0 0 0 0 

很明显是错误的,无法让刷题少的≥刷题多的

  • 我们需要分情况找出mid是+1还是=mid,这时候就需要统计比mid大的个数max_m和比mid小的个数min_m
  • 这个样例的mid是3,则max_m=3,min_m=2
  • 我们会发现此时如果a[i]≤mid,就需要令其等于mid+1,因为max_m>min_m,必须比mid大,才能让min_m增大
package demo_lanqiao;import java.math.BigInteger;
import java.util.*;public class abc {public static void main(String[] args){Scanner sc=new Scanner(System.in);int n=sc.nextInt();int[] a=new int[n],res=new int[n],b=new int[n];Map<Integer,Integer> mp=new HashMap<>();for(int i=0;i<n;i++){a[i]=sc.nextInt();b[i]=a[i];}Arrays.sort(a);for(int x:a) System.out.print(x+" ");System.out.println();int mid=a[n/2];for(int i=0;i<n;i++){int x=0;if(n%2==0) x=a[i]<mid? mid-a[i]:0;else if(n%2==1) x=a[i]<mid? mid+1-a[i]:0;mp.put(a[i],x);}for(int i=0;i<n;i++) res[i]=mp.get(b[i]);for(int x:res) System.out.print(x+" ");}}

(2)正解 

思路:

        先排序找出中位数mid=a[n/2],用二分统计出大于mid的个数max_m,和小于mid的个数min_m,分情况讨论:

设res为a[i]最终刷题数

  • min_m < max_m     需要让≤mid的数比mid大1,这样才可保证res>mid,保证刷题多<刷题少
    • 8
    • 1 1 3 3 3 10 20 30
  • min_m == max_m  需要让<mid的数比mid大1,才能保证res>mid,刷题多<刷题少
    • 5
    • 1 2 3 4 5
  • min_m > max_m    只要让<mid的数=mid即可,这样既刷题多<刷题少,又能保证刷题数最少
    • 6
    • 1 1 1 2 4 5

蓝桥杯官网的测评机同一个代码每一次测的百分比都不一样。。。。

蓝桥杯2022年第十三届省赛真题-最少刷题数 - C语言网

import java.math.BigInteger;
import java.util.*;public class abc {public static void main(String[] args){Scanner sc=new Scanner(System.in);int n=sc.nextInt();int[] a=new int[n],t=new int[n];for(int i=0;i<n;i++){a[i]=sc.nextInt();t[i]=a[i];}Arrays.sort(t);int mid=t[n/2];int min_m=findmin(t,mid),max_m=n-findmax(t,mid)-1;if(min_m<max_m) for(int i=0;i<n;i++) if(a[i]<=mid) System.out.print(mid-a[i]+1+" ");else System.out.print(0+" ");else if(min_m==max_m)for(int i=0;i<n;i++) if(a[i]<mid) System.out.print(mid-a[i]+1+" ");else System.out.print(0+" ");else for(int i=0;i<n;i++) if(a[i]<mid) System.out.print(mid-a[i]+" ");else System.out.print(0+" ");}public static int findmax(int[] a,int tar){int l=0,r=a.length-1;while(l<r){int mid=l+r+1>>1;if(a[mid]<=tar) l=mid;else r=mid-1;}return l;}public static int findmin(int[] a,int tar){int l=0,r=a.length-1;while(l<r){int mid=l+r>>1;if(a[mid]>=tar) r=mid;else l=mid+1;}return r;}}

E、求阶乘 - 数学思维 + 二分

思路:

题目越短,难度越大,看数据范围就知道主打就是一个不会(暴力无法做)

思路参考:

蓝桥杯刷题014——求阶乘(二分法)-CSDN博客

很明显末尾0的出现跟因子2和5息息相关,因为2×5=10,其他数无论怎么乘都不可能出0

每个数字末尾的每个0都可以看成是2和5相乘得到

结论:给定一个数的阶乘,计算它的因子中2*5出现的次数,即可确定末尾0的个数 

而因子2无需寻找,因为相乘关系2,4,6,8中都存在2,2肯定比5多

【求N的阶乘尾部0的个数】转换为【求N的阶乘中因子5的个数】
        我们可知:1~24中每隔5个就有1个5(分别是5 10 15 20共4个),而25能分出2个5,因此25!=末尾6个0,没有5个0,如下图

为什么这样算?

【第一轮除5】我们先把含有1个及以上5的25个数全部取出一个5加到总数num,那么本来1个5的数就变成0个(可以忽略),本来2个5的数变成1个5的数,本来3个5的变成2个5的。

【第二轮除5】再对原本含有2个及以上5的5个数(现在是含有一个及以上5的数)操作一次,只剩下1个含5的数

【第三轮除5】最后再对含5的1个数取出一个5加到总数num,这样就把全部的因子5转移到了总数num

结论:求N的阶乘中因子5的个数,将N每次除以5的商求和(N中5因子的个数)即可。

因为k值很大,我们不可能枚举所有情况,而k随N增大而增加,具有单调性,可以用二分

找出≥check()的最小值【用r=mid模板】 ,检查mid末尾0的个数是否==k,如果不是返回-1

import java.util.*;public class abc {public static void main(String[] args){Scanner sc=new Scanner(System.in);long k=sc.nextLong();long l=1,r=Long.MAX_VALUE-1;while(l<r){long mid=l+r>>1;if(ck(mid)>=k) r=mid;else l=mid+1;}if(ck(r)!=k) System.out.print(-1);else System.out.print(r);}public static long ck(long n){long res=0;while(n!=0){res+=n/5;n/=5;}return res;}}

F、最大子矩阵 - (没过)暴力

 

 

六个for暴力拿10%

import java.util.*;public class abc {public static void main(String[] args){Scanner sc=new Scanner(System.in);int[][] g=new int[80][80];TreeMap<Integer,Integer> mp=new TreeMap<>();int n=sc.nextInt(),m=sc.nextInt();for(int i=0;i<n;i++)for(int j=0;j<m;j++) g[i][j]=sc.nextInt();int limit=sc.nextInt();int res=0;for(int up=0;up<n;up++)for(int dw=up;dw<n;dw++)for(int l=0;l<m;l++)for(int r=l;r<m;r++){int max=0,min=Integer.MAX_VALUE;for(int i=up;i<=dw;i++)for(int j=l;j<=r;j++){if(g[i][j]>max) max=g[i][j];if(g[i][j]<min) min=g[i][j];}if(max-min>=0&&max-min<=limit&&(dw-up+1)*(r-l+1)>res){res=(dw-up+1)*(r-l+1);//System.out.println("["+max+","+min+"]"+up+" "+dw+" "+l+" "+r+" "+res);}}System.out.print(res);}}


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

相关文章

2023最新软件测试面试300问

一、Linux系统应用和环境配置 1、Linux系统的操作命令给我说10个&#xff0c;一般用什么工具远程连接Linux服务器&#xff1f; 2、Linux中的日志存储在哪里&#xff1f;怎么查看日志内容&#xff1f; 3、Linux中top和ps命令的区别&#xff1f; 4、Linux命令运行的结果如何写…

.one4-V-XXXXXXXX勒索病毒数据怎么处理|数据解密恢复

导言&#xff1a; 随着科技的不断发展&#xff0c;网络犯罪也在不断进化&#xff0c;.one4-V-XXXXXXXX勒索病毒作为其中的一种威胁&#xff0c;对个人和企业的数据安全构成了巨大的风险。本文将深入介绍.one4-V-XXXXXXXX勒索病毒的特点、详细的数据恢复方法&#xff0c;以及全…

离线环境通过脚本实现服务器时钟同步(假同步)

1、背景 最近遇到一个时钟同步问题&#xff0c;是内网多台服务器之间时钟不同步&#xff0c;然后部署在不同服务器间的应用展示得时间戳不能统一&#xff0c;所以用户让做一下内网服务器间得时钟同步。 内网服务器x86和arm都有&#xff0c;而且有得系统是centos有得是ubuntu&…

认识计算机-JavaEE初阶

文章目录 一、计算机的发展史二、冯诺依曼体系&#xff08;Von Neumann Architecture&#xff09;三、CPU基本工作流程3.1 算术逻辑单元&#xff08;ALU&#xff09;3.2 寄存器&#xff08;Register)和内存&#xff08;RAM&#xff09;3.3 控制单元&#xff08;CU&#xff09;3…

conda添加清华镜像源

一、conda下载 https://mirrors.tuna.tsinghua.edu.cn/anaconda/archive/ 显示所有channel conda config --show channels 二、添加清华镜像源 conda config --add channels https://mirrors.tuna.tsinghua.edu.cn/anaconda/pkgs/free/ conda config --add channels https://…

dream_ready

&#x1f9f8;欢迎来到dream_ready的博客&#xff0c;&#x1f4dc;相信您对这篇博客也感兴趣o (ˉ▽ˉ&#xff1b;) Python 语法及入门 &#xff08;超全超详细&#xff09; 专为Python零基础 一篇博客让你完全掌握Python语法 路的尽头是什么&#xff1f;这是我年少时常伴在嘴…

765. 情侣牵手 --力扣 --JAVA

题目 n 对情侣坐在连续排列的 2n 个座位上&#xff0c;想要牵到对方的手。 人和座位由一个整数数组 row 表示&#xff0c;其中 row[i] 是坐在第 i 个座位上的人的 ID。情侣们按顺序编号&#xff0c;第一对是 (0, 1)&#xff0c;第二对是 (2, 3)&#xff0c;以此类推&#xff0c…

并查集:Leetcode765 情侣牵手

n 对情侣坐在连续排列的 2n 个座位上&#xff0c;想要牵到对方的手。 人和座位由一个整数数组 row 表示&#xff0c;其中 row[i] 是坐在第 i 个座位上的人的 ID。情侣们按顺序编号&#xff0c;第一对是 (0, 1)&#xff0c;第二对是 (2, 3)&#xff0c;以此类推&#xff0c;最后…