等级考试（五级）试题及参考答案"/>
青少年软件编程（202209）（C语言）（分治搜索贪心）等级考试（五级）试题及参考答案
等级标准
- 掌握基本算法中的分治技术；
- 掌握基本算法中的搜索剪枝技术；
- 掌握基本算法中的贪心算法；
- 能够使用上述方法编写指定功能的正确完整的程序。
一、城堡问题
考试题目
1 2 3 4 5 6 7 #############################1 # | # | # | | ######---#####---#---#####---#2 # # | # # # # ##---#####---#####---#####---#3 # | | # # # # ##---#########---#####---#---#4 # # | | | | # ##############################(图 1)# = Wall | = No wall- = No wall
图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<iostream>
#include<algorithm>
#include<cstring>
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;
}
二、斗地主大师
考试题目
斗地主大师今天有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
参考答案
#include<bits/stdc++.h>
using 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 LOCALfreopen("202209_5_2.in", "r", stdin);
#endifSolution s;s.load(52);s.play_count();return 0;
}
三、玩具摆放
在一个4*4的方框内摆放了若干个相同的玩具。
某人想通过移动玩具，将这些玩具重新摆放成为他心中理想的状态。要求每次移动时，只能将某一个玩具向上下左右四个方向之一移动一步。不能将玩具移出方框，并且移动的目标位置不能已经放置有玩具。
请你用最少的移动次数将初始的玩具状态移动到他心中的目标状态。
时间限制：10000
内存限制：524288
输入
前4行表示玩具的初始状态，每行4个数字1或0，1表示方格中放置了玩具，0表示没有放置玩具。 接着是一个空行。接下来4行表示玩具的目标状态，每行4个数字1或0，意义同上。
输出
一个整数，所需要的最少移动次数。保证初始状态可以达到目标状态。
样例输入
1111
0000
1110
0010
1010
0101
1010
0101
样例输出
4
提示
可以考虑将玩具局面表示为一个16 bit的整数，设置一个标志数组用来判重，用这个整数做下标找其对应标志位
参考答案
#include<iostream>
#include<queue>
#include<cstring>
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;
}
四、哥斯拉大战金刚
考试试题
众所周知，哥斯拉和金刚是时代仇敌，大战一触即发。金刚为了打败哥斯拉，要先前往地心空洞获得战斧。金刚现在所在之处可以被视为一个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 <iostream>
#include <queue>
#include <cstring>
#include <vector>
#include <algorithm>
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));elsemyqueues.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;
}
更多推荐
青少年软件编程（202209）（C语言）（分治搜索贪心）等级考试（五级）试题及参考答案
发布评论