蓝桥杯2020省赛总结

A: 门牌制作

image-20201017155819375

1
2
3
4
5
6
7
8
9
10
11
12
public class A {
	public static void main(String[] args) {
		int res = 0;
		for (int i = 1; i <=2020 ; i++) {
			String s = String.valueOf(i);
			for(char c:s.toCharArray()){
				if(c == '2') res++;
			}
		}
		System.out.println(res);
	}
}

B: 寻找 2020

image-20201017160112315

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class B {
	public static void main(String[] args) throws FileNotFoundException {
		Scanner sc = new Scanner(new FileInputStream(new File("F:\\Git\\Algorithmic-training\\data\\2020.txt")));
		char[][] ss = new char[301][301];
		int n = 0;
		while(sc.hasNext()){
			String s = sc.nextLine();
			ss[n] = s.toCharArray();
			n++;
		}
		int res = 0;
		for (int i = 0; i < 300; i++) {
			for (int j = 0; j < 300; j++) {
				if(ss[i][j] == '2') res += dfs(ss,i,j);
			}
		}
		System.out.println(res);
	}
	static int dfs(char[][] ss,int i,int j){
		String s1 = "";
		String s2 = "";
		String s3 = "";
		for (int k = 0; k < 4; k++) {
			if(i+k >= 300) break;
			s1 += ss[i+k][j];
		}
		for (int k = 0; k < 4; k++) {
			if(j+k>=300) break;
			s2 += ss[i][j+k];
		}
		for (int k = 0; k < 4; k++) {
			if(i+k >= 300 || j+k>=300) break;
			s3 += ss[i+k][j+k];
		}
		int n = 0;
		if(s1.equals("2020")) n++;
		if(s2.equals("2020")) n++;
		if(s3.equals("2020")) n++;
		return n;
	}
}

C: 蛇形填数

image-20201017160254289

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class C {
	public static void main(String[] args) {
		/**
		 * (1 1)  1
		 * (2 2)  5 = 1+2+2
		 * (3 3)  13 = 1+2+3+4+3
		 * (4 4)  25 = 1+2+3+4+5+6+4
		 * ...
		 * (20,20) = E[2*(n-1)] + 20
		 */

		int res = 20;
		for (int i = 1; i <=38 ; i++) {
			res+=i;
		}
		System.out.println(res);
	}
}

D: 七段码

image-20201017160355007

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
public class D {
	public static void main(String[] args) {
		/**
		 * 枚举：
		 * 1 个 发光： 7
		 * 2 个 发光： 10  | ab bc cd de ef fa | g*4
		 * 3 个 发光： 10  | abc bcd cde def efa fab  + g*4
		 * 4 个 发光： C(7,3) - 6   |  cef ceb ceg 或 fbe fbg fbc
		 * 5 个 发光： C(7,2) - 2   |  ec 或 fb
		 * 6 个 发光： 7
		 * 7 个 发光： 1
		 */
		long res = 0;
		res = 7+10+10+C(7,3)-6+C(7,2)-2+7+1;
		System.out.println(res);
	}

	private static long C(int n, int k) {
		if(k>n) return 0;
		else if(k==0||k==n) return 1;
		else return C(n-1, k)+C(n-1, k-1);
	}
	public static int A(int n,int m) {
		if(n<m) return 0;
		int res = 1;
		for(int i = n-m+1;i<=n;i++) {
			res *= i;
		}
		return res;
	}
}

E: 排序

image-20201017160508487

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public class E {
	/**
	 * 全部按逆序排列的交换次数为 N! 且此时最短
	 * 多余的交换次数 通过 交换首字母与后面的某元素进行减少
	 * 如：交换 1 --> 2 1
	 *    交换 3 --> 3 2 1
	 *    交换 5 --> 4 3 2 1
	 *
	 *  .....
	 *  交换(105) 16 15 14 ....
	 *  交换100 --> 13 15 14 16 12 .......
	 *  对应字符即可
	 */
	public static void main(String[] args) {
		func();
	}
	static void func(){
		int n = 0;
		int lay = 1;
		while (n < 100) {
			System.out.println(n);
			 n += lay;
			 lay++;
		}
		System.out.println(n);
		System.out.println(lay);
	}
}

F: 成绩分析

image-20201017160743393

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import java.util.Scanner;
public class F {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int min = 200;
		int max = -1;
		double sum = 0;
		for (int i = 0; i < n; i++) {
			int num = sc.nextInt();
			sum += num;
			max = Math.max(max, num);
			min = Math.min(min, num);
		}
		System.out.println(max);
		System.out.println(min);
		System.out.printf("%.2f",sum/n);
	}
}

G: 单词分析

image-20201017160850978

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import java.util.Scanner;
public class G {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		String s = sc.next();
		int[] ws = new int[128];
		for(char c:s.toCharArray()){
			ws[c]++;
		}
		int max = 0;
		char w = 'a';
		for (int i = 0; i < ws.length; i++) {
			if(ws[i] > max){
				max = ws[i];
				w = (char) i;
			}
		}
		System.out.println(w);
		System.out.println(max);
	}
}

H: 数字三角形

image-20201017160953070

1
2
3
4
5
6
7
8
9
输入：
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
输出：
27
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
import java.util.Scanner;
public class H {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[][][] dp = new int[101][101][101];
		int[][] nums = new int[101][101];
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= i; j++) {
				nums[i][j] = sc.nextInt();
			}
		}
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= i; j++) {
				for (int k = 1; k <=i; k++) {
					dp[i][j][k] = Math.max(dp[i-1][j-1][k-1], dp[i-1][j][k]) + nums[i][j];
				}
			}
		}
		int res = 0;
		int m = n/2;
		if(n%2 == 1){
			for (int i = 1; i <=n; i++) {
				res = Math.max(res, dp[n][i][m+1]);
			}
		}
		if(n%2 == 0){
			for (int i = 1; i <=n; i++) {
				res = Math.max(res, dp[n][i][m]);
				res = Math.max(res, dp[n][i][m+1]);
			}
		}
		System.out.println(res);
	}
}

总结： 基于递推dp的变形，添加左右递推次数限制：

处理：多加一维，表示左边递推来的次数 + 1、右边递推来的次数 +0

dp[i][j][k] = Math.max(dp[i-1][j-1][k-1], dp[i-1][j][k]) + nums[i][j];

I: 子串分值和

image-20201017161422165

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
样例说明:
子串 f值
a 1
ab 2
aba 2
abab 2
ababc 3
b 1
ba 2
bab 2
babc 3
a 1
ab 2
abc 3
b 1
bc 2
c 1
评测用例规模与约定:
对于 20% 的评测用例，1 ≤ n ≤ 10；
对于 40% 的评测用例，1 ≤ n ≤ 100；
对于 50% 的评测用例，1 ≤ n ≤ 1000；
对于 60% 的评测用例，1 ≤ n ≤ 10000；
对于所有评测用例，1 ≤ n ≤ 100000。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
import java.util.Scanner;
public class I {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		String s = sc.next();
		int len = s.length();
		int res = 0;
		for (int i = 0; i < len; i++) {
			for (int j = i+1; j <= len; j++) {
				String tmp = s.substring(i,j);
				res += func(tmp);
			}
		}
		System.out.println(res);
	}
	static int func(String s){
		int[] w = new int[26];
		for(char c:s.toCharArray()){
			w[c-'a']++;
		}
		int res = 0;
		for(int n:w){
			if(n > 0) res++;
		}
		return res;
	}	
}

暴力拿分走人….

J: 装饰珠

复杂模拟 give up….