Day6

第一题

第三届2012年蓝桥杯省赛

巧排扑克牌

C++高职组第4题

填空题

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

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

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;     } }    }}

第三题

第九届2018年蓝桥杯真题

日志统计

本题用了排序 + 双指针算法，题解在这篇文章的第一题：蓝桥杯AcWing学习笔记 6-1双指针的学习

第四题

第九届2018年蓝桥杯真题

递增三元组

本题是一道枚举题，之前写过题解在这篇文章的第二题：蓝桥杯AcWing学习笔记 4-1枚举的学习

暴力解法以及前缀和优化都有写。

第五题

第十届2019年蓝桥杯真题

外卖店优先级

本题是一道较难的模拟题，题解在之前写的这篇的最后一题：蓝桥杯AcWing学习笔记 4-2模拟的学习