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)$ $TLE$，前缀和优化 $O(N^2)$ $TLE$ ，以及 前缀和+数学优化 $O(N)$ $AC$ 的题解都有写。

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