蓝桥杯31天冲刺打卡题解（Day11）

Day11

第一题

第十一届2020年蓝桥杯国赛

天干地支

JavaC组第6题

模拟

一道很复杂，但又不完全复杂的模拟题。

我们可以写一堆

if/else

用循环来判断，但我们其实可以找到其中的规律：在

2020

年时，是庚子年，我们判断一下

0000

年是什么年，我们可以发现天干是以

10

为单位的，利用

2020 % 10 = 0

发现

0000

年的天干也是庚，地支是以

12

为单位的，计算

2020 % 12 = 4

，所以地支要往前推

4

年，地支为申，即

0000

年为庚申年，那么根据模拟法可知：

year % 10 = 0 时，天干为庚

year % 10 = 1 时，天干为庚的下一个 辛

以此类推…

year % 10 = 0 时，地支为申

year % 10 = 1 时，地支为申的下一个 酉

所以我们可以来两个数组存储天干和地支，从

0000

年开始存储，这样就可以根据

%

的余数来判断当前的年份了。

import java.util.Scanner;publicclassMain{publicstaticvoidmain(String[] args){
        Scanner sc =newScanner(System.in);int year = sc.nextInt();
        String[] tg ={"geng","xin","ren","gui","jia","yi","bing","ding","wu","ji"};
        String[] dz ={"shen","you","xu","hai","zi","chou","yin","mao","chen","si","wu","wei"};
        System.out.println(tg[year %10]+ dz[year %12]);}}

第二题

第八届2017年蓝桥杯省赛

包子凑数

JavaB组第8题

完全背包问题

假设我们有

    N
   
  
  
   N
  
 
N 个蒸笼，每个蒸笼的包子分别为 
 
  
   
    
     A
    
    
     1
    
   
   
    ,
   
   
    
     A
    
    
     2
    
   
   
    .
   
   
    .
   
   
    .
   
   
    
     A
    
    
     n
    
   
  
  
   A_1,A_2...A_n
  
 
A1​,A2​...An​，且他们的最大公约数是 
 
  
   
    d
   
  
  
   d
  
 
d，且 
 
  
   
    d
   
   
    >
   
   
    1
   
  
  
   d>1
  
 
d>1，所有数都是 
 
  
   
    d
   
  
  
   d
  
 
d 的倍数，如果一个数不能被 
 
  
   
    d
   
  
  
   d
  
 
d 整数，则说明这个数也一定不能被 
 
  
   
    
     A
    
    
     1
    
   
   
    ,
   
   
    
     A
    
    
     2
    
   
   
    .
   
   
    .
   
   
    .
   
   
    
     A
    
    
     n
    
   
  
  
   A_1,A_2...A_n
  
 
A1​,A2​...An​ 凑出来，所以此时会有正无穷 
 
  
   
    I
   
   
    N
   
   
    F
   
  
  
   INF
  
 
INF 个数凑不出来。

当

    g
   
   
    c
   
   
    d
   
   
    (
   
   
    
     A
    
    
     1
    
   
   
    ,
   
   
    
     A
    
    
     2
    
   
   
    .
   
   
    .
   
   
    .
   
   
    
     A
    
    
     n
    
   
   
    )
   
   
    =
   
   
    1
   
  
  
   gcd(A_1,A_2...A_n)=1
  
 
gcd(A1​,A2​...An​)=1 时，不能凑出来的数一定是有限个，这是依据裴蜀定理，裴蜀定理是基于两个数 
 
  
   
    a
   
   
    ,
   
   
    b
   
  
  
   a,b
  
 
a,b 的定理，当 
 
  
   
    g
   
   
    c
   
   
    d
   
   
    (
   
   
    a
   
   
    ,
   
   
    b
   
   
    )
   
   
    =
   
   
    1
   
  
  
   gcd(a,b) = 1
  
 
gcd(a,b)=1 时，最大不能表示的数是：
 
  
   
    (
   
   
    a
   
   
    −
   
   
    1
   
   
    )
   
   
    (
   
   
    b
   
   
    −
   
   
    1
   
   
    )
   
   
    −
   
   
    1
   
  
  
   (a-1)(b-1)-1
  
 
(a−1)(b−1)−1， 当有 
 
  
   
    N
   
  
  
   N
  
 
N 个数时定理也同样适用，当数变多时，这个上界必然会更小，因为可选的数变多了，因为 
 
  
   
    1
   
   
    ≤
   
   
    N
   
   
    ≤
   
   
    100
   
  
  
   1\leq N \leq 100
  
 
1≤N≤100，小于 
 
  
   
    100
   
  
  
   100
  
 
100 中最大互质的两个数是 
 
  
   
    98
   
   
    ,
   
   
    99
   
  
  
   98,99
  
 
98,99，所以这里的上界我们取到 
 
  
   
    10000
   
  
  
   10000
  
 
10000 即可。

此时这个问题就变成了完全背包问题，在

    10000
   
  
  
   10000
  
 
10000 以内有多少个数不能被组合出来。

闫式DP分析法

此时的状态转移方程：

    f
   
   
    (
   
   
    i
   
   
    ,
   
   
    j
   
   
    )
   
   
    =
   
   
    f
   
   
    (
   
   
    i
   
   
    −
   
   
    1
   
   
    ,
   
   
    j
   
   
    )
   
   
    ∣
   
   
    f
   
   
    (
   
   
    i
   
   
    −
   
   
    1
   
   
    ,
   
   
    j
   
   
    −
   
   
    
     A
    
    
     i
    
   
   
    )
   
   
    ∣
   
   
    f
   
   
    (
   
   
    i
   
   
    −
   
   
    1
   
   
    ,
   
   
    j
   
   
    −
   
   
    2
   
   
    
     A
    
    
     i
    
   
   
    )
   
   
    ∣
   
   
    .
   
   
    .
   
   
    .
   
   
    ∣
   
   
    f
   
   
    (
   
   
    i
   
   
    −
   
   
    1
   
   
    ,
   
   
    j
   
   
    ≤
   
   
    0
   
   
    )
   
  
  
   f(i,j)=f(i-1,j)|f(i-1,j-A_i)|f(i-1,j-2A_i)|...|f(i-1,j\leq0)
  
 
f(i,j)=f(i−1,j)∣f(i−1,j−Ai​)∣f(i−1,j−2Ai​)∣...∣f(i−1,j≤0)

时间复杂度为

    O
   
   
    (
   
   
    
     N
    
    
     3
    
   
   
    )
   
  
  
   O(N^3)
  
 
O(N3)，状态的数量是 
 
  
   
    
     N
    
    
     2
    
   
  
  
   N^2
  
 
N2 个，转移的数量是 
 
  
   
    N
   
  
  
   N
  
 
N 个，显然是需要优化一下的，一般的背包问题时间复杂度是 
 
  
   
    O
   
   
    (
   
   
    
     N
    
    
     2
    
   
   
    )
   
  
  
   O(N^2)
  
 
O(N2)。

我们做一下

    j
   
  
  
   j
  
 
j 的变量变换：
 
  
   
    f
   
   
    (
   
   
    i
   
   
    ,
   
   
    j
   
   
    −
   
   
    
     A
    
    
     i
    
   
   
    )
   
   
    =
   
   
    f
   
   
    (
   
   
    i
   
   
    −
   
   
    1
   
   
    ,
   
   
    j
   
   
    −
   
   
    
     A
    
    
     i
    
   
   
    )
   
   
    ∣
   
   
    f
   
   
    (
   
   
    i
   
   
    −
   
   
    1
   
   
    ,
   
   
    j
   
   
    −
   
   
    2
   
   
    
     A
    
    
     i
    
   
   
    )
   
   
    ∣
   
   
    f
   
   
    (
   
   
    i
   
   
    −
   
   
    1
   
   
    ,
   
   
    j
   
   
    −
   
   
    3
   
   
    
     A
    
    
     i
    
   
   
    )
   
   
    ∣
   
   
    .
   
   
    .
   
   
    .
   
  
  
   f(i,j-A_i)=f(i-1,j-A_i)|f(i-1,j-2A_i)|f(i-1,j-3A_i)|...
  
 
f(i,j−Ai​)=f(i−1,j−Ai​)∣f(i−1,j−2Ai​)∣f(i−1,j−3Ai​)∣...

此时这个等式可以替换为第一个等式从第二项开始后面的所有项：

状态转移方程优化为：

    f
   
   
    (
   
   
    i
   
   
    ,
   
   
    j
   
   
    )
   
   
    =
   
   
    f
   
   
    (
   
   
    i
   
   
    −
   
   
    1
   
   
    ,
   
   
    j
   
   
    )
   
   
    ∣
   
   
    f
   
   
    (
   
   
    i
   
   
    ,
   
   
    j
   
   
    −
   
   
    
     A
    
    
     i
    
   
   
    )
   
  
  
   f(i,j)=f(i-1,j)|f(i,j-A_i)
  
 
f(i,j)=f(i−1,j)∣f(i,j−Ai​)

import java.util.Scanner;publicclassMain{staticfinalint N =110, M =10010;staticint[] a =newint[N];staticboolean[][] f =newboolean[N][M];publicstaticvoidmain(String[] args){
        Scanner sc =newScanner(System.in);int n = sc.nextInt();int d =0;for(int i =1; i <= n; i++){
            a[i]= sc.nextInt();
            d =gcd(d, a[i]);}if(d !=1) System.out.println("INF");// 最大公约数不为1 有无限多个数凑不出来else{
            f[0][0]=true;// 0件物品 体积为0时也是一种方案for(int i =1; i <= n; i++){for(int j =0; j < M; j++){
                    f[i][j]= f[i -1][j];// 第一项一定存在if(j >= a[i]) f[i][j]|= f[i][j - a[i]];// 第二项不一定存在 用或"|"}}int res =0;for(int i =0; i < M; i++){if(!f[n][i]) res++;}
            System.out.println(res);}}privatestaticintgcd(int a,int b){return b !=0?gcd(b, a % b): a;}}

我们发现我们的方程第

    i
   
  
  
   i
  
 
i 维只依赖于第 
 
  
   
    i
   
  
  
   i
  
 
i 和 
 
  
   
    i
   
   
    −
   
   
    1
   
  
  
   i-1
  
 
i−1 项，所以我们可以将数组优化成一维：

import java.util.Scanner;publicclassMain{staticfinalint N =110, M =10010;staticint[] a =newint[N];staticboolean[] f =newboolean[M];publicstaticvoidmain(String[] args){
        Scanner sc =newScanner(System.in);int n = sc.nextInt();int d =0;for(int i =1; i <= n; i++){
            a[i]= sc.nextInt();
            d =gcd(d, a[i]);}if(d !=1) System.out.println("INF");// 最大公约数不为1 有无限多个数凑不出来else{
            f[0]=true;// 0件物品 体积为0时也是一种方案for(int i =1; i <= n; i++){for(int j = a[i]; j < M; j++){
                    f[j]|= f[j - a[i]];}}int res =0;for(int i =0; i < M; i++){if(!f[i]) res++;}
            System.out.println(res);}}privatestaticintgcd(int a,int b){return b !=0?gcd(b, a % b): a;}}

第三题

第十届2019年蓝桥杯国赛

求值

C++B组第4题

填空题

目的是找到一个最小数，且它的约数个数是100。

简单的暴力打表题，我们在编译器上跑，在oj上提交结果的代码即可。

publicclassMain{publicstaticvoidmain(String[] args){for(int i =1;; i++){if(cnt(i)==100){// 有100个约数的最小数
                System.out.println(i);break;}}}// 求约数privatestaticintcnt(int a){int ans =0;for(int i =1; i <= a; i++)if(a % i ==0) ans++;return ans;}}

提交代码：

publicclassMain{publicstaticvoidmain(String[] args){
        System.out.println(45360);}}

第四题

第八届2017年蓝桥杯省赛

青蛙跳杯子

JavaC组第9题

bfs

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Main {
    static int l;
    static int[] dx = {1, -1, 2, -2, 3, -3};
    static String a = "";
    static String b = "";
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        a = in.next();
        b = in.next();
        l = a.length();
        System.out.println(bfs());
    }
    private static int bfs() {
        Queue<String> q = new LinkedList<>();
        q.offer(a);
        HashMap<String, Integer> dist = new HashMap<>();
        dist.put(a, 0);
        while (!q.isEmpty()) {
            StringBuilder t = new StringBuilder(q.poll());
            int dis = dist.get(t.toString());
            if (t.toString().equals(b)) {
                return dis;
            }
            int pos = t.indexOf("*");
            for (int i = 0; i < 6; i ++) {
                int nx = pos + dx[i];
                if (nx >= 0 && nx < l) {
                    char x = t.toString().charAt(pos);
                    char y = t.toString().charAt(nx);
                    t.setCharAt(pos, y);
                    t.setCharAt(nx, x);
                    if (!dist.containsKey(t.toString())) {
                        dist.put(t.toString(), dis + 1);
                        q.offer(t.toString());
                    }
                    x = t.toString().charAt(pos);
                    y = t.toString().charAt(nx);
                    t.setCharAt(pos, y);
                    t.setCharAt(nx, x);
                }
            }
        }
        return -1;
    }
}