【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)#学习路径##C/C++#
