当前位置:   article > 正文

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

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

个人在比赛时写的思路,当然不一定对

2024 第十五届蓝桥杯JavaB组省赛思路简述

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

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

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

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

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

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

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

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

试题 A: 报数游戏

数论不太扎实,所以先用TreeSet集合(排序去重)写了个暴力程序,来找找规律

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

(当然也不定对,当时很烦躁,指看了前几个)

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

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

我考场上算出来的结果好像是以 4288 4288 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能过
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13

有个小细节要注意,要用while(sc.hasNext())

这里我缺个特判点,应该会错部分数据

就是每次同步时,万一队列中没有元素,就一直在同步

2
sync 2
sync 2
add 2
query
    
    答案为0
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7

试题 D: 食堂

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

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

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

我的思路就是:转为01背包(超级无敌多个状态,我都不敢优化)

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

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

看看有无大佬能帮我看看

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

食堂思路.jpg

//考后回忆的有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
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37

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

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

试题 E: 最优分组

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

思路:枚举每组的宠物数,取最大期望

特判下每组个数为1

IMG20240413183350.jpg

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

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

试题 F: 星际旅行

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

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

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

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

时间复杂度: O ( 盲盒数 ∗ (点数 + 边数) ) O(盲盒数*(点数+边数)) O(盲盒数(点数+边数)),有点极限,但是也来不及整优化了

赛后想了个优化,也是这个思路,但是上面这个会重复搜
所以,可以预处理下把每个结点当作起点搜索的结果:

数组cnt[起点][距离当前起点的距离],然后把每个点当作起点,都预处理下,搜下全局,每遇到一个新的距离,都存进这个数组中
时间复杂度大概为: O ( 1000 ∗ ( 5000 + 1000 ) ) O(1000*(5000+1000)) O(1000(5000+1000)),这时候肯定能过

试题 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;//最后应该是落在不同颜色的分界线(大概,需要别把自己优化没了)
        }
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26

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

啊,想哭隔一天看的时候发现忘记取模了,不过幸好取模的情况基本都会tle,唉,安慰下自己

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/繁依Fanyi0/article/detail/429931
推荐阅读
相关标签
  

闽ICP备14008679号