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 北京

Sunyu丶

04-03 17:09

已编辑

哈尔滨理工大学自动化类

金山办公算法岗一二面面经

base 武汉时间线：3.14一面，3.26二面，发发面经攒人品，许愿hr面一面(30 min)：八股大考察+一个项目细节Python的引用计数Python的修饰器深拷贝和浅拷贝Python的多线程为什么Python没有真正意义上的多线程产生梯度消失和梯度爆炸的原因bn的原理lstm与rnn的区别lstm三种门的实现方式casade-rcnn的原理(项目中提到)非极大抑制的流程双边滤波的实现方式canny边缘检测的步骤霍夫直线检测的原理c++中内存泄露的原因，怎么解决c++中有哪些内存分配方式svm有哪些核函数svm的工作原理bagging和boosting有什么区别二面(40 min...

点赞评论收藏

03-28 20:50

很怪的一套题，单选有很多行测。编程*3：1、树上上升序列 https://blog.csdn.net/sunqjao/article/details/1294455842、扑克牌从一副扑克牌里拿出来一叠，其中包括A,2,3,...,10（一共10种牌）打牌方式：单牌、对子、顺子（连着5张）、连对（数字连续的三个对子，如334455）输入：每张牌的个数输出：最少多少次打光所有牌3、二元组个数（核心代码模式）长为n的数组array，整数k问有多少个二元组满足i<j && array[i]+array[j]≤k

投递金山WPS等公司8个岗位

点赞评论收藏

中门对狙

04-03 17:32

蚌埠坦克学院电子信息类

面试贴——金山二面C++

1.两道C程序，判断输出以及推导过程2.多态（每次面试都问，已经倒背如流）3.QT信号与槽4.用过哪些组件5.QT对象管理机制6.内存分区7.进程通信方式8.线程与进程9.项目拷打40min

点赞评论收藏

04-08 18:14

如题，今天收到的hr面（其实4月2号就收到了，但当时在面试，之后联系，这个之后就到现在了，离谱），但要半个小时，就推到明天了（明天要提交论文盲审，今天还在改）。想问大家hr面是问什么啊，半个小时也太长了吧。

点赞评论收藏

03-21 21:50

单选多选一共40分，没啥好说多，编程题一共三道：1.kanan和高音，后一个音比前一个音高度差大于8的时候就唱不上去了，给定一个音高数组，求最多能唱多长一段的音。这个用双指针过了。2.字符串替换，给定两个字符串，把第一个字符串里的"%s"按顺序替换成第二个字符串里的字符，没用到的字符补到第一个字符串后面。模拟一下就过了3.游游的水果大礼包，有n个苹果，m个桃子，可以把两个苹果和一个桃子组成价值为a的1号礼包，一个苹果两个桃子组成价值为b的2号礼包，问最多能组成总和多少的大礼包。用dp做的，定义dp[i][j]表示从前i个1号礼包，j个2号礼包里选组成大礼包价值最大，转移方程设的是dp[i][j]=max(dp[i-1][j]+a,dp[i][j-1]+b)，但是样例只过了70%就爆内存了，可能是要优化成一维dp才行，后面还有恒生的笔试，就直接交了没再继续。希望金山能给个面试机会。

投递金山WPS等公司8个岗位

点赞评论收藏

5 9 评论

招聘动态

小红书

24届春招&25届实习生招聘

博乐游戏

24届春招&25届实习生招聘

24届春招硬件高薪职位集合

阅文集团2024春季校招

全站热榜

正在热议

【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星）题解