2021-06-03 19:51 没上过大学 C++

关注

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

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

非官方

1 - 完美对

Description

完美对

Solution

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

$\begin{align}a_{i,1}-a_{i,2}&=-(a_{j,1}-a_{j,2})\\a_{i,1}-a_{i,3}&=-(a_{j,1}-a_{j,3})\\a_{i,1}-a_{i,4}&=-(a_{j,1}-a_{j,4})\\\cdots\\a_{i,1}-a_{i,k}&=-(a_{j,1}-a_{j,k})\end{align}$

令 $b_{i,j}=a_{i,j}-a_{i,1}$ ，那么当且仅当 $b_{i}$ 与 $b_j$ 每个位置都是相反数时，物品 ${i}$ 和 ${j}$ 为完美对。

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

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

而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个人以上，那么有两种比较优的情况送最重的两个人到对岸而且要用到两个最轻的人做工具人。

如果这四个人的体重由小到大排序为 ${a}$ 、 ${b}$ 、 ${c}$ 、 ${d}$ 。

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

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

一直采用这两种方式的代价最小的方式，知道人数少于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

首先给 $\frac{a}{b}$ 通分成最简分式。

然后选 $[1,A]$ 之间最大的 $a$ 的倍数 $x$ ，然后用 $x$ 求出 $y$ ，即在 $x$ 是最大的情况下 $y$ 所能的最大值。

若 $y$ 的值超出 $[1,B]$ 的范围，则用同样的方法先算出 $y$ ，然后再求出 $x$ ，显然这样 $x$ 不会超出范围。

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

若水渠为 $x=z$ ，距离和即 $\sum\limits_{i=1}^{n}|z-x_i|$ 。

对于 $y=|z-x|$ 而言，若将 $z$ 作为横坐标轴， $y$ 作为纵坐标轴，则这个函数是一个先减后增的函数。

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

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

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

#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

若排序后的序列为 $b$ ，则差异和为 $\sum\limits_{i=0}^{n-1}|a_i-a_{(i+1)\%n}|$ 。

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

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

当 $n$ 是偶数的情况下，可以有 $\frac{n}{2}$ 个数进行两次加，另外 $\frac{n}{2}$ 个数进行两次减。

当 $n$ 是奇数的情况下，可以有 $\lfloor\frac{n}{2}\rfloor$ 个数进行两次加，还有 $\lfloor\frac{n}{2}\rfloor$ 个数进行两次减，还有一个数进行一次加一次减。

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

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

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

那么 $dp[i][j]$ 表示已经选了 $i$ 个数第 $i$ 个数选的是第 $j$ 个数的 $\sum\limits_{k=1}^{i-1}|b_k-b_{k+1}|$ 最小值。

转移方程： $dp[i][j]=\min\limits_{k=1}^{3}(dp[i-1][k]+|a_{k,i-1}-a_{j,i}|)$ 。

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_{n\cdot n}^{a}\cdot C_{n\cdot n-a}^{b}\cdot C_{n\cdot n-a-b}^{c}$ 。

用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)

#学习路径##C/C++#

全部评论

推荐最新楼层

不戴眼镜的兔子1999

中国人民大学 C++

牛

点赞回复分享

发布于 03-17 11:39 北京

11-05 22:32

大连理工大学嵌入式软件开发

Lexar感谢信

我来参加一下晒感谢信的活动。存储巨头。被江波龙收购，toc品牌名是lexar。因为有外资成分，所以比较wlb。第三轮技术面的面试官是校友，但是还是被刷了。

你都收到了哪些公司的感谢信？

点赞评论收藏

10-25 17:38

点赞评论收藏

11-01 14:35

重庆邮电大学 C++

荣耀软测统计

投票

荣耀软测统计，特别是重邮的有开奖了麻烦说一下，这对我很重要！

点赞评论收藏

10-30 11:51

门头沟学院机械设计/制造

Lexar 机械工程师二面

一对一：部门负责人40min实习主要做了什么工作跌落测试，需要做多少次，每次有什么要求？钣金不同改进方案有什么差异么，和仿真对应起来？面板材料？温升实验怎么做？参与视觉方案的设计和选型，具体怎么做的？装置迭代升级了那些？观测效率提高了多少？怎么定位噪声是空气传播噪声？动刚度问题如何发现？使用的什么材料？阻燃标准是多少？仿真分析是做了什么？仿真结果和实验误差怎么样？仿真的网格划分使用了什么软件？#机械制造笔面经#

查看13道真题和解析机械制造笔面经

点赞评论收藏

11-07 12:07

已编辑

淘天集团_后端开发

麦当劳openday

现场有免费麦当劳吃吗，刚好准备去南京玩，听说去南京面试南京还有政策可以报销😋😋

点赞评论收藏

6 9 评论

招聘动态

杉川机器人

2025校园招聘

字节跳动

2025校园招聘

字节跳动Data

2025校园招聘

快手Star

2025届招聘

快手

销售类投递专区

库洛游戏

全站热榜

正在热议

# 选完offer后，你后悔学本专业吗 #

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

1 - 完美对

Description

Solution

Code

2 - 选择物品

Description

Solution

Code

3 - 小强去春游

Description

Solution

Code

4 - 比例问题

Description

Solution

Code

5 - 小强修水渠

Description

Solution

6 - 国际交流会

Description

Solution

Code

7 - 小强的神奇矩阵

Description

Solution

Code

8 - 蚂蚁森林之王

Description

Solution

Code

9 - 删除字符

Description

Solution

Code

10 - 视力表

Description

Solution

Code

全站热榜

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