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

A. 美丽的2

思路：

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

代码：文章来源地址https://www.toymoban.com/news/detail-472888.html

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. 扩散

解法一：（比较慢但是容易想）

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

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

代码：

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=p_1^{{\alpha }_1}\times p_2^{{\alpha }_2}\times p_3^{{\alpha }_3}\times ...\times p_k^{{\alpha }_k}$$
$N$的每一个约数$d_i$，可以表示为:
$$d_i=p_1^{{\beta }_1}\times p_2^{{\beta }_2}\times p_3^{{\beta }_3}\times ...\times p_k^{{\beta }_k}$$
其中，$0\le {\beta }_i\le {\alpha }_i$， ${\beta }_i$的选法有$0\sim {\alpha }_i$，共有$({\alpha }_i+1)$种选法 ，根据排列组合原理，约数个数为：
$$({\alpha }_1+1)\times ({\alpha }_2+1)\times ({\alpha }_3+1)\times ...\times ({\alpha }_k+1)$$

求 $2\sim 100$ 的质因数以及每个质因数的个数，每个质因数的个数加一相乘即可，答案为 $\prod _1^k({\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}\times 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. 玩具蛇

思路：

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

代码：

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$ 即可。

重点在于初始化，状态转移方程为：
{ f ( i , j , 0 ) = m i n { f ( i − 1 , j , 0 ) + u i − u i − 1 , f ( i − 1 , j , 1 ) + d i s t ( u i , v j ) } f ( i , j , 1 ) = m i n { f ( i , j − 1 , 0 ) + d i s t ( u i , v j ) , f ( i , j − 1 , 1 ) + v j − v j − 1 } \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} {f(i,j,0)=min{f(i−1,j,0)+ui​−ui−1​,f(i−1,j,1)+dist(ui​,vj​)}f(i,j,1)=min{f(i,j−1,0)+dist(ui​,vj​),f(i,j−1,1)+vj​−vj−1​}​

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

代码：

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$ 时，可以认为这两个村庄不可达。

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

经过每个点至少一次可以看作 $TSP$ 问题，用状态压缩 $DP$ 来求解。用一个 $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^n{n}^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();
    }

}

到了这里，关于第十一届蓝桥杯国赛JavaB组题解的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！