2021年第十二届蓝桥杯javaA组省赛部分题目

试题 D: 路径

本题总分：10 分

【问题描述】

小蓝学习了最短路径之后特别高兴，他定义了一个特别的图，希望找到图

中的最短路径。

小蓝的图由 2021 个结点组成，依次编号 1 至 2021。

对于两个不同的结点 a, b，如果 a 和 b 的差的绝对值大于 21，则两个结点

之间没有边相连；如果 a 和 b 的差的绝对值小于等于 21，则两个点之间有一条

长度为 a 和 b 的最小公倍数的无向边相连。

例如：结点 1 和结点 23 之间没有边相连；结点 3 和结点 24 之间有一条无

向边，长度为 24；结点 15 和结点 25 之间有一条无向边，长度为 75。

请计算，结点 1 和结点 2021 之间的最短路径长度是多少。

提示：建议使用计算机编程解决问题。

【答案提交】

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

个人答案：10266837

解法1: 动态规划，区间dp

import java.util.Arrays;

class Main{

	static int INF=0x3f3f3f3f;

	static int[][] dis=new int[2025][2025];

	public static void main(String[] args) {

		init();

		int n=2021;

		for(int len=2;len <= n;len++) {

			for(int i=1;i<= n-len+1;i++) {

				int j=i+len-1;

				for(int k=i;k<= j;k++) {

					dis[i][j]=Math.min(dis[i][j], dis[i][k]+dis[k][j]);

				}

			}

		}

		System.out.println(dis[1][n]);

	}

	private static void init() {

		// TODO Auto-generated method stub

		for(int i=0;i<2025;i++) {

			Arrays.fill(dis[i], INF);

		}

		for(int i=1;i<=2021;i++) {

			for(int j=1;j<=2021;j++) {

				if(Math.abs(i-j)>21) {

					continue;

				}else {

					dis[i][j]=dis[j][i]=Math.min(dis[i][j], gbs(i, j));

				}

			}

			dis[i][i]=0;

		}

	}

	private static int gbs(int a,int b) {

		// TODO Auto-generated method stub

		int at=a,bt=b;

		while(true) {

			int t=gcd(at, bt);

			if (t!=1) {

				at=at/t;

				bt=bt/t;

			}else {

				break;

			}

		}

		return at*b;

	}

	private static int gcd(int a,int b) {

		if (b==0) {

			return a;

		}

		return gcd(b, a%b);

	}

}

解法2：最短路算法，这里使用的是spfa

待补充

试题 E: 回路计数

本题总分：15 分

【问题描述】

蓝桥学院由 21 栋教学楼组成，教学楼编号 1 到 21。对于两栋教学楼 a 和 b，当 a 和 b 互质时，a 和 b 之间有一条走廊直接相连，两个方向皆可通行，否

则没有直接连接的走廊。

小蓝现在在第一栋教学楼，他想要访问每栋教学楼正好一次，最终回到第

一栋教学楼（即走一条哈密尔顿回路），请问他有多少种不同的访问方案？两个

访问方案不同是指存在某个 i，小蓝在两个访问方法中访问完教学楼 i 后访问了

不同的教学楼。

提示：建议使用计算机编程解决问题。

【答案提交】

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

根据代码的意思：走 2 3 1和走 3 2 1算一种方法，因此才可以这样用set存储

个人答案：881012367360

方法1：dfs+减枝

本人直接使用dfs，跑一百年都跑不出来，。。。



import java.util.ArrayList;

import java.util.HashMap;

import java.util.HashSet;

import java.util.Map;

import java.util.Set;

/**

 * 这种写法要跑好几秒才能得出结果

 * @author HQL

 */

public class _回路计数 {

	static ArrayList<Integer>[] list;

	static Map<String, Long> set = new HashMap<String, Long>();

	public static void main(String[] args) {

		list = new ArrayList[21 + 1];

		for (int i = 0; i < list.length; ++i)

			list[i] = new ArrayList<Integer>();

		for (int i = 1; i <= 21; ++i)

			for (int j = i + 1; j <= 21; ++j)

				if (gcd(i, j) == 1) {

					list[i].add(j);

					list[j].add(i);

				}

		System.out.println(dfs(21, 1, 0));

	}

	public static long dfs(int total, int cur, int m) {

		if (total == 0)

			return 1;

		long res = 0;

		for (int p : list[cur]) {

            //按位储存，真的牛，这样就可以储存了

            //p为目标教学楼，m为当前已经访问过的教学楼（

            //假设m==12，对应的二进制为00001100，则m表示已经访问过的教学楼有2、3号）

			if ((m & (1 << p)) != (1 << p)) {

				String pm = p + "-" + m;

				long r = 0;

				if (set.containsKey(pm)) {		//剪枝

					r = set.get(pm);

				} else {

					if (p != 1 || p == 1 && total == 1)

						r = dfs(total - 1, p, m | (1 << p));

					set.put(pm, r);

				}

				res += r;

			}

		}

		return res;

	}

	public static int gcd(int a, int b) {

		if (a == 0 || b == 0)

			return 0;

		return a % b == 0 ? b : gcd(b, a % b);

	}

}

方法2：状态压缩dp

不会。。。

试题 F: 最少砝码

时间限制: 1.0s 内存限制: 512.0MB 本题总分：15 分

【问题描述】

你有一架天平。现在你要设计一套砝码，使得利用这些砝码可以称出任意

小于等于 N 的正整数重量。

那么这套砝码最少需要包含多少个砝码？

注意砝码可以放在天平两边。

【输入格式】

输入包含一个正整数 N。

【输出格式】

输出一个整数代表答案。

【样例输入】

【样例输出】

【样例说明】

3 个砝码重量是 1、4、6，可以称出 1 至 7 的所有重量。

1 = 1；

2 = 6 − 4 (天平一边放 6，另一边放 4)；

3 = 4 − 1；

4 = 4；

5 = 6 − 1；

6 = 6；

7 = 1 + 6；

少于 3 个砝码不可能称出 1 至 7 的所有重量。

【评测用例规模与约定】

对于所有评测用例，1 ≤ N ≤ 1000000000。

acwing中有这道题，找规律

试题 G: 左孩子右兄弟

时间限制: 3.0s 内存限制: 512.0MB 本题总分：20 分

【问题描述】

对于一棵多叉树，我们可以通过 “左孩子右兄弟” 表示法，将其转化成一棵二叉树。如果我们认为每个结点的子结点是无序的，那么得到的二叉树可能不唯一。换句话说，每个结点可以选任意子结点作为左孩子，并按任意顺序连接右兄弟。

给定一棵包含 N 个结点的多叉树，结点从 1 至 N 编号，其中 1 号结点是根，每个结点的父结点的编号比自己的编号小。请你计算其通过 “左孩子右兄弟” 表示法转化成的二叉树，高度最高是多少。注：只有根结点这一个结点的树高度为 0 。

例如如下的多叉树：

可能有以下 3 种 (这里只列出 3 种，并不是全部) 不同的 “左孩子右兄弟”

表示：

其中最后一种高度最高，为 4。

【输入格式】

输入的第一行包含一个整数 N。

以下 N −1 行，每行包含一个整数，依次表示 2 至 N 号结点的父结点编号。

【输出格式】

输出一个整数表示答案。

【样例输入】

【样例输出】

【评测用例规模与约定】

对于 30% 的评测用例，1 ≤ N ≤ 20；

对于所有评测用例，1 ≤ N ≤ 100000。

acwing上也是有这道题的。dfs搜索即可

import java.io.BufferedReader;

import java.io.IOException;

import java.io.InputStreamReader;

import java.util.ArrayList;

class Main{

	static int N=100000+5;

	static ArrayList<Integer>[] lists=new ArrayList[N];

	static long res=0L;

	public static void main(String[] args) throws IOException {

		init();

		BufferedReader reader=new BufferedReader(new InputStreamReader(System.in));

		String[] line=reader.readLine().split(" ");

		int n=Integer.parseInt(line[0]);

		for(int i=2;i<=n;i++) {

			line=reader.readLine().split(" ");

			int x=Integer.parseInt(line[0]);

			lists[x].add(i);

		}

		dfs(1,0);

		System.out.println(res);

	}

	private static void dfs(int cur, int len) {

		// TODO Auto-generated method stub

		if (lists[cur].size()==0) {

			res=Math.max(res, len);

			return;

		}

		int tonbei=lists[cur].size();

		for(int i=0;i<lists[cur].size();i++) {

			int son=lists[cur].get(i);

			dfs(son, len+tonbei);

		}

	}

	private static void init() {

		// TODO Auto-generated method stub

		for(int i=0;i<N;i++) {

			lists[i]=new ArrayList<Integer>();

		}

	}

}

来源： [https://blog.csdn.net/weixin_45640260/article/details/116377115]

2021年第十二届蓝桥杯javaA组省赛部分题目

试题 D: 路径

试题 F: 最少砝码

试题 G: 左孩子右兄弟