• 算法竞赛入门【码蹄集进阶塔335题】(MT2316-2320）

    算法竞赛入门【码蹄集进阶塔335题】(MT2316-2320）

    文章目录

    前言

    在这里插入图片描述

    为什么突然想学算法了？

    > 用较为“官方”的语言讲，是因为算法对计算机科学的所有分支都非常重要。 在绝大多数的计算机科学分支领域中，要想完成任何实质性的工作，理解算法的基础知识并掌握与算法密切相关的数据结构知识是必不可少的。
    > 但从实际而言，是因为当下快到了考研和找工作的年纪(ಥ_ಥ)，无论走哪一条路，都不免需要一些相对丰富的算法知识，是故，便产生了一个暑假速成算法的计划，可能对于像我这种算法竞赛小白而言，几乎很难，但我仍然还是想尝试一下，毕竟，梦想还是要有的，万一实现了呢？～(￣▽￣～)~

    在这里插入图片描述

    为什么选择码蹄集作为刷题软件？

    码蹄集，是在全国高等学校计算机教学与产业实践资源建设专家委员会(TIPCC) 指导下建设的，其依托全国各大名校计算机系和清华大学出版社等单位的强大资源，旨在为计算机学习爱好者提供全面和权威的计算机习题。
    在这里插入图片描述

    目录

    1. MT2316 欧拉路径

    （1）题目描述
    如果图G中的一个路径包括每个边恰好一次，则该路径称为欧拉路径(Eulerpath)。输入一个有向图，请你判断这个有向图上是否存在欧拉路径。

    格式

    输入格式:
    第一行两个整数n和m，表示有n个结点和m条有向边。接下来m行输入m条有向边的信息，每行两个整数α和b，分别表示边的起点和终点的编号（编号为1~n )，即该条有向边从a到b。
    .
    输出格式: 输出一个字符串Yes或No，表示这个有向图上是否存在欧拉路径。

    样例1

    输入格式:
    4 3
    1 2
    2 3
    3 4
    .
    输出格式: Yes

    样例2

    输入格式:
    4 8
    1 2
    1 3
    1 4
    2 3
    2 3
    3 2
    3 4
    4 3
    .
    输出格式: No

    备注：

    保证:对于100%的数据:1≤n ≤100,000，m ≤ 1,000,000 。

    （2）参考代码

    #include 
using namespace std;
#define MAXN_EAGE 2000100
#define MAXN 100100
struct node{
    int v,nx;
}node[MAXN_EAGE];
int tot;
int head[MAXN];
int n,m,tn;
bool flag[MAXN];
bool goal;
void add_eage(int u,int v){
    node[tot].v=v;
    node[tot].nx=head[u];
    head[u]=tot;
    tot++;
}
void dfs(int s){
    flag[s]=true;
    for (int i=head[s];i!=-1;i=node[i].nx){
        int v = node[i].v;
        if (!flag[v]){
            dfs(node[i].v);
        }
    }
}
int myin[MAXN],myout[MAXN];
void init(int n){
    memset(myin,0,sizeof(myin));
    memset(myout,0,sizeof(myout));
    goal=false;
    memset(head,-1,sizeof(head));
    memset(flag,0,sizeof(flag));
    tot=0;
    tn=1;
}
int main (){
    int n,m;
    while (cin>>n>>m){
        init(n);
        for (int i=0;i<m;i++){
            int u,v;
            cin>>u>>v;
            add_eage(u,v);
            add_eage(v,u);
            myout[u]++;
            myin[v]++;
        }
        int t=0,t1=0,t2=0;
        dfs(1);
        for (int i=1;i<=n;i++){
            if (!flag[i]){
                t=-1;
                goal=false;
                break;
            }
            if (myout[i]-myin[i]==1){
                t1++;
            }else if (myout[i]-myin[i]==-1){
                t2++;
            }
            if (myout[i]!=myin[i]){
                t++;
            }
        }
        if (t==0){
            goal=true;
        }else if (t==2 && t1==1 && t2==1){
            goal=true;
        }
        puts(goal?"Yes":"No");
    }
    return 0;
}

    • 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
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75

    2. MT2317 匹配图

    （1）题目描述
    小码哥有一张n个点m条边的图，i号结点的点权是ai。

    请找出3个两两相连的点，求出最小的价格之和，如果找不到这样的3个点就输出-1。

    格式

    输入格式:
    第一行包含2个整数n，m ,
    接下来一行n个正整数表示ai，
    接下来m行每行两个数表示a y之间存在着一条无向边。其中: 3≤n ≤100，3≤m≤ n(n-1)/2，1≤ai≤1e6 。
    .
    输出格式: 一行一个整数表示答案，无解输出―1

    样例1

    输入格式:
    3 3
    1 2 3
    1 2
    2 3
    3 1
    .
    输出格式:
    6

    （2）参考代码

    #include 

using namespace std;
const int N=100;
const int inf=1e8;
int n,m,mp[N][N],g[N][N],price[N],next[N],res=inf;
vector<int> v;

void floyd(){
 res=inf;
 for(int k=1;k<=n;k++){
 for(int i=1;i<k;i++)
 for(int j=i+1;j<k;j++){
 int num=res;
 res=min(res,g[i][j]+mp[i][k]+mp[k][j]);//满足题目条件的3
 }
 }
 }
 int main(){
 scanf("%d %d",&n,&m);
 for(int i=1;i<=n;i++){
 scanf("%d",&price[i]);
 }
 for(int i=1;i<=n;i++){
 for(int j=1;j<=n;j++){
 if(i!=j){
 mp[i][j]=g[i][j]=inf;
 }
 }
 }
 for(int i=1;i<=m;i++){
 int u,v;
 scanf("%d %d",&u,&v);
 mp[u][v]=mp[v][u]=g[u][v]=g[v][u]=min(price[u]+price[v],mp[u][v]);
 }
 floyd();
 if(res==inf){
 cout<<-1<<endl;
 }else{
 cout<<res/2<<endl;
 }
 return 0;
 }

    • 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
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43

    3. MT2318 事务处理2

    （1）题目描述
    小码哥最近忙得焦头烂额，有n个事情需要他处理，这n个事情有一个编号,编号从1到n，编号越靠前的事情越重要，越需要优先处理。但是有些事情是需要某些提前事情完成的，比如说，炒菜一定在洗菜之后，我们用(i,j)来表示，必须先做i ,才能做j;

    现在小码哥希望越重要的事情就越先做，即:如果事情i是当前没有做的事情中重要程度最大的，就一切准备工作都为做à来做准备，尽可能的让i完成。以此类推，直到做完所有事情;

    格式

    输入格式:
    第一行两个用空格分开的正整数n和m，分别表示事情数目和完成顺序限制的条目数。
    接下来m行，每行两个正整数a, y，表示a号事情必须先于y号事情制作的限制。
    .
    输出格式:
    一行， n个整数，表示最优的事务的处理顺序，或者Impossible!表示无解

    样例1

    输入格式:
    5 4
    5 4
    5 3
    4 2
    3 2
    .
    输出格式: 1 5 3 4 2

    （2）参考代码

    #include
#define x first
#define y second
#define bug(x) cerr<<#x<<'='<<x<<' '
#define debug(x) cerr<<#x<<'='<<x<<'\n'
#define FOR(a,b,c) for(int a=(b),a##_end=(c);a<=a##_end;++a)
#define ROF(a,b,c) for(int a=(b),a##_end=(c);a>=a##_end;--a)
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int INF=0x3f3f3f3f,N=4e5+10;
template<class T>inline bool chkmin(T &x,const T &y){return y<x?x=y,1:0;}
template<class T>inline bool chkmax(T &x,const T &y){return x<y?x=y,1:0;}
int n,m,de[N],vis[N];
int res[N],tot;
queue<int>que;
vector<int>E[N],G[N],t[N];
void dfs(int x,int anc){
    if(x!=anc)
        t[anc].push_back(x);
    for(int y:G[x])if(!vis[y])
        dfs(y,anc);
}
void solve(int x){
    dfs(x,x);
    sort(t[x].begin(),t[x].end());
    for(int y:t[x])
        if(!vis[y])
            solve(y);
    vis[x]=1;
    res[++tot]=x;
    t[x].clear();
}
int main(){
    scanf("%d%d",&n,&m);
    assert(n<=100000);
    FOR(i,1,m){
        int x,y;
        scanf("%d%d",&x,&y);
        if(x==y)continue;
        E[x].push_back(y);
        G[y].push_back(x);
        de[y]++;
    }
    FOR(i,1,n)if(de[i]==0)
        que.push(i);
    while(!que.empty()){
        ++tot;
        int x=que.front();que.pop();
        for(int y:E[x])
            if((--de[y])==0){
                que.push(y);
            }
    }
    if(tot!=n)puts("Impossible!");
    else{
        tot=0;
        FOR(i,1,n)if(!vis[i])
            solve(i);
        FOR(i,1,n)printf("%d ",res[i]);
    }
    return 0;
}

    • 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
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63

    4. MT2319 高塔的庇佑

    （1）题目描述
    彼时的蒙德，冰天雪地，目力所及处都是冻土，无法生存。高塔孤王发动神力，建造了一座高塔，散发出强烈的光和热，庇佑着蒙德的人民

    蒙德地形可简化为一个n * m的矩阵，每个点代表1单位面积，且每个点都有一个高度。

    在坐标a，y的地方建立了一座高为h的高塔，高塔能让与它距离在r以内的冻土重新焕发生机。

    现在请问得到庇护的土地面积有多少

    格式

    输入格式:
    3 3 1 5 2 2
    1 1 1
    1 0 1
    1 1 1
    .
    输出格式: 9

    备注：

    其中: 0

    （2）参考代码

    #include 
using namespace std;
typedef long long ll;
ll i,j,k,n,m,t,h,r,x,y,res;
int main() {
    ios::sync_with_stdio(0);
    cin>>n>>m>>h>>r>>x>>y;
    for(i=1;i<=n;i++)for(j=1;j<=m;j++){
        cin>>k;
        res+=((i-x)*(i-x)+(j-y)*(j-y)+(k-h)*(k-h)<=r*r);
    }
    cout<<res;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13

    5. MT2320 蛇形走位

    （1）题目描述
    小码哥正在模拟系统里练习蛇形走位，他操控的角色会在一个无穷大的网格上(可以想象为笛卡尔坐标系）移动。刚开始时小码哥操控的角色出现在地图中心点，现在给出他的路径指令，uDLR分别表示往上下左右走1个单位长，走过的地方会留下标记，角色身上带有一个探测仪，可以探测前方(移动方向)和左右1个单位是否存在标记，如果存在发出BuG 警告并终止本次练习，否则继续移动，直到指令结束都未发出警告，则表示完成本次练习，输出oK。

    格式

    输入格式:
    输入一行长度不超过100且不为空的字符串，包含字符如题所述
    .
    输出格式: 按题意输出OK或BUG

    样例1

    输入格式: RRUULLDD
    .
    输出格式: BUG

    （2）参考代码

    #include 
 
using namespace std;
 
const int M = 1e5+1;
 
struct point{
	int x = 0;
	int y = 0;
	int z = 0;
    // int max;
    // int end;
}p[M];
 
bool com(point p1, point p2){
    return p1.x < p2.x;
}
 
struct res{
    int end = 0;
    int len = 0;
}s[M];
 
 
int main(){
	int n,m;
	cin >> n >> m;
	int t, x, y ,z;
	for(int i=0;i<m;i++){
		cin >> t;
        p[t].x = t;
        cin >> y >> z;
        if(p[t].z < z){
            p[t].z = z;
            p[t].y = y;
         } 
	}
	
    for(int i=1;i<=n;i++){
        if(p[i].x != 0){
//            cout <
            cout  << p[i].y << " " << p[i].z << endl;
        }
        else{
            cout << 0 << endl;
        }
    }
	return 0;
}

    • 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
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49

    结语

    感谢大家一直以来的不断支持与鼓励，码题集题库中的新手村600题现已全部完结，之后会逐步跟进黄金，钻石，星耀，王者的题，尽请期待！！！
    同时，也希望这些题能帮助到大家，一起进步，祝愿每一个算法道路上的“苦行僧”们，都能够历经磨难，终成正果，既然选择了这条路，走到了这里，中途放弃，岂不是太过可惜？

    另附中国计算机学会的杰出会员、常务理事轩哥博士的B站视频讲解链接https://space.bilibili.com/518554541/?spm_id_from=333.999.0.0，供大家更好的进行学习与刷题～(￣▽￣～)~

    愿你的结局，配得上你一路的颠沛流离。

  • 相关阅读:
    全球与中国亚麻籽行业消费量调研及未来产销需求分析报告2022-2028年
    子集和数问题
    c++之旅第七弹——继承
    数据结构与算法系列-二分查找
    【Unity】简单的深度虚化shader
    QT之UDP通信
    跨平台代码编写规范——参考《Loup&卡普》的文档
    架构师成长之路也该了解的新一代微服务技术-ServiceMesh（上）
    java中okhttp和httpclient那个效率高
    记录生产中遇到的两个sql优化场景
  • 原文地址：https://blog.csdn.net/m0_54754302/article/details/127756305