试题 A: 美丽的 2

问题描述

---

小蓝特别喜欢 2，今年是公元 2020年，他特别高兴。 他很好奇，在公元 1 年到公元 2020 年（包含）中，有多少个年份的数位中包含数字 2？

---

答案提交

---

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

---

import java.io.*;
import java.util.*;//自定义Read类中需要用到io和util这两个包，星号*(通配符)表示包中所有的类
import java.math.*;//含大数BigInteger
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;
import java.util.StringTokenizer;

public class Main {
	static int INF = 0x3f3f3f3f;
	public static void main(String[] args) {
		int cnt = 0;
		for(int i = 1;i <= 2020;i++)
			if(("" + i).contains("2"))cnt++;
		System.out.println(cnt);
	}
}

---

答案：563

---

试题 B: 扩散

问题描述

---

小蓝在一张无限大的特殊画布上作画。 这张画布可以看成一个方格图,每个格子可以用一个二维的整数坐标表示。 小蓝在画布上首先点了一下几个点:(0, 0), (2020, 11), (11, 14), (2000, 2000)。 只有这几个格子上有黑色,其它位置都是白色的。 每过一分钟,黑色就会扩散一点。具体的,如果一个格子里面是黑色,它就会扩散到上、下、左、右四个相邻的格子中,使得这四个格子也变成黑色(如果原来就是黑色,则还是黑色)。 请问,经过 2020 分钟后,画布上有多少个格子是黑色的。

---

答案提交

---

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

---

思路

---

扩充容量，然后分成2020层使用BFS模拟。

---

import java.io.*;
import java.util.*;//自定义Read类中需要用到io和util这两个包，星号*(通配符)表示包中所有的类
import java.math.*;//含大数BigInteger
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;
import java.util.StringTokenizer;

public class Main {
	static int INF = 0x3f3f3f3f;
	static class Node{
		int x, y, dp;
		Node(int x, int y, int dp){
			this.x = x;
			this.y = y;
			this.dp = dp;
			vis[x][y] = 1;//可以在构造函数里面使用标记
		}
	}
	static int vis[][] = new int[7500][7500];
	static Queue<Node>q = new LinkedList<Node>();
	public static void main(String[] args) {
		int cnt = 4;//初始4个黑点
		q.add(new Node(0 + 2050, 0 + 2050, 0));
		q.add(new Node(2020 + 2050, 11 + 2050, 0));
		q.add(new Node(11 + 2050, 14 + 2050,0));
		q.add(new Node(2000 + 2050, 2000 + 2050,0));
		while(!q.isEmpty()) {
			Node nd = q.poll();
			if(nd.dp == 2020)break;
			if(vis[nd.x + 1][nd.y] == 0) {
				q.add(new Node(nd.x + 1, nd.y, nd.dp + 1));
				cnt++;
			}
			if(vis[nd.x - 1][nd.y] == 0) {
				q.add(new Node(nd.x - 1, nd.y, nd.dp + 1));
				cnt++;
			}
			if(vis[nd.x][nd.y + 1] == 0) {
				q.add(new Node(nd.x, nd.y + 1, nd.dp + 1));
				cnt++;
			}
			if(vis[nd.x][nd.y - 1] == 0) {
				q.add(new Node(nd.x, nd.y - 1, nd.dp + 1));
				cnt++;
			}
		}
		System.out.println(cnt);
	}
}

---

答案：20312088

---

试题 C: 阶乘约数

问题描述

---

定义阶乘 n ! = 1 × 2 × 3 × ⋅ ⋅ ⋅ × n 。 请问 100 ! （100 的阶乘）有多少个约数。

---

答案提交

---

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

---

思路

---

唯一分解定理分解质因子 + 算术基本定理求约数个数

---

import java.io.*;
import java.util.*;//自定义Read类中需要用到io和util这两个包，星号*(通配符)表示包中所有的类
import java.math.*;//含大数BigInteger
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;
import java.util.StringTokenizer;

public class Main {
	static int INF = 0x3f3f3f3f;
	public static void main(String[] args) {
		
		int p[] = new int[200];
		
		for(int i = 2;i <= 100;i++) {
			int t = i;
			for(int j = 2;j <= t;j++) {
				while(t % j == 0) {
					p[j]++;
					t /= j;
				}
			}
		}
		long ans = 1;
		for(int i = 2;i <= 100;i++)
			if(p[i] != 0) ans *= (p[i] + 1);
		System.out.println(ans);
		
	}
}

---

答案：39001250856960000

---

试题 D: 本质上升序列

问题描述

---

小蓝特别喜欢单调递增的事物。 在一个字符串中，如果取出若干个字符，将这些字符按照在字符串中的顺序排列后是单调递增的，则成为这个字符串中的一个单调递增子序列。 例如，在字符串 lanqiao 中，如果取出字符 n 和 q，则 nq 组成一个单调递增子序列。类似的单调递增子序列还有 lnq、i、ano 等等。 小蓝发现，有些子序列虽然位置不同，但是字符序列是一样的，例如取第二个字符和最后一个字符可以取到 ao，取最后两个字符也可以取到 ao。小蓝认为他们并没有本质不同。 对于一个字符串，小蓝想知道，本质不同的递增子序列有多少个？ 例如，对于字符串 lanqiao，本质不同的递增子序列有 21 个。它们分别是 l、a、n、q、i、o、ln、an、lq、aq、nq、ai、lo、ao、no、io、lnq、anq、lno、ano、aio。 请问对于以下字符串（共 200 个小写英文字母，分四行显示）：（如果你把以下文字复制到文本文件中，请务必检查复制的内容是否与文档中的一致。在试题目录下有一个文件 inc.txt，内容与下面的文本相同）

---

答案提交

---

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

---

思路

---

剪枝搜索出所有情况，如果一种情况的前缀已经出现过，那么则无需再向下搜索。

---

import java.io.*;
import java.util.*;//自定义Read类中需要用到io和util这两个包，星号*(通配符)表示包中所有的类
import java.math.*;//含大数BigInteger
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;
import java.util.StringTokenizer;

public class Main {
	static int INF = 0x3f3f3f3f;
	static Set<String> s = new HashSet<>();

	static String ss = "tocyjkdzcieoiodfpbgcncsrjbhmugdnojjddhllnofawllbhfiadgdcdjstemphmnjihecoapdjjrprrqnhgccevdarufmliqijgihhfgdcmxvicfauachlifhafpdccfseflcdgjncadfclvfmadvrnaaahahndsikzssoywakgnfjjaihtniptwoulxbaeqkqhfwl";

	static void dfs(int st, String cur) {
		if(s.contains(cur))return ;
		s.add(cur);
		
		for (int i = st + 1; i < ss.length(); i++) {
			if ((int) ss.charAt(st) < (int) ss.charAt(i))
				dfs(i, cur + ss.charAt(i));
		}
		return;
	}

	public static void main(String[] args) {
		for (int i = 0; i < ss.length(); i++)
			dfs(i, "" + ss.charAt(i));
		System.out.println(s.size());
	}
}

---

答案：3616159

---

试题 E: 玩具蛇

问题描述

---

玩具蛇

---

答案提交

---

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

---

思路

---

对于每一种可能的起点进行搜索，注意剪枝即可。

---

答案

---

552

---

public class Main {
	static int map[][] = new int[20][20];
	static int cnt;
	static void dfs(int x, int y, int num) {
		if(x < 1 || y < 1 || x > 4 || y > 4)return ;
		if(map[x][y] != 0)return ; 
		map[x][y] = num;
		if(num == 16) {
			cnt++;
		
			for(int i = 1;i <= 4;i++) {
				for(int j = 1;j <= 4;j++)
					System.out.print(map[i][j] + " ");
				System.out.println();
			}
				System.out.println();
			map[x][y] = 0;
			return ;
		}
		dfs(x + 1, y, num + 1);
		dfs(x - 1, y, num + 1);
		dfs(x, y + 1, num + 1);
		dfs(x, y - 1, num + 1);
		map[x][y] = 0;
	}
	public static void main(String[] args) {
		for(int i = 1;i <= 4;i++)
			for(int j = 1;j <= 4;j++)
				dfs(i, j, 1);
		System.out.println(cnt);
	}
}

试题 F: 蓝肽子序列

问题描述

---

L 星球上的生物由蛋蓝质组成，每一种蛋蓝质由一类称为蓝肽的物资首尾连接成一条长链后折叠而成。
生物学家小乔正在研究 L 星球上的蛋蓝质。
她拿到两个蛋蓝质的蓝肽序列，想通过这两条蓝肽序列的共同特点来分析两种蛋蓝质的相似性。
具体的，一个蓝肽可以使用 1 至 5 个英文字母表示，其中第一个字母大写，后面的字母小写。
一个蛋蓝质的蓝肽序列可以用蓝肽的表示顺序拼接而成。
在一条蓝肽序列中，如果选取其中的一些位置，把这些位置的蓝肽取出，并按照它们在原序列中的位置摆放，则称为这条蓝肽的一个子序列。
蓝肽的子序列不一定在原序列中是连续的，中间可能间隔着一些未被取出的蓝肽。
如果第一条蓝肽序列可以取出一个子序列与第二条蓝肽序列中取出的某个子序列相等，则称为一个公共蓝肽子序列。
给定两条蓝肽序列，找出他们最长的那个公共蓝肽子序列的长度。

---

输入格式

---

输入两行，每行包含一个字符串，表示一个蓝肽序列。字符串中间没有空格等分隔字符。

---

输出格式

---

输出一个整数，表示最长的那个公共蓝肽子序列的长度。

---

样例输入

---

LanQiaoBei
LanTaiXiaoQiao

---

样例输出

---

2

---

样例说明

---

最长的公共蓝肽子序列为 LanQiao，共两个蓝肽。

---

评测用例规模与约定

---

对于 20% 的评测用例，两个字符串的长度均不超过 20。
对于 50% 的评测用例，两个字符串的长度均不超过 100。
对于所有评测用例，两个字符串的长度均不超过 1000。

---

思路

---

将字符串按条件转换，然后计算最长公共子序列即可。

---

import java.io.*;
import java.util.*;//自定义Read类中需要用到io和util这两个包，星号*(通配符)表示包中所有的类
import java.math.*;//含大数BigInteger
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;
import java.util.StringTokenizer;

public class Main {
	static String ss1[] = new String[1005];
	static String ss2[] = new String[1005];
	static int dp[][] = new int[1005][1005];
	
	public static void main(String[] args) {
		Scanner cin = new Scanner(System.in);
		String s1 = cin.next();
		String s2 = cin.next();
		int cnt1 = 1;ss1[1] = "";ss2[1] = "";
		int f = 0;
		for (int i = 0; i < s1.length(); i++) {
			if (s1.charAt(i) >= 'A' && s1.charAt(i) <= 'Z') {
				if (f == 1) { 
					f = 0;
					i--;
					cnt1++;
					ss1[cnt1] = "";
					continue;
				}
				else f = 1;
			}
			ss1[cnt1] +=  s1.charAt(i);
		}
		
		int cnt2 = 1;
		f = 0;
		for (int i = 0; i < s2.length(); i++) {
			if (s2.charAt(i) >= 'A' && s2.charAt(i) <= 'Z') {
				if (f == 1) { 
					f = 0;
					i--;
					cnt2++;
					ss2[cnt2] = "";
					continue;
				}
				else f = 1;
			}
			ss2[cnt2] += "" + s2.charAt(i);
		}
		
		for(int i = 1;i <= cnt1;i++)
			for(int j = 1;j <= cnt2;j++) {
				if(ss1[i].equals(ss2[j])) {
					dp[i][j] = dp[i - 1][j - 1] + 1;
				}else {
					dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
				}
			}
		System.out.println(dp[cnt1][cnt2]);
	}
}

试题 H: 画廊

问题描述

---

小蓝办了一个画展,在一个画廊左右两边陈列了他自己的作品。为了使画展更有意思,小蓝没有等距陈列自己的作品,而是按照更有艺术感的方式陈列。在画廊的左边陈列了 L 幅作品,在画廊的右边陈列了 R 幅作品,左边的作品距离画廊的起点依次为 u1 , u2 , · · · , uL ,右边的作品距离画廊起点依次为 v1 , v2 , · · · ,vR 。 每周,小蓝要整理一遍自己的每一幅作品。整理一幅作品的时间是固定的,但是要带着沉重的工具。从一幅作品到另一幅作品之间的距离为直线段的长度。 小蓝从画廊的起点的正中央(左右两边的中点)出发,整理好每一幅画,最终到达画廊的终点的正中央。已知画廊的宽为 w。 请问小蓝最少带着工具走多长的距离?

---

输入格式

---

输入的第一行包含四个整数 L, R, d, w,表示画廊左边和右边的作品数量,以及画廊的长度和宽度。 第二行包含 L 个正整数 u 1 , u 2 , · · · , u L ,表示画廊左边的作品的位置。 第三行包含 R 个正整数 v 1 , v 2 , · · · , v R ,表示画廊右边的作品的位置。

---

输出格式

---

输出一个实数,四舍五入保留两位小数,表示小蓝最少带着工具走的距离。

---

样例输入

---

3 3 10 2
1 3 8
2 4 6

---

样例输出

---

14.71

---

样例说明

---

小蓝从起点开始,首先到达左边第一幅作品(走动距离 √2),然后到达左边第二幅作品(走动距离 2),然后到达右边第一幅作品(走动距离 √5),然后到达右边第二幅和第三幅作品(走动距离 2 和 2),然后到达左边第三幅作品(走动距离 2√2),最后到达画廊终点(走动距离 √5)。 总共距离为 √2 + 2 + √5 + 2 + 2 + 2√2 + √5 ≈ 14.71。

---

评测用例规模与约定

---

对于 40% 的评测用例,1 ≤ L, R ≤ 10, 1 ≤ d ≤ 100, 1 ≤ w ≤ 100。
对于 70% 的评测用例,1 ≤ L, R ≤ 100, 1 ≤ d ≤ 1000, 1 ≤ w ≤ 1000。
对于所有评测用例,1 ≤ L, R ≤ 500, 1 ≤ d ≤ 100000, 1 ≤ w ≤ 100000,0 ≤ u 1 < u 2 < · · · < u L ≤ d, 0 ≤ v 1 < v 2 < · · · < v R ≤ d。

---

思路

---

分析可知为稠密图，且最后一定为最小生成树，按题意建图，起点和终点与另外的画建立一张图，将和起点距离转化为坐标，使用prime算法求最小生成树。

---

import java.io.*;
import java.util.*;//自定义Read类中需要用到io和util这两个包，星号*(通配符)表示包中所有的类
import java.math.*;//含大数Biglongeger
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;
import java.util.StringTokenizer;

public class Main{

	static double a[] = new double[100005];
	static int MAX = 1005; // 最大结点个数
	static long GIGANTIC = 0x3f3f3f3f; // 定义为无穷大
	static double[][] graph = new double[MAX][MAX];
	static double[] lowCost = new double[MAX]; // 到达j结点的最低花费
	static long[] previousNode = new long[MAX]; // j结点的上一个结点
	static long[] D = new long[MAX]; // j结点的上一个结点
	static double minCost = 0; // 最小成本
	static long n; // 结点个数
	static int middleNode; // 中间结点
	static double sum = 0; // 记录最小生成树的总权重
	static int L, R, d, w;
	static class PrimMST {
		/**
		 * Prim算法，返回最小生成树的总权重。
		 * 
		 * @param graph
		 * @param n
		 * @return sum
		 */
		public double prim(double[][] graph, long n) {
			// 邻接矩阵，有权值的（直接相邻的）赋权值。没有权值的（非直接相邻的）赋无穷大值
			for (int i = 0; i <= n; i++) {
				for (int j = 0; j <= n; j++) {
					if (graph[i][j] == 0) {
						graph[i][j] = GIGANTIC;
					}
				}
			}
			// 所有点默认起点是A
			for (int i = 1; i <= n; i++) {
				lowCost[i] = graph[0][i];
				previousNode[i] = 0;
			}
			previousNode[0] = -1;
			// 进行n-1次循环运算
			for (long i = 1; i <= n; i++) {
				minCost = GIGANTIC;
				middleNode = 0;

				// 找出最小的lowCost
				for (int j = 1; j <= n; j++) {
					if (lowCost[j] != 0 && lowCost[j] < minCost) {
						minCost = lowCost[j];
						middleNode = j;
					}
				}
				// 转换为ASCII码表示的英文字符输出
				sum += minCost;
				// lowCost[middleNode] = 0; previousNode[middleNode] = 0;表示middleNode被选入最小生成树
				lowCost[middleNode] = 0;
				previousNode[middleNode] = 0;

				// middleNode加入最小生成树，更新lowCost与previousNode
				for (int j = 1; j <= n; j++) {
					if (graph[middleNode][j] < lowCost[j]) {
						lowCost[j] = graph[middleNode][j];
						previousNode[j] = middleNode;
					}
				}
			}
			return sum;
		}

	}


	static double doEdge(long y1, long y2, long i1, long i2) {
		double x1 = 0;
		double x2 = 0;
		if(i1 == 0)x1 = w / 2.0;
		if (i1 > L)
			x1 = w;
		if (i2 > L)
			x2 = w;
		return Math.sqrt(1.0 * (x1 - x2) * (x1 - x2) + 1.0 * (y1 - y2) * (y1 - y2));
	}

	public static void main(String[] args) {
		Scanner cin = new Scanner(System.in);
		L = cin.nextInt();
		R = cin.nextInt();
		d = cin.nextInt();
		w = cin.nextInt();

		for (int i = 1; i <= L + R; i++) {
			D[i] = cin.nextLong();
		}

		for (int i = 1; i <= L + R; i++) {
			double e = doEdge(0, D[i], 0, i);
			graph[0][i] = e;
			graph[i][0] = e;
							
		}

		for (int i = 1; i <= L + R; i++) {
			for (int j = i + 1; j <= L + R; j++) {
				double e = doEdge(D[i], D[j], i, j);
				graph[i][j] = e;
				graph[j][i] = e;
				
			}
		}
		
		for (int i = 1; i <= L + R; i++) {//终点
			double e = doEdge(d, D[i], 0, i);
			graph[L + R + 1][i] = e;
			graph[i][L + R + 1] = e;
							
		}
		
		PrimMST primMST = new PrimMST();
		double mstCost = primMST.prim(graph, L + R + 1);
		System.out.printf("%.2f",mstCost);

	}
}