第十届蓝桥杯算法竞赛

试题A:组队

 问题描述：

作为篮球队教练，你需要从以下名单中选出 1 号位至 5 号位各一名球员， 组成球队的首发阵容。

每位球员担任 1 号位至 5 号位时的评分如下表所示。请你计算首发阵容 1 号位至 5 号位的评分之和最大可能是多少？

试题B:不同子串

问题描述：

一个字符串的非空子串是指字符串中长度至少为 1 的连续的一段字符组成 的串。例如，字符串aaab 有非空子串a, b, aa, ab, aaa, aab, aaab，一共 7 个。 注意在计算时，只算本质不同的串的个数。 请问，字符串0100110001010001 有多少个不同的非空子串？

import java.util.ArrayList;

public class Main {
	public static void main(String[] args) {
		ArrayList<String> list = new ArrayList<>();
        //首先使用题目给定的条件进行测试
//		String string = "aaab";
		String string = "0100110001010001";
		String subString = null;
		int size = string.length();
		for (int length = 1; length <= size; length++) {
			for (int index = 0; index <= (size - length); index++) {
				subString = string.substring(index, index + length);
				if (!list.contains(subString)) {
					list.add(subString);
				}
			}
		}
		System.out.println(list.size());
		System.out.println(list.toString());
	}
}
           

试题C:数列求和

问题描述：

给定数列 1, 1, 1, 3, 5, 9, 17, …，从第 4 项开始，每项都是前 3 项的和。求 第 20190324 项的最后 4 位数字。

public class Main {
	public static void main(String[] args) {
		int number = 20190324;
		
		long num1 = 1;
		long num2 = 1;
		long num3 = 1;
		long temp = 0;
		
		// 首先使用较小的项数测试完整的数字，与下面截取的结果进行比较
//		for (long i = 4; i <= 50; i++) {
//			temp = num3;
//			num3 = (num1 + num2 + num3);
//			num1 = num2;
//			num2 = temp;
//		}
		
		for (long i = 4; i <= number; i++) {
			temp = num3 % 10000;
			num3 = (num1 + num2 + num3) % 10000;
			num1 = num2 % 10000;
			num2 = temp;
		}
		System.out.println(num3);
	}
}
           

 当时试过用递归，但是对于20190324这样的项数，直接就报了栈溢出。所以试验了上面代码中注释掉的部分，直接使用了20190324跑的结果5268603393216230115，这个结果看上去还可以，但唯独千位数是0，很郁闷，用20190325跑了一次发现数值越界了（结果是-94021825125598091），当时自作聪明地以为20190324就是临界值。/泪奔

 试题D:数的分解

问题描述：

把 2019 分解成 3 个各不相同的正整数之和，并且要求每个正整数都不包 含数字 2 和 4，一共有多少种不同的分解方法？ 注意交换 3 个整数的顺序被视为同一种方法，例如 1000+1001+18 和 1001+1000+18 被视为同一种。