title: 2019中南大學(xué)研究生招生夏令營(yíng)機(jī)試題
date: 2020-04-17 17:34:23
categories: 算法
tags: [C++, 馬拉車, 最短路, dfs]
mathjax: true
2019中南大學(xué)研究生招生夏令營(yíng)機(jī)試題
| 題目編號(hào) | 標(biāo)題 | 來(lái)源/分類 | 正確 | 提交 | |
|---|---|---|---|---|---|
| Y | 1110 | 地磚問(wèn)題 | 2019中南大學(xué)研究生招生夏令營(yíng)機(jī)試題 | 306 | 932 |
| Y | 1111 | 最小花費(fèi) | 2019中南大學(xué)研究生招生夏令營(yíng)機(jī)試題 | 105 | 454 |
| Y | 1112 | 回文串 | 2019中南大學(xué)研究生招生夏令營(yíng)機(jī)試題 | 161 | 435 |
| Y | 1113 | 有序合并 | 2019中南大學(xué)研究生招生夏令營(yíng)機(jī)試題 | 156 | 435 |
| Y | 1114 | 十六進(jìn)制轉(zhuǎn)換 | 2019中南大學(xué)研究生招生夏令營(yíng)機(jī)試題 | 237 | 661 |
1110: 地磚問(wèn)題
時(shí)間限制: 1 Sec 內(nèi)存限制: 128 MB
提交: 932 解決: 306
[提交] [狀態(tài)] [討論版] [命題人:test]
題目描述
小明站在一個(gè)矩形房間里搪哪，這個(gè)房間的地面鋪滿了地磚颜阐，每塊地磚的顏色或是紅色或是黑色。小明一開(kāi)始站在一塊黑色的地磚上庄呈，并且小明從一塊地磚可以向上下左右四個(gè)方向移動(dòng)到其他的地磚上陷嘴，但是他不能移動(dòng)到紅色地磚上，只能移動(dòng)到黑色地磚上。
請(qǐng)你編程計(jì)算小明可以走到的黑色地磚最多有多少塊肚菠。
輸入
輸入包含多組測(cè)試數(shù)據(jù)。
每組輸入首先是兩個(gè)正整數(shù)W和H罩缴，分別表示地磚的列行數(shù)蚊逢。（1<=W，H<=25）
接下來(lái)H行箫章，每行包含W個(gè)字符烙荷，字符含義如下：
‘.’表示黑地磚；
‘#’表示紅地磚檬寂；
‘@’表示小明一開(kāi)始站的位置终抽，此位置是一塊黑地磚，并且這個(gè)字符在每組輸入中僅會(huì)出現(xiàn)一個(gè)桶至。
當(dāng)W=0昼伴，H=0時(shí)，輸入結(jié)束镣屹。
輸出
對(duì)于每組輸入圃郊，輸出小明可以走到的黑色地磚最多有多少塊，包括小明最開(kāi)始站的那塊黑色地磚女蜈。
樣例輸入
7 7
..#.#..
..#.#..
###.###
...@...
###.###
..#.#..
..#.#..
0 0
樣例輸出
13
來(lái)源/分類
2019中南大學(xué)研究生招生夏令營(yíng)機(jī)試題
解析：
注意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: 最小花費(fèi)
時(shí)間限制: 1 Sec 內(nèi)存限制: 128 MB
提交: 454 解決: 105
[提交] [狀態(tài)] [討論版] [命題人:test]
題目描述
在n個(gè)人中色瘩，某些人的銀行賬號(hào)之間可以互相轉(zhuǎn)賬。這些人之間轉(zhuǎn)賬的手續(xù)費(fèi)各不相同逸寓。給定這些人之間轉(zhuǎn)賬時(shí)需要從轉(zhuǎn)賬金額里扣除百分之幾的手續(xù)費(fèi)居兆，請(qǐng)問(wèn)A最少需要多少錢使得轉(zhuǎn)賬后B收到100元。
輸入
輸入包含多組測(cè)試用例竹伸。
對(duì)于每組樣例泥栖，第一行輸入兩個(gè)正整數(shù)n,m,分別表示總?cè)藬?shù)和可以互相轉(zhuǎn)賬的人的對(duì)數(shù)。（0<n<=2000）以下m行每行輸入三個(gè)正整數(shù)x,y,z勋篓。表示標(biāo)號(hào)為x的人和標(biāo)號(hào)為y的人之間互相轉(zhuǎn)賬需要扣除z%的手續(xù)費(fèi)（z<100）聊倔。
最后一行輸入兩個(gè)正整數(shù)A,B。數(shù)據(jù)保證A與B之間可以直接或間接地轉(zhuǎn)賬
輸出
輸出A使得B到賬100元最少需要的總費(fèi)用生巡。精確到小數(shù)點(diǎn)后8位耙蔑。
樣例輸入
3 3
1 2 1
2 3 2
1 3 3
1 3
樣例輸出
103.07153164
來(lái)源/分類
2019中南大學(xué)研究生招生夏令營(yíng)機(jī)試題
解析
最長(zhǎng)路
#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: 回文串
時(shí)間限制: 1 Sec 內(nèi)存限制: 128 MB
提交: 435 解決: 161
[提交] [狀態(tài)] [討論版] [命題人:test]
題目描述
現(xiàn)在給你一個(gè)字符串S，請(qǐng)你計(jì)算S中有多少連續(xù)子串是回文串孤荣。
輸入
輸入包含多組測(cè)試數(shù)據(jù)甸陌。每組輸入是一個(gè)非空字符串，長(zhǎng)度不超過(guò)5000.
輸出
對(duì)于每組輸入盐股，輸出回文子串的個(gè)數(shù)钱豁。
樣例輸入
aba
樣例輸出
4
來(lái)源/分類
2019中南大學(xué)研究生招生夏令營(yíng)機(jī)試題
解析
#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: 有序合并
時(shí)間限制: 1 Sec 內(nèi)存限制: 128 MB
提交: 435 解決: 156
[提交] [狀態(tài)] [討論版] [命題人:test]
題目描述
已知線性表LA和LB中的數(shù)據(jù)元素按值非遞減有序排列，現(xiàn)要求LA和LB歸并為一個(gè)新的線性表LC疯汁，且LC中的數(shù)據(jù)元素仍然按值非遞減有序排列牲尺。例如，設(shè)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）谤碳。
輸入
有多組測(cè)試數(shù)據(jù)，每組測(cè)試數(shù)據(jù)占兩行溢豆。第一行是集合A蜒简，第一個(gè)整數(shù)m（0<=m<=100）代表集合A起始有m個(gè)元素，后面有m個(gè)非遞減排序的整數(shù)漩仙，代表A中的元素搓茬。第二行是集合B，第一個(gè)整數(shù)n（0<=n<=100）代表集合B起始有n個(gè)元素队他，后面有n個(gè)非遞減排序的整數(shù)卷仑，代表B中的元素。每行中整數(shù)之間用一個(gè)空格隔開(kāi)麸折。
輸出
每組測(cè)試數(shù)據(jù)只要求輸出一行锡凝，這一行含有m+n個(gè)來(lái)自集合A和集合B中的元素。結(jié)果依舊是非遞減的磕谅。每個(gè)整數(shù)間用一個(gè)空格隔開(kāi)私爷。
樣例輸入
4 3 5 8 11
7 2 6 8 9 11 15 20
樣例輸出
2 3 5 6 8 8 9 11 11 15 20
來(lái)源/分類
2019中南大學(xué)研究生招生夏令營(yíng)機(jī)試題
#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: 十六進(jìn)制轉(zhuǎn)換
時(shí)間限制: 1 Sec 內(nèi)存限制: 128 MB
提交: 661 解決: 237
[提交] [狀態(tài)] [討論版] [命題人:test]
題目描述
輸入一個(gè)不超過(guò)100000位的十六進(jìn)制數(shù)，請(qǐng)轉(zhuǎn)換成八進(jìn)制數(shù)膊夹。
注：十六進(jìn)制數(shù)中衬浑，字母09還對(duì)應(yīng)表示數(shù)字09。字母”A”（大寫）表示10放刨，”B”表示11工秩，”...”，”F”表示15进统，比如：十六進(jìn)制數(shù)A10B表示的是10進(jìn)制數(shù)是10×163+1×162+0×161+11×160=41227助币。轉(zhuǎn)換成的八進(jìn)制數(shù)是120413，因?yàn)?×85+2×84+0×83+4×82+1×81+3×80=41227螟碎。
輸入
一個(gè)十六進(jìn)制數(shù)眉菱，沒(méi)有前導(dǎo)0（除非是數(shù)字0）。
輸出
一個(gè)八進(jìn)制數(shù)掉分，沒(méi)有前導(dǎo)0（除非是數(shù)字0）俭缓。
樣例輸入
123ABC
樣例輸出
4435274
來(lái)源/分類
2019中南大學(xué)研究生招生夏令營(yíng)機(jī)試題
#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
****************************************************************/
