考级在即,这篇文章就来看看往年的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..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;
- }
复制代码
免责声明:如果侵犯了您的权益,请联系站长,我们会及时删除侵权内容,谢谢合作!更多信息从访问主页:qidao123.com:ToB企服之家,中国第一个企服评测及商务社交产业平台。 |