阿里8.19笔试
ak了,但是因为代码不能用本地IDE,所以没有AC的代码,赛后凭记忆写了一个,只展示思路,不保证交了能AC。
第一题
给你n个数,你现在可以选两个数,把他们变成他们的平均值,问是否能让这些所有数的乘积变成偶数
找规律,显然有偶数肯定可以,然后就是mod 4等于1和3都出现就行。
#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(0); int n; cin >> n; bool flag = false; int tmp[4] = {0}; for (int i = 0; i < n; i++) { int x; cin >> x; if (x % 2 == 0) flag = true; else tmp[x % 4]++; } if (!flag) flag = (tmp[1] && tmp[3]); puts(flag ? "Yes" : "No"); return 0; }
第二题
两个数组a和b,都是无重复元素,现在你可以把b里的元素,按照任意顺序放在a的开头或者结尾,问最大值的下标和最小值的下标差的绝对值最大是多少
暴力,显然只和b数组的最大最小值位置有关,把所有情况枚举出来就行了。
#include <bits/stdc++.h> #include <algorithm> using namespace std; #define all(x) x.begin(), x.end() int cal(vector<int> v) { return abs(max_element(all(v)) - min_element(all(v))); } vector<int> operator+(vector<int> a, vector<int> b) { a.insert(a.end(), all(b)); return a; } int main() { int n, m; cin >> n >> m; vector<int> a(n); vector<int> b(m); for (auto &x : a) cin >> x; for (auto &x : b) cin >> x; sort(all(b)); auto rb = b; reverse(all(rb)); int ans = 0; for (auto &t : {b, rb}) { ans = max(ans, cal(a + b)); ans = max(ans, cal(b + a)); ans = max(ans, cal(vector<int>{t[0]} + a + vector<int>(t.begin() + 1, t.end()))); ans = max(ans, cal(vector<int>{t.back()} + a + vector<int>(t.begin(), --t.end()))); ans = max(ans, cal(vector<int>(t.begin(), --t.end()) + a + vector<int>{t.back()})); ans = max(ans, cal(vector<int>(t.begin() + 1, t.end()) + a + vector<int>{t[0]})); } cout << ans; return 0; }
第三题
有n个点,每个时间每个点分别向上下左右扩展出4个点,原来的点不变,问多久才能所有点构成一个联通块
二分答案,然后每次check的时候两两判断两个矩形是否相交。因为不会计算几何,也没有线段交的板子,所以猜了个结论,感觉是他们曼哈顿距离小于等于时间的两倍,懒得证明,反正我过了。
#include <bits/stdc++.h> using namespace std; using point = array<int, 2>; class dsu { public: vector<int> fa; dsu(int n) { fa.resize(n); iota(fa.begin(), fa.end(), 0); } int find(int x) { return fa[x] == x ? x : (fa[x] = find(fa[x])); } void join(int a, int b) { fa[find(a)] = find(b); } int count() { set<int> se; for (int i = 0; i < fa.size(); i++) se.insert(find(i)); return se.size(); } }; int main() { int n; cin >> n; vector<point> v(n); for (auto &x : v) cin >> x[0] >> x[1]; int l = 0, r = 1e9; auto meet = [&](int i, int j, int t) { return abs(v[i][0] - v[j][0]) + abs(v[i][1] - v[j][1]) <= 2 * t; }; auto check = [&](int t) { dsu d(n); for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { if (meet(i, j, t)) d.join(i, j); } } return d.count() == 1; }; while (l < r) { if (l + 1 == r) { if (check(l)) r--; else l++; break; } int mid = (l + r) / 2; if (check(mid)) r = mid; else l = mid; } cout << l; return 0; }#阿里巴巴信息集散地#