蚂蚁25年春招-工程研发-0309(实习)个人题解
题目:单选 + 不定项 + 2道 c++/java 单选 + 2道 c++/java 不定项 + 3 编程题
结果:比下午的阿里笔试简单很多,提前半小时 ak 出来了(下午阿里只做出 1 题)。
第一题:
按规则模拟即可,注意读入字符串有空格
#include <bits/stdc++.h> using namespace std; // 这样也行 // void up(char c){ // if(isupper(c)) cout << c; // else cout << (char)(c - 'a' + 'A'); // } int main() { int n; string s, t; cin >> n; getchar(); getline(cin, s); getline(cin, t); for(int i = 0;i < n;i++){ if(isupper(s[i])) toupper(t[i]); else if(islower(s[i])) tolower(t[i]); else if(isdigit(s[i])) cout << (int)(t[i]); else cout << "_"; } return 0; }
第二题:
深度优先搜索模拟即可
#include <bits/stdc++.h> using namespace std; struct node{ int x, y; }; const int N = 1e5 + 4; vector<int>v[N]; node idx[N]; int n, q; // flag = 0 左儿子,flag = 1 右儿子 void dfs(int now, int fa, int flag){ if(flag == 0) idx[now] = {idx[fa].x - 1, idx[fa].y - 1}; else idx[now] = {idx[fa].x + 1, idx[fa].y - 1}; flag = 0; for(auto nxt : v[now]){ if(nxt == fa) continue; dfs(nxt, now, flag); flag = 1; } } int main() { cin >> n >> q; int x, y; for(int i = 1;i < n;i++){ cin >> x >> y; v[x].push_back(y); v[y].push_back(x); } idx[1] = {0, 0}; dfs(v[1][0], 1, 0); if(v[1].size() > 1) dfs(v[1][1], 1, 1); while(q--){ cin >> x >> y; cout << abs(idx[x].x - idx[y].x) + abs(idx[x].y - idx[y].y) << endl; } return 0; }
第三题:
每个值单独计算对整体答案的贡献值,因为数值范围在 1e5 之内,可以将 1e5 这个区间分为 a[i] 2*a[i] 3*a[i] ...,然后统计各个区间的值的数量,计算贡献,在纸上模拟模拟可以做出来。
复杂度由调和级数保证,相同值要特殊处理下
#include <bits/stdc++.h> using namespace std; const int N = 1e5 + 3; int a[N], cnt[N]; using ll = long long; ll sum[N], ans; int main() { int n; cin >> n; int ma = 0; for(int i = 1;i <= n;i++) { cin >> a[i]; cnt[a[i]]++; ma = max(ma, a[i]); } sort(a + 1, a + 1 + n); for(int i = 1;i <= n;i++) sum[i] = sum[i - 1] + cnt[i]; for(int i = 1;i <= n;i++){ int now = a[i]; ll tot = sum[now] - sum[now - 1]; // 相同值数量 i += tot - 1; for(int j = 2; ;j++){ int range = now * j; // 统计 [range - now, range - 1] 范围内 a[j] 数量 // 对答案的贡献都是 j - 1,相同值一块处理,所以乘 tot ans += (j - 1) * (sum[min(range - 1, ma)] - sum[range - now - 1]) * tot; if(range > ma) break; } } cout << ans; return 0; }