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;public class Main {    public static void main(String[] args) {    Scanner sc = new Scanner(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$ 个蒸笼，每个蒸笼的包子分别为 A 1 , A 2 . . . A n A_1,A_2...A_n A1​,A2​...An​，且他们的最大公约数是 $d$，且 $d>1$，所有数都是 $d$ 的倍数，如果一个数不能被 $d$ 整数，则说明这个数也一定不能被 A 1 , A 2 . . . A n A_1,A_2...A_n A1​,A2​...An​ 凑出来，所以此时会有正无穷 $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$ 的定理，当 $gcd(a,b)=1$ 时，最大不能表示的数是：$(a-1)(b-1)-1$， 当有 $N$ 个数时定理也同样适用，当数变多时，这个上界必然会更小，因为可选的数变多了，因为 $1\le N\le 100$，小于 $100$ 中最大互质的两个数是 $98,99$，所以这里的上界我们取到 $10000$ 即可。

此时这个问题就变成了完全背包问题，在 $10000$ 以内有多少个数不能被组合出来。

闫式DP分析法

此时的状态转移方程：$f(i,j)=f(i-1,j)|f(i-1,j-A)|f(i-1,j-2A)|...|f(i-1,j\le 0)$

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

我们做一下 $j$ 的变量变换：$f(i,j-A)=f(i-1,j-A)|f(i-1,j-2A)|f(i-1,j-3A)|...$

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

状态转移方程优化为：$f(i,j)=f(i-1,j)|f(i,j-A)$

import java.util.Scanner;public class Main { static final int N = 110, M = 10010;    static int[] a = new int[N];    static boolean[][] f = new boolean[N][M]; public static void main(String[] args) {    Scanner sc = new Scanner(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); }    } private static int gcd(int a, int b) { return b != 0 ? gcd(b, a % b) : a;    }}

我们发现我们的方程第 $i$ 维只依赖于第 $i$ 和 $i-1$ 项，所以我们可以将数组优化成一维：

import java.util.Scanner;public class Main { static final int N = 110, M = 10010;    static int[] a = new int[N];    static boolean[] f = new boolean[M]; public static void main(String[] args) {    Scanner sc = new Scanner(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); }    } private static int gcd(int a, int b) { return b != 0 ? gcd(b, a % b) : a;    }}

第三题

第十届2019年蓝桥杯国赛

求值

C++B组第4题

填空题

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

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

public class Main {public static void main(String[] args) {for(int i = 1; ; i++) {if(cnt(i) == 100) { // 有100个约数的最小数System.out.println(i);break;}}}// 求约数private static int cnt(int a){int ans = 0;for (int i = 1; i <= a; i++)if (a % i == 0) ans++;return ans;}}

提交代码：

public class Main {public static void main(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 q = new LinkedList(); q.offer(a); HashMap dist = new HashMap(); dist.put(a, 0); while (!q.isEmpty()) {     StringBuffer t = new StringBuffer(q.poll());     int dis = dist.get(t.toString());     if (t.toString().equals(b)) {  return dis;     }     int pos = t.indexOf("*");     for (int i = 0; i = 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;    }}