蚂蚁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] ...，然后统计各个区间的值的数量，计算贡献，在纸上模拟模拟可以做出来。

复杂度由调和级数保证，相同值要特殊处理下

图来源 https://www.cnblogs.com/lrj124/p/15058439.html

#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;
}