第十一届蓝桥杯国赛JavaB组题解

理想-

1464人浏览 · 2023-06-05 22:00:04

理想- · 2023-06-05 22:00:04 发布

A. 美丽的2

在这里插入图片描述
思路：

枚举 1 到 2020 的每个数，依次判断即可。

代码：

public class Main {
	
	public static boolean check(int x) {
		while (x != 0) {
			if (x % 10 == 2) return true;
			x /= 10;
		}
		return false;
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int cnt = 0;
		for (int i = 1; i <= 2020; i++) 
			if (check(i))
				cnt++;
		
		System.out.println(cnt);
	}

}

B. 扩散

在这里插入图片描述
解法一：（比较慢但是容易想）

$b f s$ ，先将给出的点加入队列中，并且加到集合里。记录扩散的步数，初始化为2020，然后对队列中的每一个同一层的节点在四个方向上扩散，当扩散的点不在集合里时，把它加到队列里，并加到集合里。每扩散一层就减1，当步数为0时，就结束 $b f s$ ，输出答案。

这种做法比较慢，当时跑了好几分钟，不过填空题也无关紧要了。

代码：

package L11;

import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Objects;
import java.util.Queue;

public class B {
	
	static final int N = 10000;
	static long ans = 0;
	static int[] dx = {-1, 0, 1, 0}, dy = {0, 1, 0, -1};
	static HashSet<Point> set = new HashSet<Point>();
	static Queue<Point> queue = new LinkedList<Point>();
	static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
	
	public static void bfs() {
		int count = 2020;
		while (!queue.isEmpty()) {
			for (int i = queue.size(); i >= 1; i--) {
				Point p = queue.poll();
				int x = p.x, y = p.y;
				for (int u = 0; u < 4; u++) {
					int a = x + dx[u], b = y + dy[u];
					if (set.contains(new Point(a, b))) continue;
					set.add(new Point(a, b));
					queue.add(new Point(a, b));
				}
			}
			
			count--;
			System.out.println(count);
			if (count == 0) break;
		}
	}
	

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		queue.add(new Point(0, 0));
		queue.add(new Point(2020, 11));
		queue.add(new Point(11, 14));
		queue.add(new Point(2000, 2000));
		
		set.add(new Point(0, 0));
		set.add(new Point(2020, 11));
		set.add(new Point(11, 14));
		set.add(new Point(2000, 2000));

		bfs();
		System.out.println(set.size());
		
	}
	
	static class Point {
		int x, y;
		Point(int x, int y) {
			this.x = x;
			this.y = y;
		}
		@Override
		public int hashCode() {
			return Objects.hash(x, y);
		}
		@Override
		public boolean equals(Object obj) {
			if (this == obj)
				return true;
			if (obj == null)
				return false;
			if (getClass() != obj.getClass())
				return false;
			Point other = (Point) obj;
			return x == other.x && y == other.y;
		}
		
	}

}

解法2：

统计在扩散范围内的点与那几个点距离小于2020的个数。

代码：

package L11;

public class B_2 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub

		int ans = 0;
		for (int i = 0 - 2020; i <= 2020 + 2020; i++) 
			for (int j = 0 - 2020; j <= 2020 + 2020; j++) {
				if (Math.abs(i - 0) + Math.abs(j - 0) <= 2020 || Math.abs(i - 2020) + Math.abs(j - 11) <= 2020 || 
						Math.abs(i - 11) + Math.abs(j - 14) <= 2020 || Math.abs(i - 2000) + Math.abs(j - 2000) <= 2020)
					ans++;
			}
		
		System.out.println(ans);
	}

}

C. 阶乘约数

在这里插入图片描述

思路：

复习了一下试除法求质约数个数与约数个数。

给定一个数 $N$ ， $p_i$ 为 $N$ 的质约数，则可以表示为:
$N=p1α1×p2α2×p3α3×...×pkαkN=p_{1}^{\alpha_1}\times p_{2}^{\alpha_2} \times p_{3}^{\alpha_3}\times... \times p_{k}^{\alpha_k}$
$N$ 的每一个约数 $d_i$ ，可以表示为:
$di=p1β1×p2β2×p3β3×...×pkβkd_i=p_{1}^{\beta_1}\times p_{2}^{\beta_2} \times p_{3}^{\beta_3}\times... \times p_{k}^{\beta_k}$
其中， $\le \beta_i \le \alpha_i$ ， $βi\beta_i$ 的选法有 $\sim \alpha_i$ ，共有 $(αi+1)(\alpha_i + 1)$ 种选法，根据排列组合原理，约数个数为：
$(α1+1)×(α2+1)×(α3+1)×...×(αk+1)(\alpha_1 + 1) \times (\alpha_2 + 1) \times (\alpha_3 + 1) \times ... \times (\alpha_k + 1)$

求 $\sim 100$ 的质因数以及每个质因数的个数，每个质因数的个数加一相乘即可，答案为 $∏1k(αi+1)\displaystyle\prod^{k}_{1}{(\alpha_i + 1)}$ 。

代码：

public class Main {
    
    static int[] p = new int[110];

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        for (int i = 2; i <= 100; i++) {
            int x = i;
            for (int j = 2; j <= i / j; j++) {
                if (x % j == 0) {
                    while (x % j == 0) {
                        x /= j;
                        p[j]++;
                    }
                }
            }
            if (x > 1) p[x]++;
        }
        
        long ans = 1;
        for (int i = 2; i < 100; i++) ans *= (p[i] + 1);
        System.out.println(ans);
    }

}

D. 本质上升序列

在这里插入图片描述
解法1：

暴力枚举。因为本质上升序列最长为26，所有的序列个数为 $2^{26}$ ，可以二进制枚举所有的序列，判断在字符串中是否存在该序列，如果存在答案就加一，时间复杂度为 $O(2^{26} × 200)$ 。

代码：

public class D {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int ans = 0;
		//String s = "lanqiao";
		String s = "tocyjkdzcieoiodfpbgcncsrjbhmugdnojjddhllnofawllbhfiadgdcdjstemphmnjihecoapdjjrprrqnhgccevdarufmliqijgihhfgdcmxvicfauachlifhafpdccfseflcdgjncadfclvfmadvrnaaahahndsikzssoywakgnfjjaihtniptwoulxbaeqkqhfwl";
		for (int i = 1; i < (1 << 26); i++) {
			StringBuffer sb = new StringBuffer();
 			for (int j = 0; j < 26; j++) {
				if (((i >> j) & 1) == 1)
					sb.append((char)('a' + j));
			}
 			int j = 0;
 			for (int k = 0; k < s.length(); k++) {
 				if (s.charAt(k) == sb.charAt(j)) {
 					j++;
 					if (j == sb.length()) {
 	 					ans++;
 	 					break;
 	 				}
 				}
 				
 			}
		}
		System.out.println(ans);
	}
}

解法2：

动态规划，分析如下，时间复杂度为 $O (N)$
在这里插入图片描述

代码：

public class Main {
	
	static int[] dp = new int[200];

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		String s = "tocyjkdzcieoiodfpbgcncsrjbhmugdnojjddhllnofawllbhfiadgdcdjstemphmnjihecoapdjjrprrqnhgccevdarufmliqijgihhfgdcmxvicfauachlifhafpdccfseflcdgjncadfclvfmadvrnaaahahndsikzssoywakgnfjjaihtniptwoulxbaeqkqhfwl";
		char[] str = s.toCharArray();
		for (int i = 0; i < 200; i++) {
			dp[i] = 1;
			for (int j = 0; j < i; j++) {
				if (str[i] > str[j]) dp[i] += dp[j];
				if (str[i] == str[j]) dp[i] -= dp[j];
			}
		}
		
		long ans = 0;
		for (int i = 0; i < 200; i++) ans += dp[i];
		System.out.println(ans);
	}
}

E. 玩具蛇

在这里插入图片描述
思路：

从 $\times 4$ 的小方格中每一个位置放置 $1$ , 接着按上下左右 4 个方向 $df s$ 。在搜索的过程中记得回溯，因为求的是方案的个数。枚举每一个位置都要先标记起点，搜索之后再删除标记。

代码：

public class Main {
	
	static int ans;
	static int[] dx = {-1, 0, 1, 0}, dy = {0, 1, 0, -1};
	static boolean[][] st = new boolean[4][4];
	
	public static void dfs(int x, int y, int ch) {
		if (ch == 16) {
			ans++;
			return;
		}
		for (int i = 0; i < 4; i++) {
			int a = x + dx[i], b = y + dy[i];
			if (a < 0 || a >= 4 || b < 0 || b >= 4) continue;
			if (st[a][b]) continue;
			
			st[a][b] = true;
			dfs(a, b, ch + 1);
			st[a][b] = false;
		}
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		for (int i = 0; i < 4; i++) 
			for (int j = 0; j < 4; j++) {
				st[i][j] = true;
				dfs(i, j, 1);
				st[i][j] = false;
			}
				
		System.out.println(ans);
	}

}

F. 蓝肽子序列

在这里插入图片描述

思路：

LCS问题，将字符串分割成一个个以大写字母为首的的字符串，再根据LCS的方法进行求解。

代码：

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;

public class Main {
    
    static final int N = 1010;
    static int[][] f = new int[N][N];
    static String[] a = new String[N], b = new String[N];
    
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException {
        // TODO Auto-generated method stub
        char[] A = br.readLine().toCharArray();
        char[] B = br.readLine().toCharArray();
        
        int n = 0, m = 0;
        for (int i = 0; i < A.length; i++) {
            if ('A' <= A[i] && A[i] <= 'Z') n++;
            a[n] += A[i];
        }
        
        for (int i = 0; i < B.length; i++) {
            if ('A' <= B[i] && B[i] <= 'Z') m++;
            b[m] += B[i];
        }
        
        for (int i = 1; i <= n; i++) 
            for (int j = 1; j <= m; j++) {
                if (a[i].equals(b[j])) f[i][j] = f[i - 1][j - 1] + 1;
                else f[i][j] = Math.max(f[i][j - 1], f[i - 1][j]);
            }
        
        System.out.println(f[n][m]);
    }

}

H. 画廊

在这里插入图片描述

思路：

十三届蓝桥杯Java组曾经考了个跟这个类似的题目，换汤不换药。以下是分析过程：

在这里插入图片描述
状态 $f (i, j, k)$ 表示所有走过 $u_i$ 、 $v_j$ 的所有走法的集合，属性为 $min$ 。

当 $k = 0$ 时，表示当前在画廊左侧；当 $k = 1$ 时，表示当前在画廊右侧

根据上一个点在画廊左侧还是在画廊右侧上可以划分状态计算，每一类又有两种情况：上一个点从画廊左侧转移过来还是从画廊右侧转移过来分别取 $min$ 即可。

重点在于初始化，状态转移方程为：
$\begin{cases} f(i, j,0) = min\{f(i - 1, j, 0) + u_i - u_{i - 1}, f(i - 1, j, 1) + dist(u_i, v_j) \} \\ f(i, j,1) = min\{f(i, j - 1, 0) + dist(u_i, v_j), f(i , j - 1, 1) +v_j - v_{j - 1} \} \\ \end{cases}$

通过 $O (L R)$ 的时间复杂度可以求解。

代码：

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
import java.util.Arrays;

public class Main {
    
    static final int N = 510;
    static double[][][] f = new double[N][N][2];
    static int[] u = new int[N], v = new int[N];
    static int l, r, d, w;
    
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
    static StreamTokenizer in = new StreamTokenizer(br);
    
    public static int nextInt() throws IOException {
        in.nextToken();
        return (int)in.nval;
    }

    public static void main(String[] args) throws IOException {
        // TODO Auto-generated method stub
        l = nextInt();
        r = nextInt();
        d = nextInt();
        w = nextInt();
        
        for (int i = 1; i <= l; i++) u[i] = nextInt();
        for (int i = 1; i <= r; i++) v[i] = nextInt();
        
        // 初始化画廊左侧第一个位置的距离
        f[1][0][0] = Math.hypot(w * 1.0 / 2, u[1]);
        // 非法情况
        f[1][0][1] = 1e18;
        for (int i = 2; i <= l; i++) {
        	// 依次计算画廊左侧上的每个作品的距离
            f[i][0][0] = f[i - 1][0][0] + u[i] - u[i - 1];
            // 非法情况
            f[i][0][1] = 1e18;
        }
        
         // 非法情况
        f[0][1][0] = 1e18;
        // 初始化画廊右侧第一个位置的距离
        f[0][1][1] = Math.hypot(w * 1.0 / 2, v[1]);
        for (int i = 2; i <= r; i++) {
        	// 非法情况
            f[0][i][0] = 1e18;
            // 依次计算画廊右侧上的每个作品的距离
            f[0][i][1] = f[0][i - 1][1] + v[i] - v[i - 1];
        }
        
        // 不重不漏考虑所有情况
        for (int i = 1; i <= l ; i++)
            for (int j = 1; j <= r; j++) {
            	// 经过ui, vj且最后到达画廊左侧，从ui-1 -> ui, vj -> ui, 两种转移方式取min
                f[i][j][0] = Math.min(f[i - 1][j][0] + u[i] - u[i - 1], f[i - 1][j][1] + Math.hypot(w, u[i] - v[j]));
                // 经过ui, vj且最后到达画廊右侧，从ui -> vj, vj-1 -> vj, 两种转移方式取min
                f[i][j][1] = Math.min(f[i][j - 1][0] + Math.hypot(w, u[i] - v[j]), f[i][j - 1][1] + v[j] - v[j - 1]);
            }
        
        // 最后求在画廊左侧和画廊右侧到画廊中央的最小距离
        double ans = Math.min(f[l][r][0] + Math.hypot(w * 1.0 / 2, d - u[l]), f[l][r][1] + Math.hypot(w * 1.0 / 2, d - v[r]));
        out.printf("%.2f", ans);
        out.flush();
    }

}

I. 补给

在这里插入图片描述

思路：

注意数据范围不是很大，可能涉及到复杂的状态转换。

首先根据每个点的坐标计算每个点之间的距离，由于飞机单次最长飞行距离为 $D$ ，当距离大于 $D$ 时，可以认为这两个村庄不可达。

再用 $Fl oy d$ 处理多源最短路问题，时间复杂度为 $O(N^3)$ 。

经过每个点至少一次可以看作 $TSP$ 问题，用状态压缩 $D P$ 来求解。用一个 $n$ 位的 $2$ 进制数来表示经过的村庄的状态。

初始化：

// 第一维表示经过的村庄的点集，1表示第0号村庄已经在集合里，到0号村庄的距离为0
// dp[state][i] 表示经过的村庄的集合为state，到达第i号村庄的最小距离
dp[1][0] = 0;

状态转移：

// 第一维枚举所有的状态
for (int i = 0; i < (1 << n); i++)
	// 第二维枚举所有的村庄
	for (int j = 0; j < n; j++) {
		// 如果当前村庄在集合中，考虑能否用其他的状态来转移，从而使得距离更小
		if ((i >> j & 1) == 1) {
			// 枚举分界点
			for (int k = 0; k < n; k++) {
				// 再去除了村庄j、且包含村庄k的情况下，从村庄k转移到村庄j
				if (((i - (1 << j) >> k) & 1) == 1)
					dp[i][j] = Math.min(dp[i][j], dp[i - (1 << j)][k] + dist[k][j]);
			}
		}
	}

由于最后还有回到起点，再计算包含所有村庄的状态下回到起点的最短距离：

double ans = 1e18;
for (int i = 1; i < n; i++) {
	ans = Math.min(ans, dp[(1 << n) - 1][i] + dist[i][0]);
}

最后时间复杂度为 $O(2^nn^2)$ 。

代码：

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
import java.util.Arrays;

public class Main {

    static final int N = 20;
    static int[] x = new int[N], y = new int[N];
    static double[][] dist = new double[N][N];
    static double[][] dp = new double[1 << N][N];
    static int n, D;

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
    static StreamTokenizer in = new StreamTokenizer(br);

    public static int nextInt() throws IOException {
        in.nextToken();
        return (int) in.nval;
    }

    public static void main(String[] args) throws IOException {
        // TODO Auto-generated method stub
        n = nextInt();
        D = nextInt();

        for (int i = 0; i < n; i++) {
            x[i] = nextInt();
            y[i] = nextInt();
        }

        for (int i = 0; i < n; i++)
            for (int j = i + 1; j < n; j++) {
                dist[i][j] = dist[j][i] = Math.hypot(x[i] - x[j], y[i] - y[j]);
                if (dist[i][j] > D)
                    dist[i][j] = dist[j][i] = 1e18;
            }

        for (int k = 0; k < n; k++)
            for (int i = 0; i < n; i++)
                for (int j = 0; j < n; j++)
                    dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);

        for (double[] ds : dp)
            Arrays.fill(ds, 1e18);

        dp[1][0] = 0;
        for (int i = 0; i < (1 << n); i++)
            for (int j = 0; j < n; j++) {
                if ((i >> j & 1) == 1) {
                    for (int k = 0; k < n; k++) {
                        if (((i - (1 << j) >> k) & 1) == 1)
                            dp[i][j] = Math.min(dp[i][j], dp[i - (1 << j)][k] + dist[k][j]);
                    }
                }
            }

        double ans = 1e18;
        for (int i = 1; i < n; i++) {
            ans = Math.min(ans, dp[(1 << n) - 1][i] + dist[i][0]);
        }

        out.printf("%.2f", ans);
        out.flush();
    }

}