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;
}
}
本文转载自: https://blog.csdn.net/weixin_53407527/article/details/123587033
版权归原作者 小成同学_ 所有， 如有侵权，请联系我们删除。
版权归原作者 小成同学_ 所有， 如有侵权，请联系我们删除。