阿里数分笔试

第一题居然是SQL题，好像和牛客SQL篇有些题目类似，

考点：join 操作， sum和 count 函数

select sum(goods_tb.goods_price * sales_num) as sales_total,

sum(goods_tb.goods_price * sales_num)/count(distinct sales_tb.user_id) as per_trans

from sales_tb join goods_tb

on sales_tb.goods_id = goods_tb.goods_id

第二题是一个什么完美数组，具体题目忘记了，但是大体如下:

先排序，然后从小到大扫描；

发现A[i] <=A[i-1]时，需要将 A[i]调整到A[i-1]+1；举例：[1，2，2，2，5，5] 调整为 [1,2,3,4,5,6]

由于一次操作是选择多个数加 1，所以将A[i]调整到A[i-1]都是可以在调整A[i]之前完成

[1，2，2，2，5，5]

=>[1, 2, 3, 2, 5, 5]

=>[1, 2, 3, 4 , 5, 5]

=>[1, 2, 3, 4, 5, 6]

#include<bits/stdc++.h>
using namespace std;
int main() {
  int n; cin >> n;
  vector<int> A(n); for (auto &a: A) cin >> a;
  sort(A.begin(), A.end());
  int ans = 0;
  for (int i = 1; i < n; i++) {
    if (A[i] <= A[i-1]) A[i] = A[i-1]+1, ans++;
  }
  cout << ans << endl;
}

第三题扫雷，好像别的人发了题面了吧，我题面也不太记得了，太长了

枚举所有的摆放状态state，判断 state 和输入有没有冲突；

如果没有冲冲突，即state 是一个合法的状态；

我们设这个合法的状态的集合为 S；

如果位置(x,y), 在所有的合法状态 s 属于 S 中，s[x][y]都是雷，那么(x,y)这个位置就一定是雷

如果位置(x,y), 在所有的合法状态 s 属于 S 中，s[x][y]都不是雷，那么(x,y)这个位置就一定不是雷

实现：棋盘只有 16 个位置，枚举用用bitset 表示状态

#include<bits/stdc++.h>
using namespace std;

const int MAX_STATE = (1<<16)-1;

int id(int x, int y) {
  return x*4+y;
}
// state表示一个集合，计算(x,y)是否在集合中
bool isIn(int state, int x, int y) {
  return (state>>id(x, y)) & 1;
}
// 计算state表示的状态中，(x,y)位置的周围有多个个雷
int countBoom(int state, int x, int y) {
  int tot = 0;
  for (int nx = max(0, x-1); nx <= min(3, x+1); nx++) {
    for (int ny = max(0, y-1); ny <= min(3, y+1); ny++) {
      tot += isIn(state, nx, ny);
    }
  }
  return tot;
}
// 判断一个 state 是否和输入的布局有冲突
bool isStateValid(int state, vector<string> &G) {
  for (int x = 0; x < 4; x++) {
    for (int y = 0; y < 4; y++) {
      if (G[x][y] == '.') continue;
      if (isIn(state, x, y)) return false;
      if (G[x][y]  - '0' != countBoom(state, x, y)) return false;
    }
  }
  return true;
}

int main() {
  vector<string> G(4); for (auto &g: G) cin >> g;

  int mustBomb = MAX_STATE;
  int notBomb = MAX_STATE;
  //枚举所有状态
  for (int state = 0; state <= MAX_STATE; state++) {
    if (!isStateValid(state, G)) continue;
    mustBomb &= state;
    notBomb &= MAX_STATE ^ state;
  }

  for (int x = 0; x < 4; x++) {
    for (int y = 0; y < 4; y++) {
      if (G[x][y] == '.' && isIn(mustBomb, x, y)) cout << 'X';
      else if (G[x][y] == '.' && isIn(notBomb, x, y)) cout << 'O';
      else cout << G[x][y];
    }
    cout << endl;
  }

}

#阿里巴巴##笔经#