13届蓝桥杯省赛Java B 组Q1~Q4

题目链接Q1蓝桥云课星期计算洛谷P13928 [蓝桥杯 2022 省 Java B] 星期计算Q2蓝桥云课山洛谷P13929 [蓝桥杯 2022 省 Java B] 山Q3蓝桥云课字符统计洛谷P13930 [蓝桥杯 2022 省 Java B] 字符统计Q4蓝桥云课最少刷题数洛谷P13931 [蓝桥杯 2022 省 Java B] 最少刷题数算法原理Q1解法7为一个周期时间复杂的O(1)思路很简单,直接用20²²%7取余数,余数6即为结果Q2解法暴力枚举时间复杂度O(1)注意文字陷阱单调不减≠单调递增单调不减保持不变单调递增由于“山”回文因此我们只看前半部分即可四位数ABBA时A位只能取1或2A位≤B位≤9五位数ABCBA时1≤A位≤9A位≤B位≤9B位≤C位≤9六位数ABCCBA时与五位数相同七位数ABCDCBA时1≤A位≤9A位≤B位≤9B位≤C位≤9C位≤D位≤9八位数ABCDDCBA时与七位数相同九位数ABCDEDCBA时1≤A位≤9A位≤B位≤9B位≤C位≤9C位≤D位≤9D位≤C位≤9十位数ABCDEEDCBA时最大为2022222022A位为2时不可达因此A位只能为1其余位与上述规律相同累加到一起就是结果3138Q3解法哈希表时间复杂度O(N)思路很简单这应该是蓝桥杯中为数不多的最接近力扣的题了把字符串中所有字符的频率统计在一个哈希表中找到其中的最大频率只要等于这个最大频率就可以打印到结果中优化由于只有大写字母因此我们可以用一个大小为26的数组来代替哈希表这样会更快Q4解法排序中位数时间复杂度O(n logn)其实这题排序很好想因为要保证“刷题比他多”≤“刷题比他少”因此自然要用到排序但是有1点很容易搞混不能直接取中位数作为target了事因为排序后的数组可以是[1,2,2,2,2,3,3]当中位数对应的数值有很多时即使根据n的奇偶取中间偏左还是中间偏右都会取到相同的值此时我们可能想到用最左端点模型和最右端点模型来找中位数的最左端点位置和最右端点位置这样就能快速计算出中位数左右边各有多少数快速确定每个数需要达到的目标值但即使能处理好边界情况这个思路其实也是错的因为“并不是每个都需要刷到同一个数target每个人的target可以不一样”我们最终要的就是“当前数多少能保证比他多≤比他少”因此可分2种情况考虑①中位数如果已满足条件那么目标值就是他本身否则就是中位数1②非中位数先要补到中位数那么它改变后比中位数小的值就少了1个因此有效小的数量原本的1接下来就是①中位数的逻辑了整体思路如下①排序寻找中位数mid数组里的数不超过它的数数组里不小于它的数②大于mid的数显然是满足条件的直接输出0③等于mid的数去掉相等的情况如果该数不符合条件直接1因为目标值只能是mid或者mid1④小于mid的数至少要补足到中位数的大小不同于中位数因为补足以后小于中位数的数少了1个。所以统计数据中小于的部分应该-1接下来就等同于③判断是否需要额外1Java代码Q1public class Main { public static void main(String[] args) { System.out.println((int)Math.pow(20,22)%76); } }Q2import java.util.Scanner; public class Main { public static void main(String[] args) { int cnt40,cnt50,cnt70,cnt90,cnt100; for(int i12;i19;i1) for(int i2i1;i29;i2) cnt4; for(int i11;i19;i1) for(int i2i1;i29;i2) for(int i3i2;i39;i3) cnt5; for(int i11;i19;i1) for(int i2i1;i29;i2) for(int i3i2;i39;i3) for(int i4i3;i49;i4) cnt7; for(int i11;i19;i1) for(int i2i1;i29;i2) for(int i3i2;i39;i3) for(int i4i3;i49;i4) for(int i5i4;i59;i5) cnt9; for(int i11;i19;i1) for(int i2i1;i29;i2) for(int i3i2;i39;i3) for(int i4i3;i49;i4) cnt10; System.out.println(cnt42*cnt52*cnt7cnt9cnt10); } }Q3import java.util.*; public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); String ssc.nextLine(); int[] hashnew int[26]; for(char c:s.toCharArray()) hash[c-A]; int mx0; for(int i0;i26;i) mxMath.max(mx,hash[i]); StringBuffer curnew StringBuffer(); for(int i0;i26;i) if(hash[i]mx) cur.append((char)(iA)); System.out.println(cur.toString()); sc.close(); } }Q4import java.util.*; public class Main { public static void main(String[] args) { Scanner scnew Scanner(System.in); int n sc.nextInt(); int[] numsnew int[n]; for (int i0;in;i) nums[i]sc.nextInt(); int[] nums2 nums.clone(); Arrays.sort(nums2); int midnums2[n/2]; int smaller0,bigger0; for(int i0;in;i){ if(nums[i]mid) smaller; if(nums[i]mid) bigger; } //对于中位数 int c1biggersmaller?0:1; //对于其他数 //一个原本mid的数提升到mid后比t小的数量会少1个因此1 int c2bigger(smaller-1)?0:1; for (int i0;in;i){ //根据是否是中位数算出最终目标值 int tmid(nums[i]mid?c1:c2); //计算针对当前数要满足biggersmaller需要加的最少数 if(nums[i]t) System.out.print(0 ); else System.out.print(t-nums[i] ); } sc.close(); } }