阿里巴巴校招笔试研发岗-0314场
总结：选择题难度挺高的，编程题前面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;
}
}
} 
