往年5级考题（c++）
考级在即，这篇文章就来看看往年的c++5级考试真题
逃离迷宫
题目描述
你在一个地下迷宫中找到了宝藏，但是也触发了迷宫机关，导致迷宫将在T分钟后坍塌，为此你需要在T分钟内逃离迷宫，你想知道你能不能逃离迷宫。
迷宫是一个边长为m的正方形，其中"S"表示你所在的位置，"E"表示迷宫出口，"."是可以随意走动的区域，"#"是不可穿行的墙壁，每次你可以耗费1分钟在区域间移动（上下左右四个方向）。
输入格式
输入包含多组数组，第一行是一个整数K（1 <= K <= 10)，表示有K组数据。
接下来每组数组包含整数m(2<=m<=10)和整数T，m表示正方形迷宫的边长，T表示坍塌时间。
其后是一个m*m的字符矩阵，包含字符"S", "E", "."和"#"。
输出格式
每组数据输出一行，输出“YES"或者"NO"，表示是否可以在坍塌之前逃离（也就是说移动次数是否可以不超过T）。
样例
样例输入
2
4 7
S...
###.
.#E.
..#.
3 4
S..
..#
.#E
样例输出
YES
NO
#include <bits/stdc++.h>
using namespace std;
struct node
{
int x,y,v;
node(){};
node(int a,int b,int c)
{
x = a;
y = b;
v = c;
}
};
node que[300];
int dx[4] = {0,1,0,-1};
int dy[4] = {1,0,-1,0};
int xx,yy;
int m;
char a[15][15] = {'\0'};
int head;
int tail;
int main()
{
int k;
cin>>k;
for(int iii = 0;iii<k;iii++)
{
int t;
cin>>m>>t;
int xxx,yyy;
for(int i = 1;i<=m;i++)
{
for(int j = 1;j<=m;j++)
{
cin>>a[i][j];
if(a[i][j]=='S')
{
xxx = i;
yyy = j;
}
else if(a[i][j]=='E')
{
xx = i;
yy = j;
}
}
}
que[++tail] = {xxx,yyy,0};
bool f = false;
while(head<tail)
{
head++;
for(int i = 0;i<4;i++)
{
int tx = que[head].x+dx[i];
int ty = que[head].y+dy[i];
if(tx>=1&&tx<=m&&ty>=1&&ty<=m&&a[tx][ty]!='#')
{
a[tx][ty] = '#';
que[++tail] = {tx,ty,que[head].v+1};
if(tx==xx&&ty==yy)
{
if(que[tail].v<=t)
{
f = true;
cout<<"YES"<<endl;
}
break;
}
}
}
if(f==true) break;
}
if(f==false) cout<<"NO"<<endl;
}
return 0;
}密室逃脱
题目描述
有一个密室逃脱游戏，有100间密室连在一排。密室编号是从1开始连续排列一直排到第100间密室，如下图:游戏规则:1.玩家初始位置在1号密室; ⒉每次玩家可以进入右边的一个密室，也可以跳过一个密室进入下个密室(如:当玩家当前在3号密室，他可以进入4号密室也可以进入5号密室);3.有毒气的密室不能进入需要避开。 给定三个正整数X，Y，M (1<X<Y<M≤100)，表示三个密室编号。X号密室和Y号密室有毒气泄漏，不能进入，玩家需要进入到M号密室 按照 游戏规则进入M号密室有多少种路线方案。例如: X=2，Y=4，M=7，2号和4号有毒气泄露，避开2号和4号毒气密室，进入7号密室有2种路线方案，分别是1->3->5->6->7路线和1->3->5->7路线。
输入格式
输入三个正整数X，Y，M(1<X<Y≤M)，并以英文逗号隔开
输出格式
输出从1号密室开始避开X、Y号毒气密室，进入M号密室有多少种路线方案
样例
样例输入
2,4,7
样例输出
2
#include <bits/stdc++.h>
using namespace std;
int a[110] = {0};
int cnt = 0;
int m;
void aaa(int);
int main()
{
int x,y;
char aaaa,bbbb;
cin>>x>>aaaa>>y>>bbbb>>m;
a[x] = 1;
a[y] = 1;
aaa(1);
cout<<cnt;
return 0;
}
void aaa(int n)
{
if(n==m)
{
cnt++;
return;
}
else if(n>m)
{
return;
}
if(a[n+1]!=1)
{
aaa(n+1);
}
if(a[n+2]!=1)
{
aaa(n+2);
}
}求逆序对问题
题目描述
给定N个数的序列a1,a2,...aN，定义一个数对(ai, aj)为“重要逆序对”的充要条件为 i < j 且 ai > 2aj。求给定序列中“重要逆序对”的个数。
输入格式
本题有多个测试点，每个测试点分为两行：第一行为序列中数字的个数N（1 ≤ N ≤ 200000），第二行为序列a1, a2 ... aN(0 ≤a ≤ 10000000)，由空格分开。N=0表示输入结束。
输出格式
每个测试点一行，输出一个整数，为给序列中“重要逆序对”的个数。
样例
样例输入
10
0 9 8 7 6 5 4 3 2 1
0
样例输出
16
#include <bits/stdc++.h>
using namespace std;
int n;
int a[100010];
int cnt;
int main()
{
cin>>n;
while(n!=0)
{
for(int i = 1;i<=n;i++)
{
cin>>a[i];
}
for(int i = 1;i<=n;i++)
{
for(int j = 1;j<=n;j++)
{
if(i<j&&a[i]>2*a[j])
{
cnt++;
}
}
}
cout<<cnt<<endl;
cin>>n;
}
return 0;
}Bookshelf B超级书架
题目描述
Farmer John 最近为奶牛们的图书馆添置了一个巨大的书架，尽管它是如此的大，但它还是几乎瞬间就被各种各样的书塞满了。现在，只有书架的顶上还留有一点空间。
所有 头奶牛都有一个确定的身高 。设所有奶牛身高的和为 。书架的高度为 ，并且保证 。
为了够到比最高的那头奶牛还要高的书架顶，奶牛们不得不像演杂技一般，一头站在另一头的背上，叠成一座“奶牛塔”。当然，这个塔的高度，就是塔中所有奶牛的身高之和。为了往书架顶上放东西，所有奶牛的身高和必须不小于书架的高度。
显然，塔中的奶牛数目越多，整座塔就越不稳定，于是奶牛们希望在能够到书架顶的前提下，让塔中奶牛的数目尽量少。 现在，奶牛们找到了你，希望你帮她们计算这个最小的数目。
输入格式
第 行: 个用空格隔开的整数： 和 。
第 行: 第 行是 个整数：。
输出格式
第 行: 输出 个整数，即最少要多少头奶牛叠成塔，才能够到书架顶部
样例
样例输入
复制6 40
6
18
11
13
19
11
样例输出
复制3
样例说明
输入说明: 一共有6头奶牛，书架的高度为40，奶牛们的身高在6..19之间。
输出说明: 一种只用3头奶牛就达到高度40的方法：18+11+13。当然还有其他方法，在此不一一列出了。
#include <iostream>
#include <algorithm>
using namespace std;
int n,b;
int a[20010];
int main()
{
cin>>n>>b;
for(int i = 0;i<n;i++)
{
cin>>a[i];
}
sort(a+0,a+n);
int sum = 0;
int cnt = 0;
for(int i = n-1;i>=0;i--)
{
sum += a[i];
cnt++;
if(sum>=b)
{
cout<<cnt;
return 0;
}
}
return 0;
}抓住那头牛
题目描述
农夫知道一头牛的位置，想要抓住它。农夫和牛都位于数轴上，农夫起始位于点，牛位于点。农夫有两种移动方式：
1、从 移动到 或 ，每次移动花费一分钟
2、从 移动到 ，每次移动花费一分钟
假设牛没有意识到农夫的行动，站在原地不动。农夫最少要花多少时间才能抓住牛？
输入格式
两个整数， 和 。
输出格式
一个整数，农夫抓到牛所要花费的最小分钟数。
样例
样例输入
5 17
样例输出
4
样例解释
路线为： 5 -> 10 -> 9 -> 18 -> 17,共 4 步。
#include <bits/stdc++.h>
using namespace std;
struct point
{
int x,v;
point(){};
point(int a,int b)
{
x = a;
v = b;
}
};
point que[100010];
int head = 0;
int tail = 0;
int b[100010];
int n,m;
int cnt;
int dx[] = {1,-1,2};
int main()
{
cin>>n>>m;
b[n] = 1;
que[++tail] = {n,0};
while(head<tail)
{
head++;
bool t = false;
for(int i = 0;i<3;i++)
{
int tx;
if(i==2)
{
tx = que[head].x*dx[i];
}
else
{
tx = que[head].x+dx[i];
}
if(tx>=1&&tx<=100010&&b[tx]==0)
{
b[tx] = 1;
que[++tail] = {tx,que[head].v+1};
if(tx==m)
{
t = true;
break;
}
}
}
if(t==true)
{
break;
}
}
cout<<que[tail].v;
return 0;
}献给阿尔吉侬的花束
题目描述
阿尔吉侬是一只聪明又慵懒的小白鼠，它最擅长的就是走各种各样的迷宫。今天它要挑战一个非常大的迷宫，研究员们为了鼓励阿尔吉侬尽快到达终点，就在终点放了一块阿尔吉侬最喜欢的奶酪。现在研究员们想知道，如果阿尔吉侬足够聪明，它最少需要多少时间就能吃到奶酪。
迷宫用一个R×C的字符矩阵来表示。字符S表示阿尔吉侬所在的位置，字符E表示奶酪所在的位置，字符#表示墙壁，字符.表示可以通行。阿尔吉侬在1个单位时间内可以从当前的位置走到它上下左右四个方向上的任意一个位置，但不能走出地图边界。
输入格式
第一行是一个正整数T（1 ≤ T ≤ 10），表示一共有T组数据。
每一组数据的第一行包含了两个用空格分开的正整数R和C（2 ≤ R, C ≤ 200），表示地图是一个R×C的矩阵。
接下来的R行描述了地图的具体内容，每一行包含了C个字符。字符含义如题目描述中所述。保证有且仅有一个S和E。
输出格式
对于每一组数据，输出阿尔吉侬吃到奶酪的最少单位时间。若阿尔吉侬无法吃到奶酪，则输出“oop!”（只输出引号里面的内容，不输出引号）。每组数据的输出结果占一行。
样例
样例输入
3
3 4
.S..
###.
..E.
3 4
.S..
.E..
....
3 4
.S..
####
..E.
样例输出
5
1
oop!
#include <bits/stdc++.h>
using namespace std;
struct node
{
int x,y,v;
node(){};
node(int a,int b,int c)
{
x = a;
y = b;
v = c;
}
};
node que[10010];
char a[210][210];
int ma;
int n,m;
int sx,sy,ex,ey;
int head,tail;
int dx[] = {0,1,0,-1};
int dy[] = {1,0,-1,0};
int main()
{
int ttt;
cin>>ttt;
while(ttt!=0)
{
ttt--;
cin>>n>>m;
for(int i = 1;i<=n;i++)
{
for(int j = 1;j<=m;j++)
{
cin>>a[i][j];
if(a[i][j]=='S') sx = i,sy = j;
if(a[i][j]=='E') ex = i,ey = j;
}
}
head = 0;
tail = 0;
bool t = false;
que[++tail] = {sx,sy,0};
while(head<tail)
{
head++;
for(int i = 0;i<4;i++)
{
int tx = que[head].x+dx[i];
int ty = que[head].y+dy[i];
if(tx>=1&&tx<=n&&ty>=1&&ty<=m&&a[tx][ty]!='#')
{
a[tx][ty] = '#';
que[++tail] = {tx,ty,que[head].v+1};
if(tx==ex&&ty==ey)
{
cout<<que[tail].v<<endl;
t = true;
break;
}
}
}
if(t==true) break;
}
if(t==false) cout<<"oop!"<<endl;
}
return 0;
}