总结:选择题难度挺高的,编程题前面2题还行,但是看上次笔试评论区有人发题解,上一次最后一题是扫雷,这一场是消消乐,看来阿里最后一题喜欢弄这种大模拟来恶心人了
总分:100分
时长:90分钟,19:00-8:30
题型:6道单选+6到多选+3道编程
分值:单选12分,多选24分,编程64分
选择部分就是八股文系列有Linux,Mysql,智力题,数据结构,操作系统,计算机网络
编程题知识点分布:模拟;前缀和;大模拟
时长:90分钟,19:00-8:30
题型:6道单选+6到多选+3道编程
分值:单选12分,多选24分,编程64分
选择部分就是八股文系列有Linux,Mysql,智力题,数据结构,操作系统,计算机网络
编程题知识点分布:模拟;前缀和;大模拟
第一题:小红的16进制数
题解:
注意输入的是字符串,可能是个超级大的 16进制数
我们枚举 16 进制每一位怎么表示就行;
这里用了 __builtin_popcount ,但暴力 for 统计一下也能 ac 的
我们枚举 16 进制每一位怎么表示就行;
这里用了 __builtin_popcount ,但暴力 for 统计一下也能 ac 的
代码:
#include<bits/stdc++.h> using namespace std; int main() { string s; cin >> s; int tot = 0; for (int i = 2; i < s.size(); i++) { char ch = s[i]; if (isdigit(ch)) ch -= '0'; else ch = 10+ch-'a'; tot += __builtin_popcount(ch); } cout << tot << endl; }
第二题:聚光灯下的人
有几种办法,一个是做前缀和的预处理,可以参考这个题目:
https://www.nowcoder.com/practice/acead2f4c28c401889915da98ecdc6bf?tpId=230&tqId=2021480&ru=/exam/oj&qru=/ta/dynamic-programming/question-ranking&sourceUrl=%2Fexam%2Foj%3Ftab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D230
不过一个是一维的,一个是二维的,前缀和:
分 4 个方向扫描一遍;
(小声bb:这个题目好像刚刚开始说明还写错了一点东西)
代码:
#include<bits/stdc++.h> using namespace std; const int MAXN=1023; int A[MAXN][MAXN]; int B[MAXN][MAXN]; int main() { int n, m; cin >> n >> m; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) cin >> A[i][j]; } int last = 0; for (int i = 0; i < n; i++) { last = 0; for (int j = 0; j < m; j++) if (!A[i][j]) B[i][j]+=last; else last = 1; last = 0; for (int j = m-1; j >= 0; j--) if (!A[i][j]) B[i][j]+=last; else last = 1; } for (int j = 0; j < m; j++) { last = 0; for (int i = 0; i < n; i++) if (!A[i][j]) B[i][j] += last; else last = 1; last = 0; for (int i = n-1; i >= 0; i--) if (!A[i][j]) B[i][j] += last; else last = 1; } int tot = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) tot += A[i][j] == 0?B[i][j]: 0; } cout << tot << endl; }
第三题:消消乐
最恶心的题目,大模拟题
分别写 4 个方向太累了;我们可以只写"左落"的情况,然后 对每一种情况 rotote 到和"左落"一样,处理完再 rotate 回来; (特别需要注意,rotate 之后,用于填充的序列,有些是 0和 0对应,有些是 0和 7 对应)
#include<bits/stdc++.h> using namespace std; void rotate(vector<string> &g) { vector<string> res(8, string(8, '.')); for (int x = 0; x < 8; x++) { for (int y = 0; y < 8; y++) res[7-y][x] = g[x][y]; } g = res; } void rotate(int &x, int &y) { int nx =7- y, ny = x; x = nx, y = ny; } string ops = "awds"; int dx[4]={0, 1, 0, -1}; int dy[4]={-1, 0, 1, 0}; int main(){ int n; while (cin >> n) { vector<string> G(8); for (auto &s: G) cin >> s; vector<string> S(8); for (auto &s: S) cin >> s; for (auto &s: S) reverse(s.begin(), s.end()); vector<int> pos(8); while (n--) { int x, y; cin >> x >> y; x--, y--; string op; cin >> op; //旋转成"左落"的情况 int r = ops.find(op[0]); for (int i = 0; i < r; i++) rotate(G), rotate(x, y); //用 bfs,进行"暴雷"操作 queue<pair<int, int>> Q; int tot = 0; char ch = G[x][y]; G[x][y] = '.', Q.push({x, y}), tot++; while (!Q.empty()) { auto [x, y] = Q.front(); Q.pop(); for (int i = 0; i < 4; i++) { int nx = x + dx[i], ny = y + dy[i]; if (!(0 <= nx && nx < 8 && 0 <= ny && ny < 8 && G[nx][ny] == ch)) continue; G[nx][ny] = '.', Q.push({nx, ny}), tot++; } } // "左落"的处理 for (int i = 0; i < 8; i++) { int l = 0; for (int j = 0; j < 8; j++) if (G[i][j] != '.') G[i][l++] = G[i][j]; int q = (r == 0 || r == 3)?i: 7-i; while (l < 8) G[i][l++] = S[q].back(), S[q].pop_back(); } //旋转回来 for (int i = 0; i < 4-r; i++) rotate(G), rotate(x, y); cout << tot << endl; } } }
全部评论
(12) 回帖