Day6

第一题

第三届2012年蓝桥杯省赛

巧排扑克牌

C++高职组第4题

填空题

其实本质一直遵循 “隔一个未知的数字加一个数” :

找规律：
第一次：	?	1	?	2	?	3	?	4	?	5	?	6	?
第二次：	7	1	?	2	8	3	?	4	9	5	?	6	10
第三次：	7	1	?	2	8	3	11	4	9	5	?	6	10
第四次：	7	1	12	2	8	3	11	4	9	5	?	6	10
第五次：	7	1	12	2	8	3	11	4	9	5	13	6	10

直接将答案输出即可，本题是很老的题，出题当时还不是很严谨，所以并没有说输出还要加空格，我们要注意这点。

public class Main {
	public static void main(String[] args) {
		System.out.print("7, A, Q, 2, 8, 3, J, 4, 9, 5, K, 6, 10");
	}
}

模拟，按照题意顺序模拟即可。

import java.util.ArrayList;

public class Main {
    public static void main(String[] args) {
        String[] s = {"A", "2", "3", "4", "5", "6", "7", "8", "9", "10", "J", "Q", "K"};
        ArrayList<String> list = new ArrayList<>();
        for (int i = s.length - 1; i >= 0; i--) {
            list.add(s[i]);
            list.add(list.remove(0));
        }
        for (int i = list.size() - 1; i >= 0; i--) {
            if (i == 0) System.out.print(list.get(i));
            else System.out.print(list.get(i) + ", "); // 输出要加空格
        }
    }
}

第二题

第十届2019年蓝桥杯国赛

质数拆分

C++B组第2题

直接暴力枚举所有方案，用了时间复杂度 $O (N)$ 的筛法还是超时，因为每个质数只能用1次，所以这道题其实是一个01背包问题。

闫式DP分析法

public class Main {

    static final int N = 2030;
    static int[] primes = new int[N]; // 存所有的质数
    static int cnt = 1; // 存质数的个数
    static boolean[] st = new boolean[N]; // 当前数有没有被筛过 false没有被筛过 true表示筛过
    static long[][] f = new long[N][N]; // 记录方案数

    public static void main(String[] args) {
        get_primes(2019);

        f[0][0] = 1; // 容量为0也是一种方案
        for(int i = 1; i < cnt; i++){
            for(int j = 0; j <= 2019; j++){ // 背包容积最小为0，所以j从0开始
                f[i][j] = f[i - 1][j]; // 不选i
                if (j >= primes[i]) f[i][j] += f[i - 1][j - primes[i]]; // 如果当前可以容下i，那么选i
            }
        }
        System.out.println(f[cnt - 1][2019]);
    }

    // 埃式筛法
    private static void get_primes(int n) {
        for (int i = 2; i <= 2019; i ++ ) {
            if (!st[i]) {
                primes[cnt++] = i; // 存放质数
                for (int j = i + i; j <= 2019; j += i) st[j] = true;
            }
        }
    }
}