目录
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);}}