首页 > 【2021】阿里巴巴编程题（2星） 题解
头像
肖战公关团队
发布于 2021-06-03 19:51
+ 关注

【2021】阿里巴巴编程题（2星） 题解

题目链接：https://www.nowcoder.com/test/30440590/summary

非官方

1 - 完美对

Description

完美对

Solution

显然可以分离参数，则可以变成下面个等式。

令，那么当且仅当与每个位置都是相反数时，物品和为完美对。

那么枚举每一个物品，然后去找有多少个完美对即可。

容易想到把个数组哈希成一个数就可以存进哈希表里了。

而C++中std::vector自带字典序比较函数，所以直接可以作为std::map的key，就不需要写哈希了。

Code

#include <bits/stdc++.h>
const int _______ = []() { std::ios::sync_with_stdio(false), std::cin.tie(nullptr); return 0; }();

int main() {
  int n, k; std::cin >> n >> k;
  std::map<std::vector<int>, int> dict;
  int ans = 0;
  for (int i = 0; i < n; i++) {
    std::vector<int> a(k), b(k);
    for (int j = 0; j < k; j++) {
      std::cin >> a[j];
      b[j] = a[j] - a[0];
    }
    ans += dict[b];
    for (int j = 0; j < k; j++) {
      b[j] = -b[j];
    }
    dict[b]++;
  }
  std::cout << ans << "\n";
}

2 - 选择物品

Description

选择物品

Solution

DFS模拟一下即可（brute force）。

Code

#include <bits/stdc++.h>
const int _______ = []() { std::ios::sync_with_stdio(false), std::cin.tie(nullptr); return 0; }();

void dfs(int n, int m, int f, std::vector<int>& a) {
  if (static_cast<int>(a.size()) == m) {
    for (int i = 0; i < m; i++) {
      std::cout << a[i] << " \n"[i + 1 == m];
    }
    return;
  }
  for (int i = f; i <= n; i++) {
    a.push_back(i);
    dfs(n, m, i + 1, a);
    a.pop_back();
  }
}

int main() {
  int n, m; std::cin >> n >> m;
  std::vector<int> a;
  dfs(n, m, 1, a);
}

Python原生库，用了都说好。

from itertools import combinations
n, m = map(int, input().split())
for o in combinations(range(1, n + 1), m):
    print(' '.join([str(e) for e in o]))

3 - 小强去春游

Description

小强去春游

Solution

样例给的很好，把做法都告诉你了。

如果有4个人以上，那么有两种比较优的情况送最重的两个人到对岸而且要用到两个最轻的人做工具人。

如果这四个人的体重由小到大排序为、、、。

第一种情况是：一个最轻的人带一个一个最重的人过河，然后最轻的人回到原来的地方；然后再做一遍同样的操作带次重的人过河。代价为。

第二种情况是：两个最轻的人先过河，然后最轻回到原来的地方，然后最重的和次重的过河，最后次轻的会到原来的地方。代价为。

一直采用这两种方式的代价最小的方式，知道人数少于4个人则是最优的。

少于4个人时只有一种最优策略，都考虑一遍即可。

Code

#include <bits/stdc++.h>
const int _______ = []() { std::ios::sync_with_stdio(false), std::cin.tie(nullptr); return 0; }();

int main() {
  int T; std::cin >> T;
  while (T--) {
    int n; std::cin >> n;
    std::vector<int> a(n);
    for (int i = 0; i < n; i++) {
      std::cin >> a[i];
    }
    std::sort(a.begin(), a.end());
    int last = n - 1;
    int ans = 0;
    while (last >= 3) {
      ans += std::min(a[0] + a[last] + a[0] + a[last - 1], a[0] + a[1] * 2 + a[last]);
      last -= 2;
    }
    if (last == 2) {
      ans += a[0] + a[1] + a[2];
    } else if (last == 1) {
      ans += a[1];
    } else if (last == 0) {
      ans += a[0];
    }
    std::cout << ans << "\n";
  }
}

4 - 比例问题

Description

比例问题

Solution

首先给通分成最简分式。

然后选之间最大的的倍数，然后用求出，即在是最大的情况下所能的最大值。

若的值超出的范围，则用同样的方法先算出，然后再求出，显然这样不会超出范围。

Code

#include <bits/stdc++.h>
const int _______ = []() { std::ios::sync_with_stdio(false), std::cin.tie(nullptr); return 0; }();

int main() {
  int64_t A, B, a, b; std::cin >> A >> B >> a >> b;
  int64_t g = std::__gcd(a, b);
  a /= g;
  b /= g;
  int64_t x = A / a * a;
  int64_t y = x / a * b;
  if (y > B) {
    y = B / b * b;
    x = y / b * a;
  }
  std::cout << x << " " << y << "\n";
}

5 - 小强修水渠

Description

比例问题

Solution

若水渠为，距离和即。

对于而言，若将作为横坐标轴，作为纵坐标轴，则这个函数是一个先减后增的函数。

多个先减后增函数相加一定还是一个先减后增的函数。（不会证明）

那么求这个函数的最低点用三分法即可求出。

（当然由于本题的式子比较特殊，所以可以有更简单的方法，我自己写的是一个普适的做法）

#include <bits/stdc++.h>
const int _______ = []() { std::ios::sync_with_stdio(false), std::cin.tie(nullptr); return 0; }();

int main() {
  int n; std::cin >> n;
  std::vector<std::pair<int, int>> a(n);
  for (int i = 0; i < n; i++) {
    std::cin >> a[i].first >> a[i].second;
  }
  auto Calc = [&](int x) -> int64_t {
    int64_t ans = 0;
    for (int i = 0; i < n; i++) {
      ans += abs(x - a[i].first);
    }
    return ans;
  };
  int left = 0, right = 100000;
  while (left + 5 < right) {
    int lmid = (right - left) / 3 + left;
    int rmid = right - (right - left) / 3;
    int64_t lans = Calc(lmid);
    int64_t rans = Calc(rmid);
    if (lans > rans) {
      left = lmid;
    } else {
      right = rmid;
    }
  }
  int64_t ans = INT64_MAX;
  for (int i = left; i <= right; i++) {
    ans = std::min(ans, Calc(i));
  }
  std::cout << ans << '\n';
}

6 - 国际交流会

Description

国际交流会

Solution

若排序后的序列为，则差异和为。

如果将绝对值符号拆出来，每个数都会被运算两次，有三种情况：两次加，一次加一次减，两次减。

加和减的数量是要一致的，所以会希望两次加的情况尽量都给大的数，然后两次减的情况尽量都给小的数。

当是偶数的情况下，可以有个数进行两次加，另外个数进行两次减。

当是奇数的情况下，可以有个数进行两次加，还有个数进行两次减，还有一个数进行一次加一次减。

分配座位时候只要保证上面的情况成立就是最优的情况。

Code

#include <bits/stdc++.h>
const int _______ = []() { std::ios::sync_with_stdio(false), std::cin.tie(nullptr); return 0; }();

int main() {
  int n; std::cin >> n;
  std::vector<int> a(n);
  for (int i = 0; i < n; i++) {
    std::cin >> a[i];
  }
  std::sort(a.begin(), a.end());
  std::vector<int> b(n);
  for (int from = 0, to = n - 1, i = 0; i < n; i++) {
    if (i & 1) {
      b[i] = a[from];
      from++;
    } else {
      b[i] = a[to];
      to--;
    }
  }
  int64_t ans = 0;
  for (int i = 0; i < n; i++) {
    ans += abs(b[i] - b[(i + 1) % n]);
  }
  std::cout << ans << '\n';
  for (int i = 0; i < n; i++) {
    std::cout << b[i] << " \n"[i + 1 == n];
  }
}

7 - 小强的神奇矩阵

Description

小强的神奇矩阵

Solution

在一个位置选一个数只对前面一个数和后面一个数有影响。

那么表示已经选了个数第个数选的是第个数的最小值。

转移方程：。

Code

#include <bits/stdc++.h>
const int _______ = []() { std::ios::sync_with_stdio(false), std::cin.tie(nullptr); return 0; }();

int main() {
  int n; std::cin >> n;
  std::vector<std::vector<int>> a(n, std::vector<int>(3));
  for (int j = 0; j < 3; j++) {
    for (int i = 0; i < n; i++) {
      std::cin >> a[i][j];
    }
  }
  std::vector<std::vector<int64_t>> dp(n, std::vector<int64_t>(3, INT64_MAX));
  dp[0][0] = dp[0][1] = dp[0][2] = 0;
  for (int i = 1; i < n; i++) {
    for (int j = 0; j < 3; j++) {
      for (int k = 0; k < 3; k++) {
        dp[i][k] = std::min(dp[i][k], dp[i - 1][j] + abs(a[i - 1][j] - a[i][k]));
      }
    }
  }
  std::cout << std::min({dp[n - 1][0], dp[n - 1][1], dp[n - 1][2]}) << "\n";
}

8 - 蚂蚁森林之王

Description

蚂蚁森林之王

Solution

把每个小动物看作是多棵树的一个节点，那么要求的就是每一个节点的子树大小，DFS求解即可。

（这个题比较特殊，可以倒着遍历然后DP，原理相同）

Code

#include <bits/stdc++.h>
const int _______ = []() { std::ios::sync_with_stdio(false), std::cin.tie(nullptr); return 0; }();

void dfs(int u, const std::vector<std::vector<int>>& edg, std::vector<int>& siz) {
  siz[u] = 1;
  for (const int& v : edg[u]) {
    dfs(v, edg, siz);
    siz[u] += siz[v];
  }
}

int main() {
  int n; std::cin >> n;
  std::vector<int> fa(n);
  std::vector<std::vector<int>> edg(n);
  for (int i = 0; i < n; i++) {
    std::cin >> fa[i];
    fa[i]--;
    if (fa[i] != -1) {
      edg[fa[i]].push_back(i);
    }
  }
  std::vector<int> siz(n, 0);
  for (int i = 0; i < n; i++) {
    if (fa[i] == -1) {
      dfs(i, edg, siz);
    }
  }
  for (int i = 0; i < n; i++) {
    std::cout << siz[i] << "\n";
  }
}

9 - 删除字符

Description

删除字符

Solution

若一个字符串只能删除一个字符，要使得这个字符串字典序最小，则需要从左往右扫删除第一个字符比其右边的一个字符大的字符，若没有这种字符则删除最后一个字符。

那么删除多个字符的话一直做这个操作是最优的。（不会证明）

模拟一下这个过程即可。

Code

#include <bits/stdc++.h>
const int _______ = []() { std::ios::sync_with_stdio(false), std::cin.tie(nullptr); return 0; }();

int main() {
  int T; std::cin >> T;
  while (T--) {
    int n, m; std::cin >> n >> m;
    std::string s; std::cin >> s;
    std::string res;
    int cnt = 0;
    for (int i = 0; i < n; i++) {
      while (!res.empty() && res.back() > s[i] && cnt < m) {
        res.pop_back();
        cnt++;
      }
      res.push_back(s[i]);
    }
    while (cnt < m) {
      res.pop_back();
      cnt++;
    }
    std::cout << res << '\n';
  }
}

10 - 视力表

Description

视力表

Solution

中学数学题。

答案即。

用C++的话要使用逆元。（我选择Python）

Code

from math import comb
n, a, b, c, d = map(int, input().split())
print(comb(n * n, a) * comb(n * n - a, b) * comb(n * n - a - b, c) % 998244353)
2025最新求职资料大礼包领取
真题
历年笔试真题附答案
Momenta2019秋招技术岗笔试题
【2021】智加科技校招技术岗编程题汇总
酷家乐2020校园招聘-项目经理卷
全部 >
面经
面试常考问题整理
硬件/IC/嵌入式高薪--你应该看看这些公司和岗位
腾讯三面已上岸
23届联想面经分享： 秋招上岸
全部 >
内推
员工内推码获取
全部 >
大家都在关注
校招日程表 笔试日历 ai模拟面试 面试宝典 剑指offer 知识点专项练习

全部评论

(1) 回帖
加载中...
话题 回帖
博文推荐

相关热帖

近期热帖

近期精华帖

热门推荐

牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”