目录
前言：试题 A: 报数游戏试题 B: 类斐波那契循环数试题C:分布式队列试题D:食堂试题E:最优分组
前言：
没参加这次蓝桥杯算法赛，十四届蓝桥杯被狂虐，对算法又爱又恨，爱我会做的题，痛恨我连题都读不懂的题,十四届填空只做对一个，今天闲的蛋疼想看看这次比赛能做对几个。
暂时没找到题目，这是网上找的简略版，看了看就知道蓝桥杯前几道题就喜欢考数学思维和十四届一样
测试平台：链接
试题 A: 报数游戏
（简洁版） 从小到大排列是20或24倍数的正整数，前10个数依次是：”20 24 40 48 60 72 80 96 100 120“，求第202420242024个数是多少？（填空题）
解题思路：
最开始想的是求求它俩的最小公倍数是120发现没啥用，然后再发现24比20多4，也就是24向前叠加5次就整整多出来一个20，然后再在纸上画画发现了每10次一循环：
可以看出第10个数是24 * 5，第20个数是24 * 10，那么202420242024可以分成202420242020 + 4，最后发现偶数4也是24结尾，那么答案就是202420242024 / 2 * 24
试题 B: 类斐波那契循环数
（个人理解：） 将一个n位的数字按一定的规则排成一个数列。 规则： 这个数列的起始部分分别为该数字每一位上的数。例如：数字（12345）排成数列是【1，2，3，4，5】。 这个数列的其它部分分别为从当前数列的最后一位起，前n项的和。例如数字（12345，共5位）排成数列【1，2，3，4，5，(?)，…】，此时数列的第6个数就是从当前数列的最后一位起前5项的和，即（1+2+3+4+5=15）【1，2，3，4，5，15】；第7个数就是从当前数列的最后一位起前5项的和，即（2+3+4+5+15=29）【1，2，3，4，5，15，29】；… 如果这个数列中包含这个数字本身，那么这个数就是类斐波那契循环数。 求从0~10^7范围中最大的类斐波那契循环数。（填空题）
解题思路：
仔细做了做例子发现： 发现有点像滑动窗口，求新数后窗口移动一下，所以想着将整个过程放在一个数组里，但是这样一整每次数组的长度都是不定的，不好定义数组的长度，且求到新数后，数组前面的区域就没用了，所以就想着能否用一个定长数组来做滑动窗口，且所有区域都用的上
分析一下上面例子求出新数15后第一个数1就对求下一个数29来说没用了，为什么不把15放在1的位置，以此类推29放在2的位置
这样就好整了，数组大小就等于数字的位数，还需要一个K指针在整个数组中循环移动用%Length就解决了
说实话这个灵感来源于我嵌入式对页面切换的处理…
最后看是怎么停止了，题目说了这个数列中包含这个数本身那么这个数就是类斐波那契循环数，因为每次求得得新数都是递增的，所以如果新数都大于原始数的话，那么说明这个数不是类斐波那契循环数
既然求类斐波那契循环数的整个逻辑模式都搞明白了，剩下就是用代码实现上述的功能需求了：
import java.util.*;
public class Main {
static int END = 10000000;
public static void main(String[] args) {
int MaxNumber = 0;
for(int i = 1; i <= END; i ++) { // 由1开始
int Length = GetNumnberLength(i);
int Array[] = new int[Length];
NumbertoArray(Array, i);
int k = 0;
while(true) {
Array[k] = ListNumberSum(Array);
if(Array[k] == i || Array[k] > i) break; // 要么是类斐波那契循环数要么不是
k = (k + 1) % Length;
}
if(Array[k] == i) { // 是的话更新MaxNumber
if(MaxNumber <= i) {
MaxNumber = i;
}
}
}
System.out.println(MaxNumber);
}
public static int GetNumnberLength(int number) {
int len = 0;
while(number > 0) {
len ++;
number = number / 10;
}
return len;
}
public static void NumbertoArray(int array[], int number) {
for(int i = array.length - 1; i >= 0; i --) {
array[i] = number % 10;
number = number / 10;
}
}
public static int ListNumberSum(int array[]) {
int sum = 0;
for(int i = 0; i < array.length; i ++) sum = sum + array[i];
return sum;
}
}
其中while循环应该也循环不了几百次，整个时间复杂度应该等于10^7 * while循环次数，超过不了10^9复杂度，计算机一两秒就算出来了。
答案：
以下试题全靠自己想法去做，可能有漏洞：
试题C:分布式队列
解题思路：
先做例题，可以看出每个结点都可以当作一个独立的数组，在执行操作命令的时候对对应数组进行操作，add就是对主结点做添加操作，sync就是对对应副结点做操作，query就是输出情况
那么好怎么将具体的例子解法抽象成一般问题的解决逻辑呢，并且这个逻辑能较好用编程去实现？
首先分析到这个题有点像木桶的短板效应，即输出只需要关注最少元素的那个副结点即可，且主结点内装具体什么元素好像都不重要，重要的是装了几个元素
这样以来变成就简化成了一维数组，每个数组下标对应相应结点，数组对应值为同步的数的数量，只需关注最小的那个结点即可
代码：
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int Number = sc.nextInt(); // 输入
String Temp = sc.nextLine(); // 吃空格
int Array[] = new int [Number];
while(sc.hasNext()){
String Command = sc.nextLine();
if(Command.charAt(0) == 'a') {
Array[0] ++; // add命令
}else if(Command.charAt(0) == 'q') {
System.out.println(GetArrayMinNumber(Array));
}else {
String Split[] = Command.split("\\s+");
int Index = Integer.parseInt(Split[1]);
if(Array[Index] < Array[0]) Array[Index] ++; // 主节点还有多的元素才能同步
}
}
}
public static int GetArrayMinNumber(int array[]) {
int MinOne = Integer.MAX_VALUE;
for(int i = 0; i < array.length; i ++) {
if(MinOne >= array[i]) MinOne = array[i];
}
return MinOne;
}
}
注意：主节点没有多余的元素就不能同步给副结点了
例如： 2 sync 1 sync 1 add 11 add 22 query 输出为0而不是2
另外sc.hasNext是读到文件末尾会停，用while true停不下来
试题D:食堂
解题思路：
这道题，可能是我想简单了吧，它题目需求是最多能坐多少人，寝室最多分2、3、4寝，这些寝室可以凑出来6、5、4、3、2这么些人，且每个寝室人都在一座子，它需求是最多可以有都少人用餐，那就有6桌子空余就先补上6的座子，用6、5补，再用4补…有4的桌子用4补用3补…主打先把人多的部分补上大桌子
这样搞例题能做对，但用代码实现好像也只能做对例题，动态规划又不会，新颖的思路又想不出来...
丑陋代码：
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int Number = sc.nextInt();
long Array1[] = new long [7];
long Array2[] = new long [7];
for(int i = 0; i < Number; i ++) {
Array1[2] = sc.nextInt();
Array1[3] = sc.nextInt();
Array1[4] = sc.nextInt();
Array2[4] = sc.nextInt();
Array2[6] = sc.nextInt();
//System.out.println(Array2[4] * 4 + Array2[6] * 6);
long Sum = 0;
Sum = Array2[4] * 4 + Array2[6] * 6;
// System.out.println(Sum);
for(int j = 6; j >= 1; j --) while(Array2[j] > 0 && RemoveTable(Array1, Array2, j) == 1);
for(int j = 1; j <= 6; j ++) Sum = Sum - Array2[j] * j;
System.out.println(Sum);
}
}
public static int RemoveTable(long array1[], long array2[], int i) {
if(array1[3] >= 2 && i == 6 && array2[i] > 0) {
array1[3] = array1[3] - 2;
array2[i] --;
return 1;
}
if(array1[2] > 0 && array1[4] > 0 && i == 6 && array2[i] > 0) { // 消6
array1[2] --;
array1[4] --;
array2[i] --;
return 1;
}
if(array1[2] >= 3 && i == 6 && array2[i] > 0) {
array1[2] = array1[2] - 3;
array2[i] --;
return 1;
}
if(array1[2] > 0 && array1[3] > 0 && i == 6 && array2[i] > 0) { // 有6消除5
array1[2] --;
array1[3] --;
array2[i] --;
array2[i - 5] ++;
return 1;
}
if(array1[4] > 0 && i >= 4 && array2[i] > 0) { // 有6消4
array1[4] --;
array2[i] --;
array2[i - 4] ++;
return 1;
}
if(array1[2] >= 2 && i >= 4 && array2[i] > 0) {
array1[2] = array1[2] - 2;
array2[i] --;
array2[i - 4] ++;
return 1;
}
if(array1[3] > 0 && i >= 3 && array2[i] > 0) { // 有6消3
array1[3] --;
array2[i] --;
array2[i - 3] ++;
return 1;
}
if(array1[2] > 0 && i >= 2 && array2[i] > 0) { // 有6消2
array1[2] --;
array2[i] --;
array2[i - 2] ++;
return 1;
}
return 0;
}
}
试题E:最优分组
解题思路：
纯数学题，当数学题解了，我数学还是有两把刷子的虽然刷子的毛不多
代码：
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int Number = sc.nextInt();
double P = sc.nextDouble();
double MinHope = Number;
int Index = 1;
for(int k = 1; k <= Number; k ++) {
if(Number % k == 0) {
double GetHope = Number * (1 - Math.pow(1 - P, k)) + Number / k;
if(GetHope < MinHope) {
MinHope = GetHope;
Index = k;
}
}
}
System.out.println(Index);
}
}
好文阅读
您阅读本篇文章共花了：
发表评论