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