蓝桥杯真题（2019年填空题）

hi,你好。

第一题

思路：该题可以动脑子，直接比较数的大小，也可以一个一个输入，注意每个队员只能选一次。
代码：

import java.util.Scanner;

public class ChosenTeam {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int[][] chosenTeam = new int[20][5];
		try {
			for (int i = 0; i < 20; i++) {
				for (int j = 0; j < 5; j++) {
					chosenTeam[i][j] = sc.nextInt();
				}
			}
			// 接下来就是要输入的数据，五个for搞定
			// 就是要输入的数据太多，反而不如直接口算比较,结果更快
			int maxSum = 0;
			for (int z = 0; z < 20; z++)
				for (int y = 0; y < 20; y++)
					for (int p = 0; p < 20; p++)
						for (int s = 0; s < 20; s++)
							for (int g = 0; g < 20; g++)
								if ((z != y && z != p && z != s && z != g) && (y != p && y != z && y != g)
										&& (p != z && p != g) && s != g) {
									int max = chosenTeam[z][0] + chosenTeam[y][1] + chosenTeam[p][2] + chosenTeam[s][3]
											+ chosenTeam[g][4];
									if (max > maxSum)
										maxSum = max;
								}
			System.out.println(maxSum);

		} catch (Exception e) {
			sc.close();
		}
	}
}

结果：490

第二题

思路：要求是不同的非空字串，可以用String.substring()方法求字串，不同子串可以用Set集合，根据给出的例子，可以看出字串在变化时，一开始，间隔一个字符，每次移动距离为1；然后，间隔俩个字符，每次移动距离也为1，一直到间隔的距离为整个字符串。
代码：

import java.util.HashSet;
import java.util.Set;

public class 不同字串 {
	public static void main(String[] args) {
		String data = "0100110001010001";
		Set<String> son = new HashSet<String>();
		for (int removing = 0; removing <= data.length() - 1; removing++) {
			for (int begin = 0, end = 1 + removing; end <= data.length(); begin++, end++) {
				son.add(data.substring(begin, end));
			}
		}
		System.out.println(son.size());
	}
}

结果：100

第三题

思路：要求的是20190324最后4位，如果将该项所有位数都存储，用斐波那契数列的思想，数肯定会溢出，原因是太大了，那就只保留后四位就行了。
代码：

public class SeekingValue {
	public static void main(String[] args) {
		int z = 1, y = 1, p = 1;
		for (int x = 3; x < 20190324; x++) {
			int interval = (z + y + p) % 10000;
			z = y;
			y = p;
			p = interval;
		}
		System.out.println(p);
	}
}

结果：4659

第四题

思路：
1.不包含2和4，2019可以怎么分解成三个数之和？
2.三个数的组合
代码：

public class disintegration{
public static void main(String[] args) {
		int data = 2019;
		int digit = 0;
		for (int z = 1; z < data; z++) {
			if ((z + "").indexOf("2") != -1 || (z + "").indexOf("4") != -1)
				continue;
			for (int y = z + 1; y < data; y++) {
				if ((y + "").indexOf("2") != -1 || (y + "").indexOf("4") != -1)
					continue;
				int p = data - z - y;
				if (z == p || y == p || z == y)
					continue;
				if (p > 0 && (p + "").indexOf("2") == -1 && (p + "").indexOf("4") == -1)
					digit++;
			}
		}
		System.out.println(digit / 3);
	}
}

		System.out.println(digit / 3);
	}
}

结果：40785
--------------------------------------未完待续

一、标题：取数位

求1个整数的第k位数字有很多种方法。
以下的方法就是一种。

public class 取数位 {

	static int len(int x) {
		if (x < 10)
			return 1;
		return len(x / 10) + 1;
	}

	// 取x的第k位数字
	static int f(int x, int k) {
		if (len(x) - k == 0)
			return x % 10;
		return ——————; // 填空
	}

	public static void main(String[] args) {
		int x = 23513;
		// System.out.println(len(x));
		System.out.println(f(x, 3));// 应该打印5。
	}
}

对于题目中的测试数据，应该打印5。
答案：

f(x / 10, k)

二、标题：最大公共子串

最大公共子串长度问题就是： 求两个串的所有子串中能够匹配上的最大长度是多少。

比如：“abcdkkk” 和 “baabcdadabc”， 可以找到的最长的公共子串是"abcd",所以最大公共子串长度为4。

下面的程序是采用矩阵法进行求解的，这对串的规模不大的情况还是比较有效的解法。

请分析该解法的思路，并补全划线部分缺失的代码。

这个主要是矩阵法求解字符串匹配的问题，我觉得很巧妙！但是我想不到！

public class Main
{
	static int f(String s1, String s2)
	{
		char[] c1 = s1.toCharArray();
		char[] c2 = s2.toCharArray();
		
		int[][] a = new int[c1.length+1][c2.length+1];
		
		int max = 0;
		for(int i=1; i<a.length; i++){
			for(int j=1; j<a[i].length; j++){
				if(c1[i-1]==c2[j-1]) {
					a[i][j] = __________________;  //填空 
					if(a[i][j] > max) max = a[i][j];
				}
			}
		}
		
		return max;
	}
	
	public static void main(String[] args){
		int n = f("abcdkkk", "baabcdadabc");
		System.out.println(n);
	}
}

注意：只提交缺少的代码，不要提交已有的代码和符号。也不要提交说明性文字。

答案：

a[ i ][ j ] = a[i - 1] [j - 1] + 1; // 靠感觉，但是我没有感觉

三、标题：字母组串

由 A,B,C 这3个字母就可以组成许多串。 比如：“A”,“AB”,“ABC”,“ABA”,“AACBB” …

现在，小明正在思考一个问题： 如果每个字母的个数有限定，能组成多少个已知长度的串呢？

他请好朋友来帮忙，很快得到了代码， 解决方案超级简单，然而最重要的部分却语焉不详。

请仔细分析源码，填写划线部分缺少的内容。

public class 字母组串 {
	// a个A，b个B，c个C 字母，能组成多少个不同的长度为n的串。
	static int f(int a, int b, int c, int n) {
		if (a < 0 || b < 0 || c < 0)
			return 0;
		if (n == 0)
			return 1;

		return ————————————————————; // 填空
	}

	public static void main(String[] args) {
		System.out.println(f(1, 1, 1, 2));
		System.out.println(f(1, 2, 3, 3));
	}
}

分析：

递归函数参数的含义

参数变化的方向

public class 字母组串 {
	// a个A，b个B，c个C 字母，能组成多少个不同的长度为n的串。
	static int f(int a, int b, int c, int n) {
		if (a < 0 || b < 0 || c < 0)
			return 0;
		if (n == 0)
			return 1;

		return f(a - 1, b, c, n - 1) + f(a, b - 1, c, n - 1) + f(a, b, c - 1, n - 1); // 填空
	}

	public static void main(String[] args) {
		System.out.println(f(1, 1, 1, 2));
		System.out.println(f(1, 2, 3, 3));
	}
}

四、标题：9数算式

观察如下的算式： 9213 x 85674 = 789314562

左边的乘数和被乘数正好用到了1 ~ 9 的所有数字，每个1次。 而乘积恰好也是用到了1~9的所有数字，并且每个1次。

请你借助计算机的强大计算能力，找出满足如上要求的9数算式一共有多少个？

注意：

1. 总数目包含题目给出的那个示例。
2. 乘数和被乘数交换后作为同一方案来看待。

考察：求全排列+去重
关键点：考虑如何去重?
左右的乘数a * b=c 与 b*a =c都是一种方案，但是求解过程中会计算2次
去重：/2即可
易错点：乘积可能会有0的存在，应该判断一下

public class 填空_九数算式 {
	static List<List<Integer>> list = new ArrayList<>();
	static int count = 0;

	public static void main(String[] args) {
		int[] arr = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
		dfs(arr, 0);
		func();
		System.out.println(count / 2);
	}

	// 全排列
	public static void dfs(int[] arr, int index) {
		if (index >= arr.length) {
			List<Integer> temp = new ArrayList<>();
			for (int i = 0; i < arr.length; i++) {
				temp.add(arr[i]);
			}
			list.add(temp);
			return;
		}
		for (int i = index; i < arr.length; i++) {
			swap(arr, index, i);
			dfs(arr, index + 1);
			swap(arr, index, i);
		}
	}

	public static void swap(int[] arr, int i, int j) {
		int temp = arr[i];
		arr[i] = arr[j];
		arr[j] = temp;
	}

	public static void func() {
		for (int i = 0; i < list.size(); i++) {
			List<Integer> temp = list.get(i);
			int left = 0;
			for (int j = 0; j < 9; j++) {
				int index = 0;
				int leftNum = 0;
				int rightNum = 0;
				if (left > 7) {
					break;
				}
				while (index <= left && left <= 7) {// 左边的数，从1位到7位
					leftNum = leftNum * 10 + temp.get(index);
					index++;
				}
				while (index < 9) {
					rightNum = rightNum * 10 + temp.get(index);
					index++;
				}
				left++;
				long res = leftNum * rightNum;
				if (res < 123456789) {
					continue;
				}
				if (judge(res)) {
					count++;
				}

			}
		}
	}
	//judge判断错了
	//因为还存在有0的乘积！
	public static boolean judge(long res) {
		String anString = res + "";
		if (anString.indexOf('0') != -1) {
			return false;
		}
		HashSet<Integer> set = new HashSet<>();
		while (res != 0) {
			int temp = (int) res % 10;
			set.add(temp);
			res /= 10;
		}
		return set.size() == 9;
	}
}

原题：

如下图所示，小明用从 1 开始的正整数“蛇形”填充无限大的矩阵。

容易看出矩阵第二行第二列中的数是 5。请你计算矩阵中第 20 行第 20 列的数是多少？ 

先请看代码，再讲解思路：

#include <stdio.h>
 int arr[50][50]={0};
 int main()
 {
 	int i,j,pen=1;
 	for(i=1;i<=50;i++)
 	{
 		for(j=1;j<=i;j++)
 		{
 			if(i%2==0)
 			arr[i][i-j+1]=pen;
 			else
 			arr[i][j]=pen;
 			pen++;
		 }
	  } 
	   printf("%d",arr[39][20]);
 	return 0;
 }

解析思路：

题目中要求我们求第20行第20列的数，而我的代码中输出的arr实际情况是

1

3 2

4 5 6 ....

所以说我要做的就是将arr数组的数横坐标向上置顶，纵坐标保持不变就可以得到我们的蛇行数组，所以题目中的第20行第20列中的那个数，实际上就是我们arr数组的第39行，第20列。