阿里巴巴校招笔试研发岗-0314场

总结：选择题难度挺高的，编程题前面2题还行，但是看上次笔试评论区有人发题解，上一次最后一题是扫雷，这一场是消消乐，看来阿里最后一题喜欢弄这种大模拟来恶心人了

总分:100分
时长:90分钟，19:00-8:30
题型:6道单选+6到多选+3道编程
分值:单选12分，多选24分，编程64分
选择部分就是八股文系列有Linux，Mysql，智力题，数据结构，操作系统，计算机网络
编程题知识点分布：模拟;前缀和;大模拟

第一题:小红的16进制数

题解:

注意输入的是字符串，可能是个超级大的 16进制数
我们枚举 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;
    }
  }
}

#阿里巴巴##笔经#