蚂蚁 - 实习 - 笔试

一、基础题7 道多选 + 4 道单选涉及内容：设计模式，计算机网络，操作系统，数据结构，KMP，排序算法二、Java基础2 道单选 + 2 道多选涉及内容：基础知识，代码结果，==，Arrays.equals ，Arrays.hashcode三、编程题三道（任选语言）A了前两道，一次过（模拟、树上曼哈顿距离），第三道（数组求和）暴力解法得20%手贱先点编程题，不提交不让退出！！！选择题还没做，不敢投入全部时间去做编程压轴题！

蚂蚁春招一共三道算法，很菜，只做出第一道最简单的第一题忘记了第二题是一个二叉树的题目，感觉是很简单的，但人太菜，没办法，复习一下二叉树题目大概如下：输入如下： 5 2 # 5个节点，问询 2次 1 2 # 节点1增加子节点 2 1 3 # 节点1增加子节点 3 2 4 2 5 3 6 # 第一次问询，节点3与节点6的距离是多少 1 5 # 第二次问询，节点1与节点5的距离是多少 第三题：给出一个数组an = [a1, a2, ..., an] 题目要求直接写的话是这样：但肯定需要优化一下算法才行 an = [1,2,5,6,2,1,5,2222,11111,2222， ...] su...

1，模拟一下就好，别忘了处理换行和回车，代码略。2，bfs一下，找出每个点的坐标，o1输出就可以了。void bfs(int u) {    queue q;    q.push(u);    pos[u] = {0, 0};    mark[u] = 1;    while (q.size() > 0) {        int v = q.front();        q.pop();        int l = - 1, r = -1;        for (auto x : g[v]) {            if (mark[x]) continue;            mark[x] = 1;            q.push(x);            if (l == -1) l = x;            else {                r = x;                if (l > r) swap(l, r);             }        }        if (l != -1) {            pos[l] = pair(pos[v].x - 1, pos[v].y - 1);        }        if (r != -1) {            pos[r] = pair(pos[v].x + 1, pos[v].y - 1);        }    } }3，可以发现，我们要计算的是每个数整除其他数之后的和。其实可以反过来想，我们要计算每个数作为除数，其他数除他之后的和。对于数i来说，[j * i, j * i + i - 1]这个范围内的数除以i等于j，那我们可以枚举每个i和每个j，维护一个前缀和来快速算出[j * i, j * i + i - 1]这个范围内的贡献，贡献数是i的数量 * 范围内数的个数 * j。时间复杂度是n + n/2 + n /3 +... = nlogn代码如下，cnt[i]是数字i的数量，sum[i]是前cnt[i]的前缀和，N是数的最大范围1e5;    for (int i = 1; i < N; i ++) {        if (cnt[i] == 0) continue;        for (int j = 1; j * i < N; j ++) {            res += 1ll * (sum[min(i * j + i - 1, N - 1)] - sum[i * j - 1]) * cnt[i] * j;        }    }#笔试# #蚂蚁# #蚂蚁笔试#

读两个带空格的字符串按要求模拟：直接按题意模拟即可，太久没写带空格的字符串读入，cin.getline嗯调半天； 给一个二叉树，每个节点定义一个坐标值，子节点的坐标可以根据父节点的坐标算出来，每次询问一对节点的曼哈顿距离：dfs一遍后直接输出即可； 给一个数组，求：考虑的贡献，枚举，计算到里有多少个满足条件的数即可，。