文章目录

• Day9
• • 第一题
  • • 第九届2018年蓝桥杯国赛
    • 最大乘积
  • 第二题
  • • 第十一届2020年蓝桥杯国赛
    • 阶乘约数
  • 第三题
  • • 第十一届2020年蓝桥杯国赛
    • 含2天数
  • 第四题
  • • 第八届2017年蓝桥杯真题
    • K倍区间

Day9

第一题

第九届2018年蓝桥杯国赛

最大乘积

JavaB组第2题

填空题

dfs枚举全排列，有很多细节要考虑，比如去重，除0。

import java.util.HashSet;import java.util.Set;public class Main {    static int max = Integer.MIN_VALUE;    public static void main(String[] args) { dfs("123456789".toCharArray(), 0); System.out.println(max);    }    private static void dfs(char[] a, int k) { if (k == a.length) {     int temp = 0;     // 分割字符串     String s1 = String.valueOf(a);     for (int i = 1; i <= a.length; i++) {  String s2 = s1.substring(0, i);  String s3 = s1.replace(s2, "0");  int t = Integer.parseInt(s2);  int nub = Integer.parseInt(s3);  temp = t * nub;  if (max < temp && check_reduplicate(temp) && check_zero(temp)) {      max = temp;  }     } } // 全排列 for (int i = k; i < a.length; i++) {     char t = a[i];     a[i] = a[k];     a[k] = t;     dfs(a, k + 1);     t = a[i]; // 回溯     a[i] = a[k];     a[k] = t; }    }    // 去重    private static boolean check_reduplicate(int num) { String s = String.valueOf(num); Set<String> set = new HashSet<>(); for (int i = 0; i < s.length(); i++) {     if (!set.add(s.charAt(i) + "")) return false; } return true;    }    // 去0    private static boolean check_zero(int num) { String s = String.valueOf(num); return !s.contains("0");    }}

可惜超时了，但问题不大，是填空题，我们把结果交上去就好了。

public class Main {    public static void main(String[] args) { System.out.println(839542176);    }}

第二题

第十一届2020年蓝桥杯国赛

阶乘约数

JavaB组第3题

填空题

这道题有点难我自己没做，贴的蓝桥oj平台的代码。

public class Main {    public static void main(String[] args) { int[] st = new int[101]; // 从1到100 for (int i = 1; i <= 100; i++) {     int k = i; // 不能让分解结果影响循环     for (int j = 2; j * j <= k; j++) {  // i 为被分解数  // 以sqrt(n)为界 如果一个数在左边，必然有一个数在右边，不用求完 只需要求一半(i*i)就行 就可以判断是不是质数  if (k % j == 0) {      // 不是质数 开始分解      while (k % j == 0) {   k /= j;   // 对应位置次数+1   st[j]++;      }  }     }     if (k > 1) {  st[k]++;     } } long res = 1; for (int i = 0; i < st.length; i++) {     if (st[i] != 0) {  res *= (st[i] + 1);     } } System.out.println(res);    }}

第三题

第十一届2020年蓝桥杯国赛

含2天数

JavaA组第2题

填空题

模拟，利用contains方法判断字符串中是否包含"2"。

public class Main {    public static void main(String[] args) { int cnt = 0; int[] days = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}; for (int year = 1900; year <= 9999; year++) {     if (year % 4 == 0 && year % 100 != 0 || year % 400 == 0) {  days[1] = 29;     } else days[1] = 28;     for (int month = 1; month <= 12; month++) {  for (int day = 1; day <= days[month - 1]; day++) {      if (String.valueOf(year).contains("2")   || String.valueOf(month).contains("2")   || String.valueOf(day).contains("2")) cnt++;  }     } } System.out.println(cnt);    }}

第四题

第八届2017年蓝桥杯真题

K倍区间

之前写过这道题的题解，暴力 O ( N 2 ) O(N^2) O(N2) $TLE$，前缀和优化 O ( N 2 ) O(N^2) O(N2) $TLE$ ，以及 前缀和+数学优化 $O(N)$ $AC$ 的题解都有写。

在该文的最后一题，链接：蓝桥杯AcWing学习笔记 2-2前缀和的学习