#|蓝桥杯31天冲刺打卡题解（Day11）蓝桥杯|java|算法|动态规划|bf

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题
完全背包问题
【#|蓝桥杯31天冲刺打卡题解（Day11）】假设我们有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 ) ∣ f ( i ? 1 , j ? 2 A ) ∣ . . . ∣ f ( i ? 1 , j ≤ 0 ) f(i,j)=f(i-1,j)|f(i-1,j-A)|f(i-1,j-2A)|...|f(i-1,j\leq0) f(i,j)=f(i?1,j)∣f(i?1,j?A)∣f(i?1,j?2A)∣...∣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 ) = f ( i ? 1 , j ? A ) ∣ f ( i ? 1 , j ? 2 A ) ∣ f ( i ? 1 , j ? 3 A ) ∣ . . . f(i,j-A)=f(i-1,j-A)|f(i-1,j-2A)|f(i-1,j-3A)|... 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 ) f(i,j)=f(i-1,j)|f(i,j-A) 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 维只依赖于第i i i 和i ? 1 i-1 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 < 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; } }