2021中南大学研讨生招生夏令营机试题-简书(2021中南大学附属中学高中录取线)
title: 2021中南大学研讨生招生夏令营机试题
date: 2021-04-17 17:34:23
categories: 算法
tags: [c++, 马拉车, 最短路, dfs]
mathjax: true
2021中南大学研讨生招生夏令营机试题
标题编号
标题
来历/分类
正确
提交
y
1110
地砖疑问
2021中南大学研讨生招生夏令营机试题
306
932
y
1111
最小花费
2021中南大学研讨生招生夏令营机试题
105
454
y
1112
回文串
2021中南大学研讨生招生夏令营机试题
161
435
y
1113
有序兼并
2021中南大学研讨生招生夏令营机试题
156
435
y
1114
十六进制变换
2021中南大学研讨生招生夏令营机试题
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
来历/分类
2021中南大学研讨生招生夏令营机试题
解析：
留心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: 1110
user: pxlsdz
language: c++
result: 正确
time:0 ms
memory: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
来历/分类
2021中南大学研讨生招生夏令营机试题
解析
最长路
#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: 1111
user: pxlsdz
language: c++
result: 正确
time:16 ms
memory:2280 kb
****************************************************************/
1112: 回文串
时刻捆绑: 1 sec 内存捆绑: 128 mb
提交: 435 处置: 161
[提交] [状况] [谈论版] [出题人:test]
标题描绘
如今给你一个字符串s，请你核算s中有多少接连子串是回文串。
输入
输入包括多组查验数据。每组输入是一个非空字符串，长度不跨越5000.
输出
关于每组输入，输出回文子串的个数。
样例输入
aba
样例输出
4
来历/分类
2021中南大学研讨生招生夏令营机试题
解析
#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]);
else
len[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: 1112
user: pxlsdz
language: c++
result: 正确
time:0 ms
memory: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
来历/分类
2021中南大学研讨生招生夏令营机试题
#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: 1113
user: pxlsdz
language: c++
result: 正确
time:0 ms
memory:2488 kb
****************************************************************/
1114: 十六进制变换
时刻捆绑: 1 sec 内存捆绑: 128 mb
提交: 661 处置: 237
[提交] [状况] [谈论版] [出题人:test]
标题描绘
输入一个不跨越100000位的十六进制数，请变换成8进制数。
注：十六进制数中，字母09还对应标明数字09。字母”a”（大写）标明10，”b”标明11，”…”，”f”标明15，比方：十六进制数a10b标明的是10进制数是10×163+1×162+0×161+11×160=41227。变换成的8进制数是120413，因为1×85+2×84+0×83+4×82+1×81+3×80=41227。
输入
一个十六进制数，没有前导0（除非是数字0）。
输出
一个8进制数，没有前导0（除非是数字0）。
样例输入
123abc
样例输出
4435274
来历/分类
2021中南大学研讨生招生夏令营机试题
#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';
else
x=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: 1114
user: pxlsdz
language: c++
result: 正确
time:8 ms
memory:3372 kb
******************************
**********************************/
评论