-
青少年软件编程（202209）（C语言）等级考试（五级）试题及参考答案
等级标准
- 掌握基本算法中的分治技术；
- 掌握基本算法中的搜索剪枝技术；
- 掌握基本算法中的贪心算法；
- 能够使用上述方法编写指定功能的正确完整的程序。
一、城堡问题
考试题目
1 2 3 4 5 6 7 ############################# 1 # | # | # | | # #####---#####---#---#####---# 2 # # | # # # # # #---#####---#####---#####---# 3 # | | # # # # # #---#########---#####---#---# 4 # # | | | | # # ############################# (图 1) # = Wall | = No wall - = No wall- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
图1是一个城堡的地形图。请你编写一个程序，计算城堡一共有多少房间，最大的房间有多大。城堡被分割成m×n(m≤50，n≤50)个方块，每个方块可以有0~4面墙。
时间限制：1000
内存限制：65536输入
程序从标准输入设备读入数据。第1、2行每行1个整数，分别是南北向、东西向的方块数。在接下来的输入行里，每个方块用一个数字(0≤p≤50)描述。用一个数字表示方块周围的墙，1表示西墙，2表示北墙，4表示东墙，8表示南墙。每个方块用代表其周围墙的数字之和表示。城堡的内墙被计算两次，方块(1,1)的南墙同时也是方块(2,1)的北墙。输入的数据保证城堡至少有两个房间。输出
输出2行，每行一个数，表示城堡的房间数、城堡中最大房间所包括的方块数。结果显示在标准输出设备上。样例输入
4
7
11 6 11 6 3 10 6
7 9 6 13 5 15 5
1 10 12 7 13 7 5
13 11 10 8 10 12 13样例输出
5
9参考答案
#include#include #include using namespace std; int st[60][60]; int g[60][60]; int num,maxnum=0,anum=0; int n,m; void dfs(int x,int y){ if(st[x][y]!=0) return ;//如果走过就跳出 num++;//没走过房间数就加 st[x][y]=1;//标记一下走过了 if((g[x][y]&1)==0)dfs(x,y-1);//西 if((g[x][y]&2)==0)dfs(x-1,y);//北 if((g[x][y]&4)==0)dfs(x,y+1);//东 if((g[x][y]&8)==0)dfs(x+1,y);//南 } int main(){ scanf("%d%d",&n,&m); memset(st,0,sizeof st);//st=0表示没走过 for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ scanf("%d",&g[i][j]); } } for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ if(st[i][j]==0){//如果没走过 num=0;//记录房间数 anum++;//记录块数 dfs(i,j); maxnum=max(maxnum,num); } } } printf("%d\n%d",anum,maxnum); return 0; } - 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
二、斗地主大师
考试题目
斗地主大师今天有P个欢乐豆，他夜观天象，算出了一个幸运数字Q，如果他能有恰好Q个欢乐豆，就可以轻松完成程设大作业了。
斗地主大师显然是斗地主大师，可以在斗地主的时候轻松操控游戏的输赢。
1.他可以轻松赢一把，让自己的欢乐豆变成原来的Y倍
2.他也可以故意输一把，损失X个欢乐豆(注意欢乐豆显然不能变成负数，所以如果手里没有X个豆就不能用这个能力)
而斗地主大师还有一种怪癖，扑克除去大小王只有52张，所以他一天之内最多只会打52把斗地主。
斗地主大师希望你能告诉他，为了把P个欢乐豆变成Q个，他至少要打多少把斗地主？时间限制：1000
内存限制：65536输入
第一行4个正整数 P,Q,X,Y 0< P,X,Q <= 2^31, 1< Y <= 225输出
输出一个数表示斗地主大师至少要用多少次能力 如果打了52次斗地主也不能把P个欢乐豆变成Q个，请输出一行 “Failed”样例输入
输入样例1：
2 2333 666 8
输入样例2：
1264574 285855522 26746122 3样例输出
输出样例1：
Failed
输出样例2：
33提示
可以考虑深搜 要用long long参考答案
#includeusing namespace std; class Solution { private: int P; int Q; int X; int Y; int min_ok_play_count; //最少需要打多少次牌 int max_play_count; //打牌的最大次数 //t：当前有多少个欢乐豆 void dfs(int step, long long t){ if(step > 52) return; //剪枝，如果t大于Q的时候再翻Y倍，那么后面全是X操作都没用 if(t > Q + (52 - step) * X) return; if(t == Q) { min_ok_play_count = min(min_ok_play_count, step); return; } dfs(step + 1, t * Y); if(t > X) dfs(step + 1, t - X); } public: void load(int max_play_count){ scanf("%d%d%d%d", &P, &Q, &X, &Y); //printf("%d %d %d %d ", P, Q, X, Y); this->max_play_count = max_play_count; } void play_count(){ //设置比52大，用来判断52次内P变成Q是否可行 min_ok_play_count = max_play_count + 100; dfs(0, P); if(min_ok_play_count == max_play_count + 100){ printf("Failed"); }else{ printf("%d", min_ok_play_count); } } }; int main(){ #ifdef LOCAL freopen("202209_5_2.in", "r", stdin); #endif Solution s; s.load(52); s.play_count(); return 0; } - 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
三、玩具摆放
在一个4*4的方框内摆放了若干个相同的玩具。
某人想通过移动玩具，将这些玩具重新摆放成为他心中理想的状态。要求每次移动时，只能将某一个玩具向上下左右四个方向之一移动一步。不能将玩具移出方框，并且移动的目标位置不能已经放置有玩具。
请你用最少的移动次数将初始的玩具状态移动到他心中的目标状态。
时间限制：10000
内存限制：524288输入
前4行表示玩具的初始状态，每行4个数字1或0，1表示方格中放置了玩具，0表示没有放置玩具。 接着是一个空行。接下来4行表示玩具的目标状态，每行4个数字1或0，意义同上。输出
一个整数，所需要的最少移动次数。保证初始状态可以达到目标状态。样例输入
1111
0000
1110
00101010
0101
1010
0101样例输出
4
提示
可以考虑将玩具局面表示为一个16 bit的整数，设置一个标志数组用来判重，用这个整数做下标找其对应标志位参考答案
#include#include #include using namespace std; const int dx[5]={0,0,0,1,-1}; const int dy[5]={0,1,-1,0,0}; const int n=4; bool goal[5][5]; int vis[65536]; struct state{bool board[5][5];int step;}start; queue<state>Q; inline bool is_finished(state tmp) { register int i,j; for(i=1;i<=n;i++) for(j=1;j<=n;j++) if(goal[i][j]^tmp.board[i][j])return 0; return 1; } inline int change(state tmp) { register int i,j; int res=0; for(i=1;i<=n;i++) for(j=1;j<=n;j++) res=(res<<1)|tmp.board[i][j]; return res; } inline int BFS() { memset(vis,0x3f3f3f3f,sizeof(vis)); Q.push(start); while(!Q.empty()) { state now=Q.front(); Q.pop(); if(is_finished(now))return now.step; int BIN=change(now); if(vis[BIN]<=now.step)continue; vis[BIN]=now.step; register int i,j,k; for(i=1;i<=n;i++) for(j=1;j<=n;j++) for(k=1;k<=4;k++) { if(i+dx[k]>n||j+dy[k]>n||i+dx[k]<1||j+dy[k]<1)continue; if(now.board[i][j]==now.board[i+dx[k]][j+dy[k]])continue; swap(now.board[i][j],now.board[i+dx[k]][j+dy[k]]); now.step ++; Q.push(now); now.step --; swap(now.board[i][j],now.board[i+dx[k]][j+dy[k]]); } } return -1; } int main() { register int i,j; start.step=0; for(i=1;i<=n;i++) for(j=1;j<=n;j++) { char tmp;cin>>tmp; start.board[i][j]=(tmp=='0')?0:1; } for(i=1;i<=n;i++) for(j=1;j<=n;j++) { char tmp;cin>>tmp; goal[i][j]=(tmp=='0')?0:1; } cout<<BFS()<<endl; return 0; } - 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
四、哥斯拉大战金刚
考试试题
众所周知，哥斯拉和金刚是时代仇敌，大战一触即发。金刚为了打败哥斯拉，要先前往地心空洞获得战斧。金刚现在所在之处可以被视为一个n*m的网格图，S表示金刚目前的位置，T表示地心空洞的入口，X表示障碍物，.表示平地。在前往地心空洞之前，金刚必须先获得一系列打开地心空洞的钥匙（在地图上通过数字1,2,…,k表示），并且获得i类钥匙的前提是金刚已经获得了1,2,…,i-1类钥匙，金刚在拿到地图上所有种类的钥匙之后即可前往地心空洞的入口。另外，同一种类的钥匙可能有多把，金刚只需获得其中任意一把即可。金刚每一步可以朝上下左右四个方向中的一个移动一格，值得注意的是，哥斯拉为了阻挠金刚的计划，还在地图上设置了q个陷阱（在网格图中用G表示），金刚第一次进入某个陷阱需要花费额外的一步来破坏陷阱（这之后该陷阱即可被视为平地）。为了更好的掌握全局，请你帮金刚计算到达地心空洞入口所需要花费的最少步数。输入数据保证有解。
时间限制：6000
内存限制：262144输入
第一行输入两个整数n,m，表示网格图的大小。 接下来n行，每行输入m个字符，表示地图 1 ≤ n,m ≤ 100 1 ≤ k ≤ 9 1 ≤ q ≤ 7输出
输出一行包含一个整数，表示金刚到达地心空洞入口所需要花费的最少步数。样例输入
5 5
XX13X
X.GXX
S…T
XXGXX
…2样例输出
24解题思路
思路：广搜题，属于较为复杂的一种，既要收集钥匙也要破坏陷阱。
状态包括：x,y坐标，keys表示现在收集的钥匙种数，fighted表示是否已经消灭陷阱，steps记录此时的步数，layout是陷阱的分布（用short变量表示）。
去重：xy坐标+钥匙+陷阱分布
地图上的标识有
‘.’：平地；‘X’：障碍，不能通过；‘T’：终点；‘S’：起点；‘G’：陷阱；1~9的数字：钥匙
起点和没有拿完钥匙的终点，不能拿的钥匙，破坏完的陷阱都当做平地处理参考答案
#include#include #include #include #include using namespace std; struct point { int x, y; short keys; short fighted; int steps; short layout; point(int inx,int iny,short k,short f,int s, short l):x(inx),y(iny),keys(k),fighted(f),steps(s),layout(l){} }; char flags[105][105][10][130]; int n, m; int k, q; char maze[105][105]; vector<pair<int, int> >traps; int dx[4] = { -1,1,0,0 }; int dy[4] = { 0,0,-1,1 }; int findTraps(int x, int y) { for (int i = 0; i < q; i++) { if (traps[i].first == x && traps[i].second == y) return i; } } int main() { cin >> n >> m; int startx, starty; q = 0; k = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { cin >> maze[i][j]; if (maze[i][j] == 'S') { startx = i; starty = j; } if (maze[i][j] == 'G') { q++; traps.push_back(make_pair(i, j)); } if (maze[i][j] > '0'&&maze[i][j] <= '9') k = max(k, maze[i][j] - '0'); } } queue<point>myqueues; short oriLayout = (1 << q) - 1; myqueues.push(point(startx, starty, 0, 0, 0,oriLayout)); memset(flags, 0, sizeof(flags)); flags[startx][starty][0][oriLayout] = 1; while (!myqueues.empty()) { point top = myqueues.front(); myqueues.pop(); if (maze[top.x][top.y] == 'T'&&top.keys==k) { cout << top.steps << endl; break; } if (maze[top.x][top.y] == 'G'&&top.fighted == 0) { int index = findTraps(top.x, top.y); short layout = top.layout&(~(1 << index)); myqueues.push(point(top.x, top.y, top.keys, 1, top.steps + 1, layout)); flags[top.x][top.y][top.keys][layout] = 1; continue; } for (int i = 0; i < 4; i++) { int tx = top.x + dx[i]; int ty = top.y + dy[i]; if (tx < 0 || tx >= n || ty < 0 || ty >= m) continue; if (maze[tx][ty] == 'X') continue; else if (maze[tx][ty] == 'G') { if (flags[tx][ty][top.keys][top.layout]) continue; int index = findTraps(tx, ty); if ((top.layout >> index) & 1) //还没打 myqueues.push(point(tx, ty, top.keys, 0, top.steps + 1, top.layout)); else myqueues.push(point(tx, ty, top.keys, 1, top.steps + 1, top.layout)); flags[tx][ty][top.keys][top.layout] = 1; } else if (maze[tx][ty] == '.'||maze[tx][ty]=='S'||maze[tx][ty]=='T') { if (flags[tx][ty][top.keys][top.layout]) continue; myqueues.push(point(tx, ty, top.keys, 0, top.steps + 1, top.layout)); flags[tx][ty][top.keys][top.layout] = 1; } else { int key = maze[tx][ty] - '0'; if (key == top.keys + 1) { if (flags[tx][ty][key][top.layout]) continue; myqueues.push(point(tx, ty, key, 0, top.steps + 1, top.layout)); flags[tx][ty][key][top.layout] = 1; } else { if (flags[tx][ty][top.keys][top.layout]) continue; myqueues.push(point(tx, ty, top.keys, 0, top.steps + 1, top.layout)); flags[tx][ty][top.keys][top.layout] = 1; } } } } return 0; } - 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
- 103
- 104
- 105
- 106
- 107
- 108
-
相关阅读:
c++智能指针
计算机毕设源代码网站ssm基于web的在线学习平台
从租完ecs云服务器 使用docker建立用户 全过程
如何使用前端表格控件实现多数据源整合？
Redis实现Mybatis二级缓存
java毕业设计大学生心理咨询管理系统mybatis+源码+调试部署+系统+数据库+lw
Mat介绍
java毕业设计网站SpringBoot美容院预约管理系统
八种button的hover效果
软件测试面试题及答案 这个可以免费白嫖的题库不要错过了
- 原文地址：https://blog.csdn.net/cwdelphi/article/details/127710106
