2024 第十五届蓝桥杯JavaB组思路分享

本次应该是没考什么特别难的算法，除了有一两题看到就不想做的没细想，其他的基本就是基本算法（但不是偏向模板，感觉这次比较综合，都是要在模板的基础上改挺多的），希望别留下遗憾

然后感觉难度不是按梯度的，有一些前面的题感觉比后面难（呜呜，但是我又特别爱死磕）

介绍下个人的一些情况吧：不是大佬，是一个双非大二小草鸡，大一下时参加过一些算法竞赛（尽管都没啥含金量，有含金量的连名额都打不进去）

然后今年一月才速成了Java，基本就是一半时间学项目，一半时间学算法

唉，可惜开学后，课太多了，进度贼慢，又不敢矿，可恶，上学真耽误学习

这次做得不太好，感觉身体很不舒服，很烦躁。

hh，我跟上次十四届一样带一大堆零食吃的，结果也是一口没吃

然后感觉适当的做一些比赛，养成独立做题的能力，相当作业，只会模板可能不会写题

试题 A: 报数游戏

我数论不太扎实，所以先用TreeSet集合（排序去重）写了个暴力程序，来找找规律

发现规律每$10$个就是120的倍数，能转为类似进制的东西

（当然也不定对，当时很烦躁，指看了前几个）

所以就是202420242024/10+arr[202420242024%10]

arr[]={被120包含了所以为0,20, 24, 40, 48, 60, 72, 80, 96, 100};

我考场上算出来的结果好像是以$4288$结尾的，反正挺长的

试题 B: 类斐波那契循环数

一眼没看，战术性没做

呜呜，其实是考场上太烦了，没做，但是听别人说好像不难

试题 C: 分布式队列

啊啊，读题读了40分钟，一直没懂，也是没谁了，状态是真的差

这个应该算是签到题

add element:这个element我最后好像没用，一般算法题每个变量都会用到，有点小慌

思路：（写个伪代码）
    （偏暴力）
三个操作对应的：
    add  element：       ++len
    sync follower_id：   ++cnt[follower_id]
    query:  {
        int res=len;//当前最多有几个
        for(int i=1;i<n;++i){
            res=min(res,cnt[i]);
        }
        输出res
    }
时间复杂度:O(操作数*N)=2e4能过

试题 D: 食堂

这题巨恶心，看到那个数据范围100，我就知道这题不简单了，还放这么前面

跟上一年的cb的飞机降落有异曲同工之妙，真的服

呜呜，上一年这个就是一个dfs暴力，但是我想成贪心了，最近补题也没想出来

我的思路就是：转为01背包（超级无敌多个状态，我都不敢优化）

感觉能做，但是我考场上有个bug没有de出来，唉

这题状态太多了，然后题目给的样例跑出来了，但是自己造的一个样例没有成功

看看有无大佬能帮我看看

唉，费了快一个小时，还没做出来

//考后回忆的有bug的伪代码(有点忘了)
    //dp数组初始化为0
for(int i=1;i<=一共有几个宿舍;++i){
    for(int b=0;b<=四人桌个数;++b){
        for(int c=0;c<=4;++c){
            for(int d=0;d<=六人桌个数;++d){
                for(int e=0;e<=6;++e){
                    //不选的情况
                    f[i][b][c][d][e]=f[i-1][b][c][d][e];
                    //合并一下新开一桌的情况
                    if(b!=0)
                        f[i][b][c][d][e]=max(f[i][b][c][d][e],f[i-1][b-1][4][d][e]);
                    if(d!=0)
                        f[i][b][c][d][e]=max(f[i][b][c][d][e],f[i-1][b][c][d-1][6]);
                    //就是选在当前桌的情况
                    if(c>=arr[i])//四人桌
                        f[i][b][c][d][e]=max(f[i][b][c][d][e],f[i-1][b][c-arr[i]][d][e]+arr[i]);
                    if(e>=arr[i])//六人桌
                        f[i][b][c][d][e]=max(f[i][b][c][d][e],f[i][b][c][d][e-arr[i]]+arr[i]);
                }
            }
        }
    }
}
输出:f[宿舍个数][b4][4][b6][6]


自己造了一个样例
    1
    2 2 1 2 1
    这样就是这个没过去
        2个两人宿舍
        2个三人宿舍
        1个四人宿舍
        2个四人桌
        1个六人桌
    答案应该是14，但是不知道为什么这个代码算出来是12

应该就是这个做法，但是我不知道哪里出错了

最大时间复杂度:$O(100*6*100)$

试题 E: 最优分组

我没学期望，用高中知识现推的，只验证了题目给的样例，但是不知道对不对

思路：枚举每组的宠物数，取最大期望

特判下每组个数为1

这里我没用快速幂，但是自己测试了下最大的那个样例挺快的，应该能过

时间复杂度：$O(宠物总数*算幂的)$应该是能过

试题 F: 星际旅行

这次这么爱靠期望是吧，还好这题解释样例了

思路：暴力：每个盲盒都用bfs最短路(边权都1么)

根据bfs的二段性，当前搜的结点如果距离起点的距离>=传送门次数就需要break了

这里我没做啥优化，存暴力

时间复杂度：$O(盲盒数*（点数+边数）)$，有点极限，但是也来不及整优化了

试题 G: LITS 游戏

以我的实力一看就是做不出来，感觉像大模拟

试题 H: 拼十字

感觉这题都比前面好想

思路：暴力两重循环就完事了，可能有几个样例过不了，需要一点优化，我这随便糊了手指针优化，也不一定对

（靠着印象写下考场写的那一坨）
枚举每种组合:
class Node{
    int x,y,z;//长，宽，颜色
    //实现下CompareTo
        //这里按z排
            //能形成三段 z=0,1,2;颜色有明显的分界
}
Node[] g;//从1开始存下所有的矩形

sort(g+1,g+n+1);//
int flag=1;//指针小优化,因为这里有明显的颜色分解
g=new Node(0,0,0);//一个虚拟边界
long res=0;
for(int i=1;i<=n;++i){
    if(g[i-1].z!=g[i].z)//看看是不是到了新的颜色
        flag=i;
    for(int j=flag+1;j<=n;++j){
        if(g[i].z!=g[j].z){//不同颜色
            if(g[i].x<g[j].x&&g[i].y>g[j].y||g[i].x>g[j].x&&g[i].y<g[j].y)
                ++res;
        }else{//排序后还在同颜色的段
            flag=j;//最后应该是落在不同颜色的分界线(大概，需要别把自己优化没了)
        }
    }
}

这个感觉时间复杂度应该挺好的，但是还是有点小极限