本文主要是介绍2019中南大学研究生招生夏令营机试题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
title: 2019中南大学研究生招生夏令营机试题
date: 2020-04-17 17:34:23
categories: 算法
tags: [C++, 马拉车, 最短路, dfs]
mathjax: true
2019中南大学研究生招生夏令营机试题
| 题目编号 | 标题 | 来源/分类 | 正确 | 提交 | |
|---|---|---|---|---|---|
| Y | 1110 | 地砖问题 | 2019中南大学研究生招生夏令营机试题 | 306 | 932 |
| Y | 1111 | 最小花费 | 2019中南大学研究生招生夏令营机试题 | 105 | 454 |
| Y | 1112 | 回文串 | 2019中南大学研究生招生夏令营机试题 | 161 | 435 |
| Y | 1113 | 有序合并 | 2019中南大学研究生招生夏令营机试题 | 156 | 435 |
| Y | 1114 | 十六进制转换 | 2019中南大学研究生招生夏令营机试题 | 237 | 661 |
1110: 地砖问题
时间限制: 1 Sec 内存限制: 128 MB
提交: 932 解决: 306
[提交] [状态] [讨论版] [命题人:test]
题目描述
小明站在一个矩形房间里，这个房间的地面铺满了地砖，每块地砖的颜色或是红色或是黑色。小明一开始站在一块黑色的地砖上，并且小明从一块地砖可以向上下左右四个方向移动到其他的地砖上，但是他不能移动到红色地砖上，只能移动到黑色地砖上。
请你编程计算小明可以走到的黑色地砖最多有多少块。
输入
输入包含多组测试数据。
每组输入首先是两个正整数W和H，分别表示地砖的列行数。（1<=W，H<=25）
接下来H行，每行包含W个字符，字符含义如下：
‘.’表示黑地砖；
‘#’表示红地砖；
‘@’表示小明一开始站的位置，此位置是一块黑地砖，并且这个字符在每组输入中仅会出现一个。
当W=0，H=0时，输入结束。
输出
对于每组输入，输出小明可以走到的黑色地砖最多有多少块，包括小明最开始站的那块黑色地砖。
样例输入
7 7
..#.#..
..#.#..
###.###
...@...
###.###
..#.#..
..#.#..
0 0
样例输出
13
来源/分类
2019中南大学研究生招生夏令营机试题
解析：
注意n,m，dfs即可
#include<iostream>
using namespace std;
int n,m;
char mp[105][105];
int ans=0;
int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};
int vis[105][105];
void dfs(int sx,int sy)
{for(int i=0;i<4;i++){int x=sx+dx[i];int y=sy+dy[i];if(x<=n && x>=1 &&y<=m&&y>=1 &&mp[x][y]!='#'&&vis[x][y]==0){ans+=1;vis[x][y]=1;dfs(x,y);}}
}
int main()
{while(~scanf("%d%d",&m,&n)){ans=0;if(n==0||m==0)break;int sx,sy;for(int i=1;i<=n;i++){scanf("%s",mp[i]+1);for(int j=1;j<=m;j++){vis[i][j]=0;if(mp[i][j]=='@'){sx=i;sy=j;}}}vis[sx][sy]=1;dfs(sx,sy);printf("%d\n",ans+1);}
}
/**************************************************************Problem: 1110User: pxlsdzLanguage: C++Result: 正确Time:0 msMemory:1760 kb
****************************************************************/
1111: 最小花费
时间限制: 1 Sec 内存限制: 128 MB
提交: 454 解决: 105
[提交] [状态] [讨论版] [命题人:test]
题目描述
在n个人中，某些人的银行账号之间可以互相转账。这些人之间转账的手续费各不相同。给定这些人之间转账时需要从转账金额里扣除百分之几的手续费，请问A最少需要多少钱使得转账后B收到100元。
输入
输入包含多组测试用例。
对于每组样例，第一行输入两个正整数n,m,分别表示总人数和可以互相转账的人的对数。（0<n<=2000）以下m行每行输入三个正整数x,y,z。表示标号为x的人和标号为y的人之间互相转账需要扣除z%的手续费（z<100）。
最后一行输入两个正整数A,B。数据保证A与B之间可以直接或间接地转账
输出
输出A使得B到账100元最少需要的总费用。精确到小数点后8位。
样例输入
3 3
1 2 1
2 3 2
1 3 3
1 3
样例输出
103.07153164
来源/分类
2019中南大学研究生招生夏令营机试题
解析
最长路
#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
#include<queue>
using namespace std;
int n,m;
const int N=20005;
#define LL long long
typedef pair<double,int> PLI;
int head[N],ne[N],e[N],idx;
double w[N],dis[N];
bool st[N];
void init()
{idx=0;for(int i=0;i<=n;i++){head[i]=-1;}
}
void add(int a,int b,double c)
{e[idx]=b;w[idx]=c;ne[idx]=head[a];head[a]=idx++;
}
priority_queue<PLI>heap;
double dij(int s,int en)
{for(int i=0;i<=n;i++)dis[i]=-1e18,st[i]=false;dis[s]=1;heap.push({1,s});while(heap.size()){//cout<<heap.size()<<endl;PLI t=heap.top();heap.pop();double dist=t.first;int y=t.second;if(st[y]==true) continue;st[y]=true;for(int i=head[y];i!=-1;i=ne[i]){int j=e[i];if(dis[j]<dist*w[i]){dis[j]=dist*w[i];heap.push({dis[j],j});}}}return dis[en];}int main()
{while(~scanf("%d%d",&n,&m)){init();int a,b;double c;for(int i=1;i<=m;i++){scanf("%d%d%lf",&a,&b,&c);c=(100-c)/100.0;//cout<<c<<endl;add(a,b,c);add(b,a,c);}int s,e;scanf("%d%d",&s,&e);double d=dij(s,e);//cout<<d<<endl;printf("%.8f\n",100.0/(d));}return 0;}/**************************************************************Problem: 1111User: pxlsdzLanguage: C++Result: 正确Time:16 msMemory:2280 kb
****************************************************************/
1112: 回文串
时间限制: 1 Sec 内存限制: 128 MB
提交: 435 解决: 161
[提交] [状态] [讨论版] [命题人:test]
题目描述
现在给你一个字符串S，请你计算S中有多少连续子串是回文串。
输入
输入包含多组测试数据。每组输入是一个非空字符串，长度不超过5000.
输出
对于每组输入，输出回文子串的个数。
样例输入
aba
样例输出
4
来源/分类
2019中南大学研究生招生夏令营机试题
解析
#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
#include<queue>
using namespace std;
int n,m;
const int N=50005;
char s[N],temp[2*N];
int Len[N];
void init()
{int len=strlen(s);temp[0]='@';for(int i=1;i<=2*len;i+=2){temp[i]='#';temp[i+1]=s[i/2];}temp[2*len+1]='#';temp[2*len+2]='\0';
}
int mancher()
{int len=strlen(temp);int po=0,mx=0;int num=0;for(int i=1;i<len;i++){if(mx>i)Len[i]=min(mx-i,Len[2*po-i]);elseLen[i]=1;while(temp[i+Len[i]]==temp[i-Len[i]])Len[i]+=1;if(Len[i]+i>mx){mx=Len[i]+i;po=i;}num+=Len[i]/2;}return num;
}
int main()
{while(~scanf("%s",s)){init();//cout<<temp<<endl;printf("%d\n",mancher());}return 0;}/**************************************************************Problem: 1112User: pxlsdzLanguage: C++Result: 正确Time:0 msMemory:2048 kb
****************************************************************/
1113: 有序合并
时间限制: 1 Sec 内存限制: 128 MB
提交: 435 解决: 156
[提交] [状态] [讨论版] [命题人:test]
题目描述
已知线性表LA和LB中的数据元素按值非递减有序排列，现要求LA和LB归并为一个新的线性表LC，且LC中的数据元素仍然按值非递减有序排列。例如，设LA=（3,5,8,11），LB=（2,6,8,9,11,15,20）则LC=（2,3,6,6,8,8,9,11,11,15,20）。
输入
有多组测试数据，每组测试数据占两行。第一行是集合A，第一个整数m（0<=m<=100）代表集合A起始有m个元素，后面有m个非递减排序的整数，代表A中的元素。第二行是集合B，第一个整数n（0<=n<=100）代表集合B起始有n个元素，后面有n个非递减排序的整数，代表B中的元素。每行中整数之间用一个空格隔开。
输出
每组测试数据只要求输出一行，这一行含有m+n个来自集合A和集合B中的元素。结果依旧是非递减的。每个整数间用一个空格隔开。
样例输入
4 3 5 8 11
7 2 6 8 9 11 15 20
样例输出
2 3 5 6 8 8 9 11 11 15 20
来源/分类
2019中南大学研究生招生夏令营机试题
#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
#include<queue>
using namespace std;
typedef long long LL;
int n,m;
int a[100005];
int ans[100005];
int main()
{while(~scanf("%d",&n)){for(int i=1; i<=n; i++){scanf("%d",&a[i]);}scanf("%d",&m);int x,j=1;int cnt=0;for(int i=1; i<=m; i++){scanf("%d",&x);while(j<=n&&a[j]<=x){ans[cnt++]=a[j];//printf("%d ",a[j]);j+=1;}ans[cnt++]=x;//printf("%d ",x);}while(j<=n){ans[cnt++]=a[j];//printf("%d ",a[j]);j+=1;}for(int i=0; i<cnt; i++){printf("%d ",ans[i]);}cout<<endl;}return 0;}/**************************************************************Problem: 1113User: pxlsdzLanguage: C++Result: 正确Time:0 msMemory:2488 kb
****************************************************************/
1114: 十六进制转换
时间限制: 1 Sec 内存限制: 128 MB
提交: 661 解决: 237
[提交] [状态] [讨论版] [命题人:test]
题目描述
输入一个不超过100000位的十六进制数，请转换成八进制数。
注：十六进制数中，字母09还对应表示数字09。字母”A”（大写）表示10，”B”表示11，”…”，”F”表示15，比如：十六进制数A10B表示的是10进制数是10×163+1×162+0×161+11×160=41227。转换成的八进制数是120413，因为1×85+2×84+0×83+4×82+1×81+3×80=41227。
输入
一个十六进制数，没有前导0（除非是数字0）。
输出
一个八进制数，没有前导0（除非是数字0）。
样例输入
123ABC
样例输出
4435274
来源/分类
2019中南大学研究生招生夏令营机试题
#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
#include<queue>
using namespace std;
typedef long long LL;
int n,m;
char s[100005];
int ans[4*100005];
int main()
{while(~scanf("%s",s)){int len=strlen(s);if(s[0]=='0'){cout<<0<<endl;continue;}int cnt=0;for(int i=len-1; i>=0; i--){int x;if(s[i]<='9'&&s[i]>='0')x=s[i]-'0';elsex=s[i]-'A'+10;int temp[]={0,0,0,0};int num=0;while(x){temp[num++]=x%2;x/=2;} for(int j=0;j<4;j++){ans[cnt++]=temp[j];//cout<<ans[cnt-1]<<" ";}//cout<<endl;}while(cnt%3){ans[cnt++]=0;}int b[]={1,2,4,8};int flag=1;for(int i=cnt-1;i>=0;i-=3){//cout<<ans[i]<<" "<<ans[i-1]<<" "<<ans[i-2]<<endl;int t=ans[i]*b[2]+ans[i-1]*b[1]+ans[i-2]*b[0];if(t!=0 || flag==0){ flag=0;printf("%d",t);}}cout<<endl;}return 0;}/**************************************************************Problem: 1114User: pxlsdzLanguage: C++Result: 正确Time:8 msMemory:3372 kb
****************************************************************/
这篇关于2019中南大学研究生招生夏令营机试题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
![BUUCTF靶场[web][极客大挑战 2019]Http、[HCTF 2018]admin](https://i-blog.csdnimg.cn/direct/ed45c0efd0ac40c68b2c1bc7b6d90ebc.png)
![最简单的使用JDBC[连接数据库] mysql 2019年3月18日](https://i-blog.csdnimg.cn/blog_migrate/d10b0c37d5115bce2197b87d8034b833.png)
