title: 2019中南大学研究生招生夏令营机试题
date: 2020-04-17 17:34:23
categories: 算法
tags: [C++, 马拉车, 最短路, dfs]
mathjax: true
| 题目编号 | 标题 | 来源/分类 | 正确 | 提交 | |
|---|---|---|---|---|---|
| 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
来源/分类
解析：
注意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
来源/分类
解析
最长路
#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
来源/分类
解析
#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
来源/分类
#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位的十六进制数，请转换成八进制数。
注：十六进制数中，字母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
来源/分类
#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
****************************************************************/
