历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

蓝桥杯考前鲤鱼锦囊(第二期）

作者：

寸铁 , 2023-04-07 20:11:08 , 所有人可见 , 阅读 416

1

2

兵贵神速实时更新

蓝桥杯考前鲤鱼锦囊(第二期）

冲刺蓝桥杯省一模板大全来啦 ~

蓝桥杯4月8号明天就要开始了 ~

距离蓝桥杯省赛倒数最后1天

还没背熟模板的伙伴们背起来

真题千千万万遍，蓝桥省一自然现！

日更3000里，蓝桥眷顾你

暴力出奇迹，打表过样例

祝大家4月8号蓝桥杯上岸 ~

不清楚蓝桥杯考什么的点点下方

考点秘籍

蓝桥杯竞赛干货

算法竞赛字符串常用操作总结！！！

锦囊妙计

蓝桥杯考前鲤鱼锦囊(第一期）

往期回顾

蓝桥杯上岸每日N题第一期(一)！！！

蓝桥杯上岸每日N题第一期(二)！！！

蓝桥杯上岸每日N题第一期(三)！！！

蓝桥杯上岸每日N题第二期(一)！！！

蓝桥杯上岸每日N题第三期(一)！！！

蓝桥杯上岸每日N题第四期(最少刷题数)！！！

蓝桥杯上岸每日N题第五期(山)！！！

蓝桥杯上岸每日N题第六期(求阶乘)！！！

蓝桥杯上岸每日N题第七期(小猫爬山)！！！

蓝桥杯上岸每日N题第八期(全球变暖)！！！

蓝桥杯上岸必刷专题

蓝桥杯上岸必刷！！！(日期专题+保姆级教学)

蓝桥杯上岸必刷！！！(字符串专题)

蓝桥杯上岸必刷！！！(模拟/枚举专题)

蓝桥杯上岸必刷！！！(进制、数位专题)

想背纯享模版的伙伴们点点下方

蓝桥杯省一你一定不能错过的模板大全(第一期)

蓝桥杯省一你一定不能错过的模板大全（第二期）

蓝桥杯省一你一定不能错过的模板大全（第三期）

想背注释模版的伙伴们点点下方

蓝桥杯必背第一期

蓝桥杯必背第二期

蓝桥杯上岸必背！！！ (第三期 DP)

蓝桥杯上岸必背！！！(第四期DFS)

蓝桥杯上岸必背！！！(第五期BFS)

蓝桥杯上岸必背！！！(第六期树与图的遍历)

蓝桥杯上岸必背！！！(第七期最短路算法)

蓝桥杯上岸每日N题第七期(小猫爬山)！！！

想看JavaB组填空题的伙伴们点点下方

填空题

前言

蓝桥杯明天就要开始啦~还没刷题的同学跟我一起来刷历年真题，考前鲤鱼锦囊来啦

老爷保佑

喜欢的小伙伴可以关注我，关注寸铁，我们一起上岸4.8蓝桥杯！！！

鲤鱼跃龙门，蓝桥必上岸！！！

稀疏图用邻接表，稠密图用邻接矩阵

初始化

很多时候我们背模板背完了，发现TLE/WA/MLE

这可能不一定是模板背错了，更有可能是未初始化。

在背出模板前，一定要想清楚是否已初始化。

建议背诵步骤：

(1)初始化(数组、起点、终点等特殊点)

(2)背整体的思路框架

(3)核心逻辑及实现细节

距离初始化：

一维：

Arrays.fill(dist,-1);
Arrays.fill(dist,INF);

二维：

Arrays.fill(dist[i],-1);
Arrays.fill(dist[i],INF);

三维：

Arrays.fill(dist[i][j],INF);

邻接表存边：

注意：用邻接表存边h[]一定记得初始化！！！

同时像最短路/BFS存在比较最短路问题时一般是先将距离初始化成INF

在最短路算法中，初始化h[]、dist[]很关键，不初始化会TLE，陷入死循环！！！

一般在main（）方法中初始化：

初始化方式：

(1)Arrays.fill(h,-1);
(2)for(int i=0;i<n;i++){
h[i]=-1;
}

实现方式：

边权不加入add方法中

public static void add(int a,int b){

e[idx]=b;

ne[idx]=h[a];

h[a]=idx;

idx++;

}

边权加入add方法中

public static void add(int a,int b,int c){

e[idx]=b;

w[idx]=c;//赋权，spfa()

ne[idx]=h[a];

h[a]=idx;

idx++;

}

邻接矩阵存边

实际上是二维数组的存储**，a–>b连一条边且权值为c。

while(m-->0){

int a=sc.nextInt();

int b=sc.nextInt();

int c=sc.nextInt();

g[a] [b]=Math.min(g[a] [b],c);//a-->b连边，重复边取最小值

//常规：g[a] [b]=c;

}

初始化数组：

像一些图论问题，往往需要初始化边的距离！！！

(1)写法1

static int INF=0x3f3f3f3f;

Arrays.fill(dist,INF)；//一维数组

初始化g[][]每个点的距离为INF

Arrays.fill(g[i],INF);

(2)写法2

for(int i=1;i<=n;i++){

dist[i]=INF;

}

java容器:Queue实现出入队

Queue<Integer>q=new LinkedList<Inetger>();
//入队
q.add(x);
q.add(x,y)
q.add(new PII(x,y));//结构体
//出队
q.poll();

BFS常用模板1

以图中点的层次为例

hh=0;
tt=-1;
q[++tt]=1;
//入队
while(hh<=tt){
    int t=q[hh++];
    //出队
    //遍历所有邻接点/出边
    for(int i=h[t];i!=-1;i=ne[i]){
        int j=e[i];
        if(d[j]==-1){//该点未被遍历过
            d[t]=d[j]+1;//更新距离
            q[++tt]=j;//入队
        }
    }
}

BFS常用模板2

以全球变暖为例

while(!q.isEmpty()) {
            pair t=q.poll();
            res++;
            boolean isbound=false;
            for(int i=0;i<4;i++) {
                int a=t.x+dx[i];
                int b=t.y+dy[i];
                if(a<0||a>=n||b<0||b>=n)continue;
                if(st[a][b])continue;
                if(g[a][b]=='.') {
                    isbound=true;
                    continue;
                }
                q.add(new pair(a, b));
                st[a][b]=true;
            }
        if(isbound)bound++; 
        }
        return res==bound;
    }