笔试——Day34

第一题

题目

ISBN号码

思路

模拟 分类讨论，注意最后一位为X时

代码

#include <iostream>
#include <string>
using namespace std;string str;int main() 
{cin >> str;int n = str.size();int a1 = str[0] - '0';int a2 = str[2] - '0';int a3 = str[3] - '0';int a4 = str[4] - '0';int a5 = str[6] - '0';int a6 = str[7] - '0';int a7 = str[8] - '0';int a8 = str[9] - '0';int a9 = str[10] - '0';int x = str[str.size() - 1] - '0';int y = (a1*1 + a2*2 + a3*3 + a4*4 + a5*5 + a6*6 + a7*7 + a8*8 + a9*9) % 11;if(y == 10){if(str[str.size() - 1] == 'X') cout << "Right" << endl;else{str[str.size() - 1] = 'X';cout << str << endl;}}else {if(x == y) cout << "Right" << endl;else{str[str.size() - 1] = y + '0';cout << str << endl;}}return 0;
}
// 64 位输出请用 printf("%lld")

第二题

题目：

kotori和迷宫

思路

BFS：当前位置没有搜过，且当前位置可以走时，加入队列

代码

#include <iostream>
#include <queue>
#include <cstring>using namespace std;
using PII = pair<int, int>;const int N = 40;
char a[N][N];
int dist[N][N];
queue<PII> q;
int n, m;
int x, y;int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};void bfs()
{memset(dist, -1, sizeof dist);dist[x][y] = 0;q.push({x, y});while(q.size()){auto [x1, y1] = q.front();q.pop();for(int k = 0; k < 4; k++){int nx = x1 + dx[k];int ny = y1 + dy[k];if(nx >= 1 && nx <= n && ny >= 1 && ny <= m && dist[nx][ny] == -1 && a[nx][ny] != '*'){dist[nx][ny] = dist[x1][y1] + 1;if(a[nx][ny] != 'e'){q.push({nx, ny});}}}}
}int main()
{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] == 'k'){x = i, y = j;}}bfs();int res = 0, min_dist = 1e9;for(int i = 1; i <= n; i++)for(int j = 1; j <= m; j++){if(dist[i][j] != -1 && a[i][j] == 'e'){res++;min_dist = min(min_dist, dist[i][j]);}}if(res == 0) cout << "-1" << endl;else cout << res << " " << min_dist << endl;return 0;
}

第三题

题目：

矩阵最长递增路径

思路

DFS搜索

代码

不加“备忘录”记忆

class Solution {int dx[4] = {0, 0, 1, -1};int dy[4] = {1, -1, 0, 0};int m, n;int maxLen; // 记录全局最长递增路径
public:int longestIncreasingPath(vector<vector<int>>& matrix) {m = matrix.size(), n = matrix[0].size();maxLen = 0;for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {dfs(matrix, i, j, 1); // 从 (i,j) 出发，当前路径长度为 1}}return maxLen;}void dfs(vector<vector<int>>& matrix, int i, int j, int currentLen) {maxLen = max(maxLen, currentLen); // 更新全局最大值for (int k = 0; k < 4; k++) {int x = i + dx[k], y = j + dy[k];if (x >= 0 && x < m && y >= 0 && y < n && matrix[x][y] > matrix[i][j]) {dfs(matrix, x, y, currentLen + 1); // 继续搜索更长的路径}}}
};

使用“备忘录”记忆

class Solution {int dx[4] = {0, 0, 1, -1};int dy[4] = {1, -1, 0, 0};int m, n;int memo[201][201];
public:int longestIncreasingPath(vector<vector<int>>& matrix) {m = matrix.size(), n = matrix[0].size();int res = 0;for(int i = 0; i < m; i++)for(int j = 0; j < n; j++)res = max(res, dfs(matrix, i ,j));return res;}int dfs(vector<vector<int>>& matrix, int i, int j){if(memo[i][j] != 0) return memo[i][j];int res = 1;for(int k = 0; k < 4; k++){int x = i + dx[k], y = j + dy[k];if(x >= 0 && x < m && y >= 0 && y < n && matrix[x][y] > matrix[i][j])res = max(res, dfs(matrix, x , y) + 1);}memo[i][j] = res;return res;}
};