首页 > 其他分享 >Acwing2024蓝桥杯DFS

Acwing2024蓝桥杯DFS

时间：2024-04-09 23:00:48浏览次数：27  
标签：head int DFS 蓝桥 flag dfs Acwing2024 include id

模板:

AcWing 826. 单链表

利用数组创建单链表:

#include<iostream>
using namespace std;
const int N=100005;
int head,value[N],nextt[N],id;
void Init(){
    head=-1,id=0;
}
void Head_Insert_x(int x){
    value[id]=x;
    nextt[id]=head;
    head=id++;
}
void Delete_k(int k){
    nextt[k]=nextt[nextt[k]];
}
void Insert_k_x(int k,int x){
    value[id]=x;
    nextt[id]=nextt[k];
    nextt[k]=id++;
}
int main(){
    int n;
    cin>>n;
    Init();
    while(n--){
        char ch;
        cin>>ch;
        if(ch=='H'){
            int x;
            cin>>x;
            Head_Insert_x(x);
        }
        if(ch=='D'){
            int k;
            cin>>k;
            if(k) Delete_k(k-1);
            else head=nextt[head];
        }
        if(ch=='I'){
            int k,x;
            cin>>k>>x;
            Insert_k_x(k-1,x);
        }
    }
    for(int i=head;i!=-1;i=nextt[i])
        cout<<value[i]<<" ";
    return 0;
}

邻接表模板

利用数组创建邻接表:

//对于每个点,开一个单链表,存储所有可以走到的点
//head存储这个单链表的头结点
//value存储结点的值
//nextt存储结点的next指针
//id表示当前用到的点的位置
int head[N],value[N],nextt[N],id;
//添加一条边a->b
void add(int a,int b){
    value[id]=b;
    nextt[id]=head[a];
    head[a]=id++;
}
//初始化
id=0;
memset(h,-1,sizeof(head));

树与图的dfs以及bfs模板:

void dfs(int x){
    flag[x]=true;
    for(int i=head[x];i!=-1;i=nextt[i]){
        int j=value[i];
        if(!flag[j]){
            dfs(j);
        }
    }
}


queue<int>q;
flag[1]=true;
q.push(1);
while(q.size()){
    int t=q.front();
    q.pop();
    for(int i=head[t];i!=-1;i=nextt[i]){
        int j=value[i];
        if(!flag[j]){
            flag[j]=true;
            q.push(j);
        }
    }
}

题目:

AcWing 2060. 奶牛选美

#include<iostream>
#include<vector>
#include<cmath>
using namespace std;
int n,m;
char map[55][55];
typedef pair<int,int>pii;//行列坐标
vector<pii>point[2];     //创建两个二维vector数组
int dx[4]={-1,0,1,0};    //x方向
int dy[4]={0,1,0,-1};    //y方向
void dfs(int xx,int yy,vector<pii>&p){
    //把xx,yy坐标存入vector中
    p.push_back({xx,yy});
    //消除已经存过的X
    map[xx][yy]='.';
    //枚举四个方向
    for(int i=0;i<4;i++){
        int tx=xx+dx[i];
        int ty=yy+dy[i];
        //判断能否继续dfs
        if(tx>0&&tx<=n&&ty>0&&ty<=m&&map[tx][ty]=='X') dfs(tx,ty,p);
    }
}
int main(){
    //输入
    cin>>n>>m;
    for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) cin>>map[i][j];
    //遍历
    int k=0;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            //如果是X,开始dfs
            if(map[i][j]=='X')
                dfs(i,j,point[k++]);//第一次dfs完,让k自增,进入第二个区域进行dfs
    //遍历两个区域
    int ans=1e9;
    for(int i=0;i<point[0].size();i++)
        for(int j=0;j<point[1].size();j++)
            //更新ans
            ans=min(ans,abs(point[0][i].first-point[1][j].first)+abs(point[0][i].second-point[1][j].second)-1);
    //输出
    cout<<ans<<endl;
    return 0;
}

补充:洛谷P5318 【深基18.例3】查找文献

利用vector创建图,注意这题要排序:

#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
const int N=1e5+5;
int n,m;
vector<int>G[N];
bool flag[N];
void dfs(int x){
    if(flag[x]) return;
    flag[x]=true;
    cout<<x<<" ";
    for(auto t:G[x]){
        if(!flag[t]){
            dfs(t);
        }
    }
}
void bfs(){
    queue<int>q;
    flag[1]=true;
    q.push(1);
    while(q.size()){
        int x=q.front();
        q.pop();
        cout<<x<<" ";
        for(auto t:G[x]){
            if(!flag[t]){
                flag[t]=true;
                q.push(t);  
            }
        }
    }
}
int main(){
    cin>>n>>m;
    for(int i=0;i<m;i++){
        int a,b;
        cin>>a>>b;
        G[a].push_back(b);
    }
    for(int i=1;i<=n;i++) sort(G[i].begin(),G[i].end());
    dfs(1);cout<<endl;
    memset(flag,0,sizeof(flag));
    bfs();cout<<endl;
    return 0;
}

 或者利用set(自带有序并且不重复):

#include<iostream>
#include<set>
#include<cstring>
#include<queue>
using namespace std;
const int N=1e5+5;
int n,m;
set<int>G[N];
bool flag[N];
void dfs(int x){
    if(flag[x]) return;
    flag[x]=true;
    cout<<x<<" ";
    for(auto t:G[x]){
        if(!flag[t]){
            dfs(t);
        }
    }
}
void bfs(){
    queue<int>q;
    flag[1]=true;
    q.push(1);
    while(q.size()){
        int x=q.front();
        q.pop();
        cout<<x<<" ";
        for(auto t:G[x]){
            if(!flag[t]){
                flag[t]=true;
                q.push(t);  
            }
        }
    }
}
int main(){
    cin>>n>>m;
    for(int i=0;i<m;i++){
        int a,b;
        cin>>a>>b;
        G[a].insert(b);
    }
    dfs(1);cout<<endl;
    memset(flag,0,sizeof(flag));
    bfs();cout<<endl;
    return 0;
}

补充:洛谷 P3916 图的遍历

利用vector创建图:

#include<iostream>
#include<vector>
using namespace std;
const int N=1e5+5;
int n,m,ans[N];
vector<int>G[N];
void dfs(int x,int maxx){
    //如果已经存储过答案,直接返回
    if(ans[x]) return;
    //否则存储答案
    ans[x]=maxx;
    //遍历该行,继续dfs
    for(int i=0;i<G[x].size();i++) dfs(G[x][i],maxx);
}
int main(){
    //输入
    cin>>n>>m;
    for(int i=0;i<m;i++){
        int a,b;
        cin>>a>>b;
        //反向建图
        G[b].push_back(a);
    }
    //从大到小遍历
    for(int i=n;i>=1;i--) dfs(i,i);
    //输出
    for(int i=1;i<=n;i++) cout<<ans[i]<<" ";
    return 0;
}

AcWing 846. 树的重心

利用数组创建邻接表:

#include<iostream>
#include<cstring>
using namespace std;
const int N=1e5+5;
int head[N],value[2*N],nextt[2*N],id;
void add(int a,int b){
    value[id]=b;
    nextt[id]=head[a];
    head[a]=id++;
}
int n,ans=N; //表示重心的所有的子树中,最大的子树的结点数目
bool flag[N];//记录节点是否被访问过,访问过则标记为true
//返回以x为根的子树中节点的个数(包括x节点)
int dfs(int x){
    int sum=1;//存储以x为根的树的节点数(包括x节点)
    int res=0;//存储删掉x节点之后,最大的连通子图节点数
    flag[x]=true;
    //遍历x的每个子节点
    for(int i=head[x];i!=-1;i=nextt[i]){
        int j=value[i];
        if(!flag[j]){
            int temp=dfs(j);
            sum+=temp;
            res=max(res,temp);
        }
    }
    res=max(res,n-sum);//选择x节点为重心后,最大的连通子图节点数
    ans=min(res,ans);  //遍历过的假设重心后,最小的最大联通子图的节点数
    return sum;
}
int main(){
    id=0,memset(head,-1,sizeof(head));
    cin>>n;
    //邻接表存储无向图
    for(int i=0;i<n-1;i++){
        int a,b;
        cin>>a>>b;
        add(a,b),add(b,a);
    }
    //从1开始dfs
    dfs(1);
    //输出
    cout<<ans<<endl;
    return 0;
}

利用vector创建图:

#include<iostream>
#include<vector>
using namespace std;
const int N=1e5+5;
int n,ans=N;
bool flag[N];
vector<int>G[N];
int dfs(int x){
    int sum=1;
    int res=0;
    flag[x]=true;
    for(int i=0;i<G[x].size();i++){
        int j=G[x][i];
        if(!flag[j]){
            int temp=dfs(j);
            sum+=temp;
            res=max(res,temp);
        }
    }
    res=max(res,n-sum);
    ans=min(ans,res);
    return sum;
}
int main(){
    cin>>n;
    for(int i=0;i<n-1;i++){
        int a,b;
        cin>>a>>b;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    dfs(1);
    cout<<ans<<endl;
    return 0;
}

AcWing 1207. 大臣的旅费(第四届省赛)

题目本质->数的直径:任取图中一个节点，找到离这个节点最远的节点，在去寻找离那个最远节点的最远节点，这样两个最远节点之间就是树的路径了

#include<iostream>
#include<vector>
using namespace std;
const int N=1e5+5;
vector<int>G[N];//存储图
vector<int>L[N];//存储权值
int n,id;       //id表示当前到哪一个位置
bool flag[N];   //状态数组
long long ans=-1e5; //答案
//计算路费
long long cost(long long x){
    return (x+21)*x/2;
}
//dfs(当前位置,当前所走的路程)
void dfs(int startt,long long res){
    if(res>ans){  //如果路程变大了
        ans=res;  //更新答案
        id=startt;//更新当前位置
    }
    //遍历当前startt的所有路径
    for(int i=0;i<G[startt].size();i++){
        int temp=G[startt][i];
        if(flag[temp]) continue;   //如果该路径已经被选中,就继续枚举
        flag[temp]=true;           //否则,更新状态数组
        dfs(temp,res+L[startt][i]);//继续dfs
        flag[temp]=false;          //回溯
    }
}
int main(){
    //输入
    cin>>n;
    for(int i=0;i<n;i++){
        int p,q,d;
        cin>>p>>q>>d;
        //双向存储
        G[p].push_back(q);
        G[q].push_back(p);
        L[p].push_back(d);
        L[q].push_back(d);
    }
    //从1开始
    flag[1]=true;
    dfs(1,0);
    flag[1]=false;//回溯
    ans=-1e5;     //重置ans,准备第二次dfs
    flag[id]=true;//从当前位置id开始dfs
    dfs(id,0);
    //输出
    cout<<cost(ans)<<endl;
    return 0;
}

AcWing 4407. 扫雷(第十三届省赛)

暴力法(40 points):

#include<iostream>
#include<cmath>
#define f first
#define s second
using namespace std;
const int N=1e5+5;
typedef pair<pair<int,int>,int>piii;
piii boom[N],rocket[N];
bool flag[N];
int n,m,ll,rr;
bool check(piii a,piii b){
    int x1=a.f.f,y1=a.f.s;
    int x2=b.f.f,y2=b.f.s;
    float distance=sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
    return distance<=a.s;
}
int main(){
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=0;i<n;i++){ //0到n-1存的都是炸弹信息
        int x,y,r;
        cin>>x>>y>>r;
        boom[rr++]={{x,y},r};
    }
    rr=0;
    for(int i=0;i<m;i++){ //0到m-1存的都是排雷火箭的信息
        int x,y,r;
        cin>>x>>y>>r;
        rocket[rr++]={{x,y},r};
    }
    int ans=0;
    while(ll<=rr){              //while循环枚举排雷火箭(ll为左指针,rr为右指针)
        piii temp=rocket[ll++]; //移动左指针
        for(int i=0;i<n;i++){   //for循环枚举炸弹
            if(!flag[i]&&check(temp,boom[i])){//如果没被选中并且在范围内
                flag[i]=true;                 //就选中
                //注意:同时，当炸雷被引爆时，在其爆炸范围内的炸雷也会被引爆
                rocket[rr++]=boom[i];         //因此把选中的炸雷变成排雷火箭,并且移动右指针
                ans++;                        //答案自增
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}

考试时候能把这40points得到就心满意足了......

标签：head,int,DFS,蓝桥,flag,dfs,Acwing2024,include,id
From： https://blog.csdn.net/2301_76144982/article/details/137514986

相关文章

  • 杨辉三角形（蓝桥杯，acwing）
    题目描述：下面的图形是著名的杨辉三角形：如果我们按从上到下、从左到右的顺序把所有数排成一列，可以得到如下数列：1,1,1,1,2,1,1,3,3,1,1,4,6,4,1,...给定一个正整数 N，请你输出数列中第一次出现 N 是在第几个数？输入格式:输入一个整数 N。输出格式:输......
  • 蓝桥杯-公平抽签
    0.题目题目描述小A的学校，蓝桥杯的参赛名额非常有限，只有m个名额，但是共有n个人报名。作为老师非常苦恼，他不知道该让谁去，他在寻求一个绝对公平的方式。于是他准备让大家抽签决定，即m个签是去，剩下的是不去。小A非常想弄明白最后的抽签结果会有多少种不同到情况，请你设计一......
  • 蓝桥杯 强者挑战赛9
    标算无理数位数查询LL没开全，WA想不太清楚细节，写了半个多小时。。。预处理而不是现算会好写一点赛时做法先确定第\(n\)位所属的数的位数，再确定该位数中第\(k\)大的数标算设\(g(x)\)表示\(m\)进制下\(1\simx\)的位数和，二分第\(n\)位所属的数贝贝的集合先不......
  • 蓝桥杯之初等数论
    在蓝桥杯竞赛中，初等数论部分涉及多个关键知识点。以下是对这些知识点的详细列出、基本概念解释、应用实例以及解题策略和步骤的说明：1.质数与合数基本概念：质数（素数）：大于1的自然数中，只能被1和它本身整除的数。合数：除了1和它本身以外还有其他因数的自然数。应用实例：题目：......
  • 蓝桥杯-外卖店优先级
     代码及其解析#include<bits/stdc++.h>usingnamespacestd;constintN=100010;intorder[N];//order[id]第id号店上一次的订单,记录的是时间intprior[N];//prior[id]第id号店的优先级intflag[N];//flag[id]第id号店在不在优先缓存中structnode{......
  • 蓝桥杯-【二分】求阶乘
     思路:对于有几个0，10一定会是5的整数倍，2的因子数一定比5的多，所以只要算5的个数即可， 30%，每个n都去算#include<bits/stdc++.h>usingnamespacestd;#definelllonglongllcheck(lln){//计算n!末尾有多少个0llcnt=0;while(n)cnt+=......
  • P8625 [蓝桥杯 2015 省 B] 生命之树
    题目：链接：https://www.luogu.com.cn/problem/P8625基本思路：1.使用dp[N]记录i节点的当前最大值2.使用vectornex[N]记录图3.使用vis[N]防回退如果该节点没有子节点，那么这个点的最大值就记录为当前的值：val如果该节点有子节点，那么先遍历子节点，然后+res并记录由于使用了vis，那么......
  • 蓝桥杯历年试题 砝码称重
    看到这个题，自然而然想到用集合set来做，因为set本身就有去重的效果。#include<bits/stdc++.h>usingnamespacestd;intN;intw;set<int>s;intmain(){ cin>>N; for(inti=1;i<=N;i++) { cin>>w; vector<int>v(s.begin(),s.end()); //这里需要用v......
  • 【每周例题】蓝桥杯 C++ 多数
    多数元素题目多数元素思路分析一.第一个想法，暴力遍历，然后会发现容易超时，那么更进一步想：哈希表使用哈希表存储每个数出现的次数，即使用哈希映射（HashMap）来存储每个元素以及出现的次数。对于哈希映射中的每个键值对，键表示一个元素，值表示该元素出现的次数加入后，遍历所有键值对，......
  • HDFS报错：Couldn‘t preview the file.
    packagecom.qm.hdfs;importorg.apache.hadoop.conf.Configuration;importorg.apache.hadoop.fs.FileSystem;importorg.apache.hadoop.fs.Path;importorg.junit.After;importorg.junit.Before;importorg.junit.Test;importjava.io.IOException;importjava.n......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99