第十五届蓝桥杯JAVA B组分享

这次题目比上一年的题目少了,总体难度来说，除了题目有点让人读不懂，其他还好

A：报数游戏

我是直接用202420242024 / 2 * 12算的，当时少考虑了一些因素，好在也是对的

B:类斐波那契循环数

这道题就是把一个十进制的数，先把他从大到小的每一位放到下标从 0 开始的一个数组中，然后做一遍和斐波那契一样的前 n.length 的和就可以了，在枚举的时候如果当前的前n项和已经大于了这个数本身就可以break了，第一层循环枚举的时候要从他的长度开始枚举，如果下标是从1开始的就从n + 1开始枚举

C:分布式队列

这道题是一道模拟题，题目的意思就是给你一个长度不超过10的二维数组，有三个操作，a：操作可以在下标为0的数组中加入一个数，b操作，同步下标为i的数组，让他的数组中加入一个第一个数组中没有的元素，这个加入要从下标为0的数组的第一个数开始算，c：操作询问当前所有数组中，元素个数的最小值，如果有一个数组里一个元素都没有就是0

思路：开一个二维数组，用来存放每个数组的值，在同步操作时需要一个指针来指向下一个同步的数，再开一个指针数组，每次同步谁就让谁的指针 ++，每次query的时候，就遍历一遍index数组找到最小的，输出即可

D:食堂

题目大概意思就是：有a个2人的宿舍，b个3人的宿舍，c个3人的宿舍，有d张4人的桌子，e张6人的桌子，要分配他们吃饭，有一个规则，同宿舍的人必须再一个桌子上吃饭，问最多可以让多少人吃饭。

思路：数据范围很小，样例最多为100，a + b + c，d + e 最大都不会超过100，一共有d * 4 + e * 6个空位，那我们最多让这些人都坐满，也就是我们的答案最多就是这些，当前，这里的座位要和他的总人数取一个最小值，在循环的时候我们先枚举人数，再枚举每个不同的宿舍出几个宿舍来吃饭

n = Math.min(d * 4 + 3 * 6, a * 2 + b * 3 + d * 4);
//A，B，C 表示2人，3人，4人的宿舍各有多少个，我们枚举的宿舍的个数
for(int k = n; k >= 0; k -- ) {
    for(int a = 0; a < A; a ++ ) {
        for(int b = 0; b < B; b ++ ) {
            for(int c = 0; c < C; c ++ ) {
                if(check(a, b, c) {
                    成功输出即可
                }
            }
        }
    }
}

正常枚举的话时间复杂度是O(k * A * B * C)再乘上100的输入数据，是有可能会报错的，我们可以发现，当A和B宿舍出的人数确定了，枚举的人数确定了以后，C宿舍出的人数是固定的，我们不需要再枚举C宿舍了，我们只需要判断C宿舍贡献的人数能否被n - A * 2 - B * 3 整除即可，就可以省去一层循环，就可以过掉了

E:最优分组

这道题没看懂他的5的怎么算出来，我的实现思路可能不太对，就不再这里和大家分享了

F:星际旅行

题目大意：给你n个点每两个点之间有一条无向边，问从这n个点中，从任意一个点出发，走不超过k条边的点的数量的最大值。

思路：他虽然说是最大值，但是我们可以发现，我能往下走就一定不会往回走，所以只要考虑从一个点往周围延申k条边能到达点的数量就可以了。

由于这个图边权都为1所以可以用bfs来做，最多是1000个点，边的话是点n * (n - 1) / 2 , 5n两个取一个最小值，建图用邻接表边的总数就是2 * 5000 = 10000最多就是10000条边，bfs的时间复杂度是边的数量，再对每个点做一次bfs的时间复杂度是O(1000 * 10000) 也就是10^7 这道题目的时间是3S 这样做是不会超时的，然后要把从每个点出发到个个点的距离存下来，开一个二维数组g[1000][1000]，这里不用怕超过空间限制，他给的空间限制是512MB，放心开，一共是有5 * 10^4询问，每次询问我们都要遍历一遍长度为10^3的数组，所以这一步的时间复杂度是5 * 10^7，这样时间总的时间就是5 * 10^7。

G:LITS游戏

跳过，感觉很麻烦

H:拼十字

思路：首先先暴力枚举任意两个木块，时间复杂度O(10^5 * 10^5)最多过百分之30的案例。

class Pair {
    // 长，宽，颜色
    int l w, c;
}

优化：仔细观察循环，我们要找的就是，在一个集合当中选取k个满足的数，把他们给加起来，那由于不满足的数我们是一定不会选的，所以这个集合是具有二段性质的。我们可以对l用从小到大排序，对w用从大到小排序，因为在比的时候，要求第一个矩阵的长度严格大于大第二个矩阵的长度，升序排列后，我们找到第一个大于第一个矩阵后，他后面的所有pair的l是一定都满足的，但是l满足并不能代表w也是满足的，由于第一个矩阵的宽度要大于第二个矩阵的宽度，如果对w采用升序排列后，他的答案是1 ~ k显然和l的判断是矛盾的，所以这里采用降序排列

贪心思路确定后，还有一点，那我们如何在这种贪心下保证最后二分停止后剩下的都是满足的呢，我们观察到，这里只是对l和w进行了贪心，还没有解决c的问题，我们无法保证剩下的一定都是颜色和我当前枚举的颜色不同的。可以发现他的颜色只有三种0，1，2，我们可以开3个集合，每个集合都只放相同颜色的pair,这样我们只需要枚举两个集合，进行贪心就不会有冲突了。

时间复杂度：由于谁做w1，和谁做w2是任意的，对于两个不同的集合，要枚举两次, 时间复杂度就是O(10^5 * log10^5 * 6);这里的log10^5理论上应该是log10^5 * loglog10^5,实际会更小