当前位置：首页 > backend >正文

杭电oj（1015、1016、1072、1075）题解

backend 2025/7/1 10:45:11

编辑

1015

题目

思路

整体思路

代码结构及具体思路

1. 全局变量定义

2. 深度优先搜索函数 dfs

3. main 函数

代码

1016

题目

思路

整体思路

代码结构及具体思路

1. 全局变量定义

2. prime 函数

3. print_ar 函数

4. dfs 函数（深度优先搜索函数）

5. main 函数

代码

1072

题目

思路

整体思路

代码结构及具体思路

1. 结构体定义

2. 全局变量定义

3. bfs 函数（广度优先搜索函数）

4. main 函数

复杂度分析

代码

1075

题目

思路

整体思路

代码具体执行步骤及思路

1. 数据结构定义

2. 读取字典

3. 读取待翻译内容

4. 翻译火星文句子

代码

1015

题目

思路

这段代码的主要思路是解决一个组合数学问题，具体是在给定一个整数 n 和一个由大写字母组成的字符串 s 的情况下，从字符串 s 中选取 5 个不同的字母，将它们转换为对应的数字（A 对应 1，B 对应 2，以此类推），然后代入到公式 a - b * b + c * c * c - d * d * d * d + e * e * e * e * e 中进行计算，看是否等于给定的整数 n。如果存在满足条件的组合，找出字典序最大的组合并输出；如果不存在，则输出 "no solution"。下面详细分析代码的思路和实现步骤：

整体思路

采用深度优先搜索（DFS）的方法来遍历所有可能的 5 个字母的组合。对于每一个组合，将字母转换为对应的数字并代入公式进行计算，判断是否等于 n，如果等于且该组合的字典序比之前记录的最大字典序组合还要大，则更新最大字典序组合。

代码结构及具体思路

1. 全局变量定义

int n;
string s;
string ans;
bool used[13];

n：存储输入的目标整数。
s：存储输入的由大写字母组成的字符串。
ans：存储满足条件的字典序最大的 5 个字母的组合，初始为空字符串。
used：布尔数组，用于标记字符串 s 中的每个字母是否已经在当前组合中被使用过。

2. 深度优先搜索函数 `dfs`

void dfs(int depth, string current) {if(depth == 5) {int a = current[0] - 'A' + 1;int b = current[1] - 'A' + 1;int c = current[2] - 'A' + 1;int d = current[3] - 'A' + 1;int e = current[4] - 'A' + 1;if (a - b * b + c * c * c - d * d * d * d + e * e * e * e * e == n) {if (current > ans) {ans = current;}}return;}for(int i = 0; i < s.size(); i++) {if(!used[i]) {used[i] = true;dfs(depth + 1, current + s[i]);used[i] = false;}}
}

终止条件：当 depth 等于 5 时，表示已经选取了 5 个字母，此时将这 5 个字母转换为对应的数字 a、b、c、d、e，代入公式 a - b * b + c * c * c - d * d * d * d + e * e * e * e * e 进行计算。如果结果等于 n 且当前组合的字典序比 ans 大，则更新 ans。
递归过程：遍历字符串 s 中的每个字母，如果该字母未被使用过，则标记为已使用，将其添加到当前组合 current 中，并递归调用 dfs 函数，深度 depth 加 1。递归返回后，将该字母标记为未使用，以便尝试其他组合。

3. `main` 函数

int main() {while(cin >> n >> s) {ans = "";if(n == 0 || s == "END") break;fill(used, used + 13, false);dfs(0, "");if(ans.empty()) {cout << "no solution" << endl;}else cout << ans << endl;}return 0;
}

输入处理：使用 while 循环不断读取输入的整数 n 和字符串 s，当 n 为 0 或者 s 为 "END" 时，结束循环。
初始化：每次循环开始时，将 ans 清空，并将 used 数组的所有元素初始化为 false。
深度优先搜索：调用 dfs 函数开始搜索所有可能的 5 个字母的组合。
输出结果：如果 ans 仍然为空，说明没有找到满足条件的组合，输出 "no solution"；否则输出 ans。

代码

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
int n;
string s;
string ans;
bool used[13];// 深度优先搜索函数
void dfs(int depth, string current) {if(depth==5){int a=current[0]-'A'+1;int b=current[1]-'A'+1;int c=current[2]-'A'+1;int d=current[3]-'A'+1;int e=current[4]-'A'+1;if (a - b * b + c * c * c - d * d * d * d + e * e * e * e * e == n) {if (current > ans) {ans = current;}}return;} for(int i=0;i<s.size();i++){if(!used[i]){used[i]=true;dfs(depth+1,current+s[i]);used[i]=false;}}
}int main() {while(cin>>n>>s){ans="";if(n==0 || s=="END") break;fill(used,used+13,false);dfs(0,"");if(ans.empty()){cout<<"no solution"<<endl;}else cout<<ans<<endl;}return 0;
}

1016

题目

思路

这段代码的主要思路是解决一个关于素数环的问题。素数环是指将从 1 到 n 的数字排列成一个环，使得相邻两个数字之和为素数，并且最后一个数字与第一个数字之和也为素数。代码使用深度优先搜索（DFS）算法来找出所有满足条件的素数环排列，并将其打印输出。以下是对代码思路的详细分析：

整体思路

使用深度优先搜索算法，从数字 1 开始，逐步尝试将未使用过的数字添加到当前排列中，同时检查相邻数字之和是否为素数。当排列长度达到 n 时，检查最后一个数字与第一个数字之和是否为素数，如果是，则输出该排列。

代码结构及具体思路

1. 全局变量定义

int cnt = 0;
bool used[25];
int n;
vector<int> a;

cnt：用于记录测试用例的编号。
used：布尔数组，用于标记从 1 到 n 的每个数字是否已经在当前排列中被使用过。
n：表示要排列的数字范围是从 1 到 n。
a：vector 容器，用于存储当前的排列。

2. `prime` 函数

bool prime(int num) {if (num <= 1) return false;if (num == 2) return true;for (int i = 2; i * i <= num; i++) {if (num % i == 0) return false;}return true;
}

该函数用于判断一个数是否为素数。如果数字小于等于 1，则不是素数；如果数字为 2，则是素数；否则，从 2 开始到该数字的平方根进行遍历，如果能被其中任何一个数整除，则不是素数，否则是素数。

3. `print_ar` 函数

void print_ar() {for (int i = 0; i < a.size(); i++) {if (i > 0) cout << " ";cout << a[i];}cout << endl;
}

该函数用于打印 vector 容器 a 中的元素，元素之间用空格分隔，最后换行。

4. `dfs` 函数（深度优先搜索函数）

void dfs(int num, int step) {if (step == n) {// 检查最后一个数与第一个数的和是否为素数if (prime(num + a[0])) {a.push_back(num);print_ar();a.pop_back();}return;}if (!used[num]) {used[num] = true;a.push_back(num);for (int i = 2; i <= n; i++) {if (!used[i] && prime(num + i)) {dfs(i, step + 1);}}a.pop_back();used[num] = false;}
}

终止条件：当 step 等于 n 时，表示已经排列了 n 个数字，此时检查最后一个数字 num 与第一个数字 a[0] 之和是否为素数。如果是，则将 num 添加到 a 中，调用 print_ar 函数打印该排列，然后将 num 从 a 中移除。
递归过程：如果 num 未被使用过，则标记为已使用，并将其添加到 a 中。然后从 2 到 n 遍历每个数字 i，如果 i 未被使用且 num + i 为素数，则递归调用 dfs 函数，将 i 作为下一个数字，step 加 1。递归返回后，将 num 从 a 中移除，并将其标记为未使用。

5. `main` 函数

int main() {while (cin >> n) {cnt++;cout << "Case " << cnt << ":" << endl;fill(used, used + 25, false);a.clear();dfs(1, 1);}return 0;
}

输入处理：使用 while 循环不断读取输入的 n，直到输入结束。
初始化：每次循环开始时，cnt 加 1，输出当前测试用例的编号。将 used 数组的所有元素初始化为 false，清空 a 容器。
深度优先搜索：调用 dfs 函数，从数字 1 开始进行深度优先搜索，初始步数为 1。

代码

#include <iostream>
#include <vector>
using namespace std;
int cnt=0;
bool used[25];
int n;
vector<int> a;// 判断一个数是否为素数
bool prime(int num) {if (num <= 1) return false;if (num == 2) return true;for (int i = 2; i * i <= num; i++) {if (num % i == 0) return false;}return true;
}// 打印向量中的元素
void print_ar() {for (int i = 0; i < a.size(); i++) {if (i > 0) cout << " ";cout << a[i];}cout << endl;
}// 深度优先搜索函数
void dfs(int num, int step) {if (step == n) {// 检查最后一个数与第一个数的和是否为素数if (prime(num + a[0])) {a.push_back(num);print_ar();a.pop_back();}return;}if (!used[num]) {used[num] = true;a.push_back(num);for (int i = 2; i <= n; i++) {if (!used[i] && prime(num + i)) {dfs(i, step + 1);}}a.pop_back();used[num] = false;}
}int main() {while (cin >> n) {cnt++;cout<<"Case "<<cnt<<":"<<endl;fill(used, used + 25, false);a.clear();dfs(1, 1);}return 0;
}

1072

题目

思路

这段代码的主要思路是解决一个迷宫寻路问题，使用广度优先搜索（BFS）算法来寻找从起点到终点的最短路径，同时考虑了炸弹爆炸时间的限制。以下是对代码思路的详细分析：

整体思路

在一个 \(N\times M\) 的迷宫地图中，有起点（标记为 2）、终点（标记为 3）、普通通路（标记为 1）、炸弹补充点（标记为 4）和障碍物（标记为 0）。玩家从起点出发，身上携带一个炸弹，初始爆炸剩余时间为 6 个单位时间。每移动一步，炸弹爆炸剩余时间减 1。当炸弹爆炸剩余时间为 1 时，若未到达终点则不能继续前进。当玩家到达炸弹补充点时，炸弹爆炸剩余时间重置为 6，且该补充点会变为障碍物。使用 BFS 算法遍历迷宫，找到从起点到终点的最短路径所需的总时间，若无法到达终点则返回 -1。

代码结构及具体思路

1. 结构体定义

struct node{int x, y;int stime; // 炸弹爆炸剩余时间 int etime; // 总时间 
};

定义了一个结构体 node 来表示迷宫中的一个状态，包含当前位置的坐标 (x, y)、炸弹爆炸剩余时间 stime 和从起点到当前位置的总时间 etime。

2. 全局变量定义

int T, M, N;
int dxy[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
int map[10][10];
int bx, by;

T：表示测试用例的数量。
M 和 N：分别表示迷宫地图的列数和行数。
dxy：一个二维数组，用于表示上下左右四个方向的偏移量，方便进行搜索。
map：二维数组，用于存储迷宫地图。
bx 和 by：表示起点的坐标。

3. `bfs` 函数（广度优先搜索函数）

int bfs(int x, int y) {queue<node> q;while (!q.empty()) {q.pop();}node stare, temp;stare.x = x;stare.y = y;stare.etime = 0;stare.stime = 6;q.push(stare);while (!q.empty()) {temp = q.front();q.pop();if (map[temp.x][temp.y] == 3) {return temp.etime;}if (temp.stime == 1) continue;// 搜索 for (int i = 0; i < 4; i++) {int mx = temp.x + dxy[i][0];int my = temp.y + dxy[i][1];if (mx < 0 || mx >= N || my < 0 || my >= M || map[mx][my] == 0) continue;stare.x = mx;stare.y = my;stare.stime = temp.stime - 1;stare.etime = temp.etime + 1;if (map[mx][my] == 4) {stare.stime = 6;map[mx][my] = 0;}q.push(stare);}}return -1;
}

初始化队列：创建一个队列 q，将起点状态 stare 入队，起点的炸弹爆炸剩余时间初始化为 6，总时间初始化为 0。
BFS 循环：当队列不为空时，取出队首元素 temp。
- 判断是否到达终点：如果当前位置是终点（map[temp.x][temp.y] == 3），则返回总时间 temp.etime。
- 检查炸弹剩余时间：如果炸弹爆炸剩余时间为 1，则跳过该状态，因为无法继续前进。
- 搜索相邻位置：遍历四个方向，计算相邻位置的坐标 (mx, my)。如果相邻位置越界或为障碍物（map[mx][my] == 0），则跳过。否则，更新相邻位置的状态，炸弹爆炸剩余时间减 1，总时间加 1。如果相邻位置是炸弹补充点（map[mx][my] == 4），则将炸弹爆炸剩余时间重置为 6，并将该位置标记为障碍物（map[mx][my] = 0），然后将该状态入队。
无法到达终点：如果队列为空仍未到达终点，则返回 -1。

4. `main` 函数

int main() {cin >> T;while (T--) {cin >> N >> M;for (int i = 0; i < N; i++) { // 输入地图 for (int j = 0; j < M; j++) {cin >> map[i][j];if (map[i][j] == 2) {bx = i;by = j;}}}int res = bfs(bx, by);cout << res << endl;}return 0;
}

输入处理：首先读取测试用例的数量 T。对于每个测试用例，读取迷宫地图的行数 N 和列数 M，并输入迷宫地图。同时，记录起点的坐标 (bx, by)。
调用 BFS 函数：调用 bfs 函数从起点开始进行广度优先搜索，得到从起点到终点的最短路径所需的总时间 res。
输出结果：输出结果 res。

复杂度分析

时间复杂度：由于使用了 BFS 算法，每个位置最多被访问一次，因此时间复杂度为 \(O(N\times M)\)，其中 N 和 M 分别是迷宫地图的行数和列数。
空间复杂度：主要是队列的空间开销，最坏情况下队列中可能存储所有位置的状态，因此空间复杂度为 \(O(N\times M)\)。

代码

#include<iostream>
#include<queue>
using namespace std;
struct node{int x,y;int stime;//炸弹爆炸剩余时间 int etime;//总时间 
};
int T,M,N;
int dxy[4][2]={{-1,0},{0,1},{1,0},{0,-1}};
int map[10][10];
int bx,by;
int bfs(int x,int y){queue<node>q;while(!q.empty()){q.pop();}node stare,temp;stare.x=x;stare.y=y;stare.etime=0;stare.stime=6;q.push(stare);while(!q.empty()){temp=q.front();q.pop();if(map[temp.x][temp.y]==3){return temp.etime;}if(temp.stime==1) continue;// 搜索 for(int i=0;i<4;i++){int mx=temp.x+dxy[i][0];int my=temp.y+dxy[i][1];if(mx<0 || mx>N || my<0 || my>M || map[mx][my]==0) continue;stare.x=mx;stare.y=my;stare.stime=temp.stime-1;stare.etime=temp.etime+1;if(map[mx][my]==4){stare.stime=6;map[mx][my]=0;}q.push(stare);}}return -1;
}
int main(){cin>>T;while(T--){cin>>N>>M;for(int i=0;i<N;i++){//输入地图 for(int j=0;j<M;j++){cin>>map[i][j];if(map[i][j]==2){bx=i;by=j;}}}int res = bfs(bx,by);cout<<res<<endl;}return 0;
}

1075

题目

思路

这段代码的核心思路是实现一个简单的火星文到英文的翻译程序。下面为你详细分析其实现思路：

整体思路

程序主要分为两个阶段：一是读取并存储火星文与英文的对应字典；二是利用这个字典对输入的火星文句子进行翻译。

代码具体执行步骤及思路

1. 数据结构定义

struct zd {string yw;  // 英文 string hxw; // 火星文 
};
vector<zd> p;

定义了一个结构体 zd，用于存储英文和对应的火星文。
使用 vector<zd> 类型的 p 来存储多组英文 - 火星文的对应关系，也就是字典。

2. 读取字典

cin >> sstart;
cin.ignore();
while (1) {cin >> s1;if (s1 == "END") break;cin >> s2;zd temp;temp.yw = s1;temp.hxw = s2;p.push_back(temp);
}

首先读取一个起始标识 sstart，cin.ignore() 用于忽略输入缓冲区中的换行符。
接着进入一个无限循环，不断读取两个字符串 s1 和 s2，分别作为英文和火星文。
当读取到的 s1 为 "END" 时，循环结束，表明字典读取完毕。
每次读取到有效的英文和火星文后，创建一个 zd 结构体对象 temp，将英文和火星文赋值给它，再把 temp 添加到 p 中。

3. 读取待翻译内容

cin >> sstart;
cin.ignore();

再次读取一个起始标识 sstart，并忽略输入缓冲区中的换行符，为读取待翻译的火星文句子做准备。

4. 翻译火星文句子

while (1) {getline(cin, s3);if (s3 == "END") break;string tempstr = "";string ans = "";for (int i = 0; i < s3.size(); i++) {if ('a' <= s3[i] && s3[i] <= 'z') {tempstr += s3[i];} else {bool found = false;for (int j = 0; j < p.size(); j++) {if (p[j].hxw == tempstr) {ans += p[j].yw;found = true;break;}}if (!found) {ans += tempstr;}tempstr = "";ans += s3[i];}}// 处理最后一个积累的火星文bool found = false;for (int j = 0; j < p.size(); j++) {if (p[j].hxw == tempstr) {ans += p[j].yw;found = true;break;}}if (!found) {ans += tempstr;}cout << ans << endl;
}

进入一个无限循环，使用 getline 逐行读取待翻译的火星文句子。当读取到 "END" 时，循环结束。
对于每一行火星文句子，使用 tempstr 来临时存储连续的小写字母（即可能的火星文单词），使用 ans 来存储翻译后的结果。
遍历句子中的每个字符：
- 若字符是小写字母，将其添加到 tempstr 中。
- 若字符不是小写字母，说明一个可能的火星文单词结束，此时在字典 p 中查找该火星文对应的英文：
  - 若找到，将对应的英文添加到 ans 中。
  - 若未找到，将 tempstr 原样添加到 ans 中。
  - 清空 tempstr，并将当前非小写字母字符添加到 ans 中。
遍历结束后，还需处理最后一个积累的 tempstr，同样在字典中查找，若找到则添加对应英文，未找到则原样添加，最后输出翻译结果 ans。

代码

#include <iostream>
#include <vector>
#include <string>
using namespace std;
struct zd {string yw;  // 英文 string hxw; // 火星文 
};
vector<zd> p;
string sstart, send;
string s1, s2, s3;
int main() {cin >> sstart;cin.ignore();while (1) {cin >> s1;if (s1 == "END") break;cin >> s2;zd temp;temp.yw = s1;temp.hxw = s2;p.push_back(temp);}cin >> sstart;cin.ignore();while (1) {getline(cin, s3);if (s3 == "END") break;string tempstr = "";string ans = "";for (int i = 0; i < s3.size(); i++) {if ('a' <= s3[i] && s3[i] <= 'z') {tempstr += s3[i];} else {bool found = false;for (int j = 0; j < p.size(); j++) {if (p[j].hxw == tempstr) {ans += p[j].yw;found = true;break;}}if (!found) {ans += tempstr;}tempstr = "";ans += s3[i];}}// 处理最后一个积累的火星文bool found = false;for (int j = 0; j < p.size(); j++) {if (p[j].hxw == tempstr) {ans += p[j].yw;found = true;break;}}if (!found) {ans += tempstr;}cout << ans << endl;}return 0;
}

查看全文

http://www.xdnf.cn/news/3118.html