蚂蚁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;
}

全部评论
深圳字节部门直招,会快速安排面试,简历快快来~可以看我主页
点赞 回复 分享
发布于 03-11 20:23 广东
听说第二题后面有玄学事件发生?有大佬知道啥情况吗,我看到有人重测后 85->100,还有100->85的
点赞 回复 分享
发布于 03-09 21:09 北京

相关推荐

玉无心❤️:发照片干啥 发简历啊
点赞 评论 收藏
分享
点赞 评论 收藏
分享
评论
3
4
分享

创作者周榜

更多
牛客网
牛客企业服务