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

    算法竞赛入门【码蹄集进阶塔335题】MT2311-2315

    文章目录

    前言

    在这里插入图片描述

    为什么突然想学算法了？

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

    在这里插入图片描述

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

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

    目录

    1. MT2311 还是跑图

    （1）题目描述
    给出一张有向图，你需要返回图中出边最多的节点，如果有多个出边最多的节点，输出编号最小的。

    格式

    输入格式:
    第一行n, m，表示有n个节点,m条边，
    第二行开始m行，
    每行有三个数ayz ,表示有一条从c到y的边,长度为z。
    .
    输出格式:
    输出1行，为出边最多的节点，
    接下来若干行，每行输出该节点的边的去向节点和边长，按去向节点编号从小到大输出，如有重边按边长从小到大输出。

    样例1

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

    备注：

    1≤n ≤1000,1 ≤m ≤100000 ,1≤x, y ≤n, x ≠ y ，1

    （2）参考代码

    #include 
 
// 内部转换与空间顺序
using namespace std;
 
const int M = 1e5+1;
 
struct point{
	int x;
    int y;
    int z;
    int sum=0;
}p[M]; 
 
struct res{
	int start;
	int end;
}r[M];
 
bool com2(point p1, point p2){
    return p1.x < p2.x;
}
 
bool com3(res r1, res r2) {
	return r1.start < r2.start;
}
 
int main()
{
    int n, m;
    cin >> n >> m;
    int index;
    for(int i=0;i<m;i++){
        cin >> p[i].x >> p[i].y >>p[i].z;
        index = p[i].x;
        p[index].sum++;
    }
 
	int max = 0;
	int ans = 0;
	
	for(int i=0;i<m;i++){
		if(p[i].sum > max){
			max = p[i].sum;
			ans = i;
		}
	}
	
	sort(p,p+m, com2);
	int j=0;
	for(int i=0;i<m;i++){
		if(p[i].x == ans){
			r[j].start = p[i].y;
			r[j].end = p[i].z;
			j++;
		}
	}
	
	sort(r, r+j,com3);
	
	for(int i=1;i<j;i++){
		if(r[i-1].start==r[i].start && r[i-1].end > r[i].end) {
			int temp = r[i].end;
			r[i].end = r[i-1].end;
			r[i-1].end = temp;
		}
	}
	
	//	出边最多的节点 
	cout << ans << endl;
	
	for(int i=0;i<j;i++){
		cout << r[i].start << " " << r[i].end << 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
    • 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
    • 76
    • 77

    2. MT2312 文件管理

    （1）题目描述
    题目中，会给出一个目录下的所有文件和文件夹。同目录下可能会有同名文件或文件夹。

    最后，会查询一个文件名，你需要给出文件目录。如果有多个查询结果，则每个结果输出一行，若查找不到，则输出NULL

    格式

    输入格式:
    本题不对文件或文件夹进行具体区分每行包含数个空格和一个小写字母字符串文件隶属于其上方最近的空格数-1的文件夹，例如:
    在这里插入图片描述
    1，5直接位于根目录下，2，4在文件夹1中，3在文件夹2中最后以一行”#\n”结束
    再查询一个文件名

    .
    输出格式: 每行输出一个查询到的文件的目录，按在input中文件出现顺序输出
    详细格式见样例

    样例1

    输入格式:
    aabb
    cpp
    md
    md
    abcd
    cpp
    md
    .#
    md
    .
    输出格式:
    /aabb/md
    /aabb/md/md
    /abcd/md

    备注：

    4<总文件(文件夹)数<1000
    2≤文件(文件夹)名长度≤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. MT2313 过年访亲

    （1）题目描述
    小码哥的家乡有n个家庭(1≤n ≤8 )，过年期间他要到每一家去访亲，每个家庭之间的路程s(0

    格式

    输入格式:
    家庭数n和各家庭之间的路程(均是整数)
    .
    输出格式: 最短的路程

    样例1

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

    （2）参考代码

    #include 
using namespace std;
const int N=20,M=1<<N;
int n;
int w[N][N];
int f[M][N];
signed main()
{
    cin>>n;
   // memset (w,0x3f,sizeof w);
    for (int i=0;i<n;i++)
        for (int j=0;j<n;j++)
            cin>>w[i][j];
    memset(f,0x3f,sizeof f);
    //从第0个点走到第0个点的代价为0
    f[1][0]=0;
    
    //枚举所有的状态
    for (int i=1;i<1<<n;i+=2)
    //枚举所有点
        for (int j=0;j<n;j++)
        //如果说走到了第j个点
            if (i>>j&1)
            //判断上一个点
                for (int k=0;k<n;k++)
                {
                        if ((i-(1<<j))>>k&1)
                //说明去除掉第j个点之后是走到过第k个点的
                        f[i][j]=min(f[i][j],f[i-(1<<j)][k]+w[k][j]);
                }
    //所有点都走过了并且走到第n-1个点
    int ans=5888888;
    for (int i=0;i<=n-1;i++)
    {
        ans=min(ans,f[(1<<n)-1][i]+w[i][0]);
    }
    cout<<ans<<"\n";
    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

    4. MT2314 八竿子打不着

    （1）题目描述
    小码哥正在整理NPU的学生信息。现在到了关键的一步:存储cp信息。

    因为众所周知情网很乱，所以可能一个人和多个人暧昧，并且不分性别。同时—对暧昧关系可能会由于大意等原因多次记录。

    现在我们知道n个人，并且有m个暧昧关系。

    现在我们对暧昧团进行定义:一个人所有和他有直接暧昧关系以及间接暧昧关系的集合。比如1与2暧昧，2与3暧昧，3与4暧昧，5与3暧昧，6与2暧昧，那么{1,2,3,4,5,6},{2,3},{1,4,5,6},{空集合}就均属于暧昧团，其中，{1,2,3,4,5,6}就是极大暧昧团

    现在小码哥告诉你一个人名的编号x，让你回答与x所处极大暧昧团中与x最“八竿子打不着”的权值。我们定义:最“八竿子打不着”的权值表示在这个极大暧昧团中，距离x关系最远的那个人的距离。比如刚才举得例子中，1的最“八竿子打不着”的权值就是3。

    注意本题中，保证不存在自己和自己暖昧。

    格式

    输入格式:
    第一行一个整数n,m( 1 ≤n, m ≤ 1e5 )，表示人数，和暧昧关系的数量。
    接下来m行，每行两个整数a,b( 1 ≤a, b ≤n )，表示a,b之间存在暧昧关系。
    最后一行一个整数x，表示询问x所处极大暧昧团中与x最“八竿子打不着”的权值。
    .
    输出格式: 一行一个整数表示答案

    样例1：

    输入：
    6 8
    1 2
    5 2
    3 6
    4 5
    1 4
    2 1
    3 6
    3 6
    3
    输出：1

    （2）参考代码

    #include
#include
#include
#define maxn 100005
using namespace std;
int n,m,s,ans;
int tot,lnk[maxn],son[maxn<<1],net[maxn<<1];
bool vis[maxn];
int que[maxn],dis[maxn];
inline int read(){
    int ret=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
    while (ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar();
    return ret*f;
}
inline void add(int x,int y){net[++tot]=lnk[x];son[tot]=y;lnk[x]=tot;}
void BFS(){
    int hed=0,tal=1;
    que[1]=s;vis[s]=1;
    memset(dis,63,sizeof(dis));dis[s]=0;
    while (hed!=tal){
        hed++;
        int x=que[hed];
        for (int j=lnk[x];j;j=net[j])
        if (!vis[son[j]]){
            dis[son[j]]=dis[x]+1;
            ans=max(ans,dis[son[j]]);
            que[++tal]=son[j];vis[son[j]]=1;
        }
    }
}
int main(){
    n=read();m=read();
    for (int i=1;i<=m;i++){
        int x=read(),y=read();
        add(x,y);add(y,x);
    }
    s=read();
    BFS();
    printf("%d\n",ans);
    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

    5. MT2315 欧拉回路

    （1）题目描述
    如果图G中的一个路径包括每个边恰好一次，则该路径称为欧拉路径(Eulrepath)。如果一个回路是欧拉路径，则称为欧拉回路(Eulercircuit)。

    输入一个有向图，请你判断这个有向图上是否存在欧拉回路。

    格式

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

    样例1

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

    样例2

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

    备注：

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

    （2）参考代码

    #include 

using namespace std;
const int MAX_N = 100000;
const int MAX_M = 10000000;
int res=0;
struct edge
{
int v, next;
int len;
} E[MAX_M];
int p[MAX_N], eid;
void init()
{
memset(p, -1, sizeof(p));
eid = 0;
}
void insert(int u, int v)
{
E[eid].v = v;
E[eid].next = p[u];
p[u] = eid++;
}
int n, m;
int degree[MAX_N];
int cnt;
bool vis[MAX_N];
void dfs(int u)
{
vis[u] = true;
cnt++;
for (int i = p[u]; i != -1; i = E[i].next)
{
int v = E[i].v;
if (!vis[v])
{
dfs(v);
}
}
}
int euler()
{
dfs(1);
if (cnt != n)
{
return res;
}
int cntodd = 0;
for (int i = 1; i <= n; i++)
{
if (degree[i] % 2 == 1)
{
cntodd++;
}
}
if (cntodd == 0)
{
++res;
}

return res;
}
int main()
{
init();
memset(degree, 0, sizeof(degree));
cin >> n >> m;
for (int i = 0; i < m; i++)
{
int u, v;
cin >> u >> v;
insert(u, v);
insert(v, u);
degree[u]++;
degree[v]++;
}
if(1==euler()){
cout<<"Yes";
}
else{
cout<<"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
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84

    结语

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

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

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

  • 相关阅读:
    设计模式最佳实践代码总结 - 结构型设计模式篇 - 代理模式最佳实践
    asp.net core在其他程序集获取HttpContext
    99-104-Hadoop-MapReduce-排序：
    DRM系列(8)之prepare_signaling
    springboot整合mybatis & druid
    CSS鼠标指针表
    基于SpringBoot的OCR识别服务端方案
    软件设计师考试重点1 计算机组成与体系结构
    SpringBoot集成支付宝 - 少走弯路就看这篇
    [网络工程师]-防火墙-防火墙技术
  • 原文地址：https://blog.csdn.net/m0_54754302/article/details/128078641