美团笔试 美团实习 0401

笔试时间：2023年04月01日

第一题

题目：算数

小美在数学课上学会了加减乘除，现在她想多进行一些算数训练来加强自己的计算能力。为了不重复出题，她想出一个好方法。她先写下了一排n个数(n≥2)，依次用加号连接。举例来说，小美可能写下了如下的式子1+4+7+4+2+3+1共7个数以及6个加号。接着小美以一种全新的方式进行出题：她每次选择一个加号，将它改变成加减乘除中的一个（虽然很奇怪，但小美认为加号也可以被改成加号，尽管不会产生任何影响），然后计算整个式子的结果。值得注意的是，小美认为每次操作不对后续操作产生影响，详见样例解释。小美认真做了很多次算数训练，现在她想让作为她好朋友的你帮她用程序计算一次，方便她核对答案。

输入描述

第一行一个整数n，含义见题面。

接下来一行n个整数a1,a2,..,an，依次表示小美初始写下的连加算式中的每一个数。

接下来一个整数m，表示小美做了m次算数训练

接下来2m个以空格分开数字或符号 t1,o1, t2,o2, ... tm,om，其中ti为数字，oi是'+','-','*','/'(即加减乘除符号，不含引号)中的一个符号，表示第 i 次操作选定了第ti个加号，将其改变为了oi。

对于所有的的数据,2≤N≤50000，1≤M≤50000,1≤ai≤500,1≤ti<N,oi∈{+,-,*,/}

输出描述

输出一行m个整数，分别表示每次操作的答案，结果四舍五入到一位小数。

样例输入

5

1 2 4 2 5

3

1 - 2 * 4 /

样例输出

10.0 16.0 7.4

解释：

第一次操作后算数式为1-2+4+2+5 = 10.0

第二次操作后算数式为1+2*4+2+5 = 16.0

第三次操作后算数式为1+2+4+2/5 = 7.4

值得注意的是，每次操作都认为对初始的全加号式子(此处为1+2+4+2+5)进行操作，操作之间互不影响。

参考题解

按照题意模拟。

C++：[此代码未进行大量数据的测试，仅供参考]

#include <iostream>
#include <vector>
#include <iomanip>

using namespace std;

double perform_operation(int a, int b, char op) {
    switch (op) {
        case '+':
            return a + b;
        case '-':
            return a - b;
        case '*':
            return a * b;
        case '/':
            return static_cast<double>(a) / b;
        default:
            return 0;
    }
}

int main() {
    int n;
    cin >> n;
    vector<int> nums(n);
    for (int i = 0; i < n; ++i) {
        cin >> nums[i];
    }

    // 计算原始算式的结果
    int original_sum = 0;
    for (int i = 0; i < n; ++i) {
        original_sum += nums[i];
    }

    int m;
    cin >> m;
    vector<int> t(m);
    vector<char> op(m);
    for (int i = 0; i < m; ++i) {
        cin >> t[i] >> op[i];
    }

    cout << fixed << setprecision(1);
    for (int i = 0; i < m; ++i) {
        int index = t[i] - 1;
        char operation = op[i];
        double result = original_sum - nums[index] - nums[index + 1];
        result += perform_operation(nums[index], nums[index + 1], operation);
        cout << result << " ";
    }

    return 0;
}

Java：[此代码未进行大量数据的测试，仅供参考]

import java.util.Scanner;

public class Main {
    public static double performOperation(int a, int b, char op) {
        switch (op) {
            case '+':
                return a + b;
            case '-':
                return a - b;
            case '*':
                return a * b;
            case '/':
                return (double) a / b;
            default:
                return 0.0;
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] nums = new int[n];
        for (int i = 0; i < n; ++i) {
            nums[i] = scanner.nextInt();
        }

        // 计算原始算式的结果
        int originalSum = 0;
        for (int i = 0; i < n; ++i) {
            originalSum += nums[i];
        }

        int m = scanner.nextInt();
        int[] t = new int[m];
        char[] op = new char[m];
        for (int i = 0; i < m; ++i) {
            t[i] = scanner.nextInt();
            op[i] = scanner.next().charAt(0);
        }

        for (int i = 0; i < m; ++i) {
            int index = t[i] - 1;
            char operation = op[i];
            double result = originalSum - nums[index] - nums[index + 1];
            result += performOperation(nums[index], nums[index + 1], operation);
            System.out.printf("%.1f ", result);
        }
    }
}

Python：[此代码未进行大量数据的测试，仅供参考]

def perform_operation(a, b, op):
    if op == '+':
        return a + b
    elif op == '-':
        return a - b
    elif op == '*':
        return a * b
    elif op == '/':
        return float(a) / b
    else:
        return 0.0

def main():
    n = int(input())
    nums = list(map(int, input().split()))

    # 计算原始算式的结果
    original_sum = sum(nums)

    m = int(input())
    t = []
    op = []
    for _ in range(m):
        ti, opi = input().split()
        t.append(int(ti))
        op.append(opi)

    for i in range(m):
        index = t[i] - 1
        operation = op[i]
        result = original_sum - nums[index] - nums[index + 1]
        result += perform_operation(nums[index], nums[index + 1], operation)
        print("{:.1f}".format(result), end=" ")

if __name__ == "__main__":
    main()

第二题

题目：整理

小美正在整理桌子上的一排装饰品。小美对待装饰品摆放方式的审美角度很奇特，她认为高度相差比较大的装饰品放在相邻位置会很难看，她想对这一排装饰品进行整理，可以交换任意两个装饰品的位置任意多次。假设当前从左到右n个装饰品的高度分别为h1,h2,...,hn，那么当前一排装饰品的丑陋值为\sum_{i=1}^{n-1}{\left| h_{i} - h_{i+1} \right|}，其中|x|为x的绝对值。小美想最小化她的装饰品的丑陋值，请你帮她排一下顺序。形式化地来讲，有一长为n的序列a1,a2,...,an，你可以任意次数地进行交换，每次交换都可以选择任意两个不同的数i,j,交换ai,aj的位置。经过若干次交换后，序列变为h1,h2,...,hn，其丑陋值为\sum_{i=1}^{n-1}{\left| h_{i} - h_{i+1} \right|}，你需要找出一种交换方式，使得最终序列{hn}的丑陋值最小化。你不需要输出具体交换方式，只需要输出最终的{hn}序列的丑陋值即可。

输入描述

第一行一个整数n，表示小美的装饰品数量。

接下来一行n个整数a1,a2,...,an，依次表示从左到右n个装饰品的高度。

对于所有的数据:2≤N≤50000，0≤ai≤10^9。

输出描述

输出第一行一个数，为最优方案的最小丑陋值。

样例输入

3 3 1 2

样例输出

2

提示：

我们可以将3和1交换，得到1 3 2然后再将2和3交换，得到1 2 3可以证明，此时有最小丑陋值|1-2|+|2-3|=2

参考题解

C++：[此代码未进行大量数据的测试，仅供参考]

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> a(n);

    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }

    sort(a.begin(), a.end());

    int res = 0;
    for (int i = 0; i < n - 1; ++i) {
        res += a[i + 1] - a[i];
    }

    cout << res << endl;

    return 0;
}

Java：[此代码未进行大量数据的测试，仅供参考]

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] a = new int[n];

        for (int i = 0; i < n; ++i) {
            a[i] = scanner.nextInt();
        }

        Arrays.sort(a);

        int res = 0;
        for (int i = 0; i < n - 1; ++i) {
            res += a[i + 1] - a[i];
        }

        System.out.println(res);
    }
}

Python：[此代码未进行大量数据的测试，仅供参考]

n = int(input())
a = [int(c) for c in input().split(" ")]
a.sort()

res = 0
for i in range(n-1):
    res += a[i+1] - a[i]
print(res)

第三题

题目：收藏家

小美爱上了收藏！现在她给自己修建了一排n个收藏夹分别编号为1,2,3,...,n。有时小美会改变某一个收藏夹里的内容，例如从中拿入、拿出一些藏品，这样的操作会改变小美对这个收藏夹的欣赏程度，我们记编号为i的收藏夹小美对其的欣赏程度为ai。还有一些时候，小美会欣赏连续编号的一些收藏夹，例如编号为L,L+1,L+2,...,R-1,R的这一些收藏夹，她能从中获得的满足感为这些收藏夹的欣赏程度之和，即\sum_{i=L}^{R}{a_{i}},小美想在欣赏之前提前做一些评估，想知道如果她选择编号区间为[L,R]的收藏夹，能给她带来的满足感是多少。小美想请你，最好的朋友，来帮帮她。

输入描述

第一行两个整数n和m，表示小美的收藏夹数量和小美的操作数量。初始时刻收藏夹都是空的，也即ai=0(i∈[1,n])；

第二行m个整数op1,op2,...,opm；

第三行m个整数x1,x2,...,xm；

第四行m个整数y1,y2,...,ym，这些共同表示了m次操作。具体而言，对第i次操作，opi=0时表示为一次收藏夹更新操作，会将xi位置的收藏夹欣赏程度更新为yi，即axi=yi；opi=1时表示为一次查询操作，表示如果小美欣赏编号在区间[xi,yi]的收藏夹，能获得的满足感是多少，也即\sum_{j=x_{i}}^{y_{i}}{a_{j}}的值；

对于所有的数据，1≤n,m≤ 50000,opi∈{0,1},当opi=0 时,1≤xi≤n,0≤yi≤10000; 当opi=1 时，1≤xi≤yi≤n。保证至少有一次opi=1 的操作。

输出描述

对每个opi=1的操作，输出一个数表示对应答案。空格隔开所有答案。

样例输入

4 7

1 0 1 0 1 0 1

1 1 1 3 1 4 1

3 2 3 5 3 100 3

样例输出

0 2 7 7

参考题解

参考线性树做法。

Python：[此代码未进行大量数据的测试，仅供参考]

class Node:
    def __init__(self, left=None, right=None, left_child=None, right_child=None, value=None):
        self.left = left
        self.right = right
        self.left_child = left_child
        self.right_child = right_child
        self.value = value


class SegmentTree:
    def __init__(self, nums):
        n = len(nums)
        self.root = Node()
        self.nums = [0] + nums
        self.build_tree(self.root, 1, n)

    def build_tree(self, node, left, right):

        if left == right:
            node.value = self.nums[left]
            return
        mid = (left + right) // 2
        if node.left_child is None:
            node.left_child = Node()
        if node.right_child is None:
            node.right_child = Node()
        self.build_tree(node.left_child, left, mid)
        self.build_tree(node.right_child, mid + 1, right)
        node.value = node.left_child.value + node.right_child.value

    def update(self, node, left, right, index, value):
        node.value += value
        if left == right:
            return
        mid = (left + right) // 2
        if index <= mid:
            self.update(node.left_child, left, mid, index, value)
        else:
            self.update(node.right_child, mid + 1, right, index, value)

    def query(self, node, left, right, start, end):
        if left == start and end == right:
            return node.value
        mid = (left + right) // 2
        if end <= mid:
            return self.query(node.left_child, left, mid, start, end)
        elif start > mid:
            return self.query(node.right_child, mid + 1, right, start, end)
        left_part = self.query(node.left_child, left, mid, start, mid)
        right_part = self.query(node.right_child, mid + 1, right, mid + 1, end)
        return left_part + right_part


n, m = map(int, input().split())
ops = [int(c) for c in input().split()]
xs = [int(c) for c in input().split()]
ys = [int(c) for c in input().split()]

nums = [0 for _ in range(n)]
st = SegmentTree(nums)
for i in range(m):
    op, x, y = ops[i], xs[i], ys[i]
    if op == 0:
        delta = y - nums[x - 1]
        nums[x - 1] = y
        st.update(st.root, 1, len(nums), x, delta)
    else:
        print(st.query(st.root, 1, len(nums), x, y), end=" ")

第四题

题目：倒水魔法

小美最近在魔法课中掌握了倒水魔法：可以运用法力隔空倒水。最近魔法课考试临近，小美早早地来到了魔法训练室训练难以掌握的倒水魔法。魔法训练室里有n个神奇的杯子，有着不同的大小，假设第i个杯子已满，向其倒水，多余的水会正正好好流向第i+1个杯子（如果i=n时没有下一个杯子，不会有杯子接住此时多余的水而溢出到魔法训练室的水池）。这些杯子有着初始固定的水量，每次练习后杯子里的水都会还原到最初状态。每次练习时，魔法黑板会告诉小美需要将哪一个杯子倒满水。因为每个杯子的材质和形状有所不同，所以对其释放倒水魔法需要消耗的魔法值不同。小美想尽可能多练习，所以需要最小化每次消耗的魔法值的总量。

输入描述

第一行一个整数n，表示杯子数量；

第二行n个整数x1,x2,...,xn，依次表示第 i 个杯子能容纳水的量（单位为毫升）；

第三行n个整数y1,y2,...,yn，依次表示第 i 个杯子初始有的水量（单位为毫升）；

第四行n个整数z1,z2,...,zn，依次表示对第 i 个杯子每添加1毫升水需要消耗的法力值；

第五行一个整数m，表示练习的数量；

第六行m个整数q1,q2,...,qm，依次表示第i次练习时需要将第qi个杯子倒满。（每次练习过后，杯子里的水量都会还原为初始状态，不会影响到下一次练习）；

1≤n,m≤3000 , 1≤yi≤xi≤109, 1≤zi≤300,1≤qi≤n

输出描述

输出第一行m个数，依次表示每次训练时需要消耗的最小法力值。如果杯子初始本身就是满的，则需要消耗的法力值为0。

样例输入

3

1 2 3

1 1 2

1 2 5

2

3 1

样例输出

2 0

提示：

第一次训练，最优方案如下：

初始时杯子的水量和最大容量分别为： 1/1 1/2 2/3

1、给1号杯子（本身已满）倒水1毫升，消耗1点法力，水溢出转移到2号杯子，当前状态为： 1/1 2/2 2/3

2. 继续给1号杯子（本身已满）倒水1毫升，消耗1点法力，水溢出到2号杯子（也已满），继续溢出到3号杯子,此时3号杯子也被成功注满水，状态为：1/1 2/2 3/3。共消耗2点法力。可以证明没有更优方案。

第二次训练时，：

初始时杯子的水量和最大容量分别为（注意不同训练互不影响，因为训练结束后魔法会让水杯还原为初始状态）：1/1 1/2 2/3

可以发现1号杯子已满，不用注水，消耗法力为0。

参考题解

C++：[此代码未进行大量数据的测试，仅供参考]

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> xs(n), ys(n), zs(n);

    for (int i = 0; i < n; ++i) {
        cin >> xs[i];
    }

    for (int i = 0; i < n; ++i) {
        cin >> ys[i];
    }

    for (int i = 0; i < n; ++i) {
        cin >> zs[i];
    }

    int m;
    cin >> m;
    vector<int> qs(m);

    for (int i = 0; i < m; ++i) {
        cin >> qs[i];
    }

    vector<int> pres(n + 1, 0);
    for (int i = 1; i <= n; ++i) {
        pres[i] = pres[i - 1] + xs[i - 1] - ys[i - 1];
    }

    for (int i = 0; i < m; ++i) {
        int q = qs[i];
        int cur = INT_MAX;
        for (int j = 0; j < q; ++j) {
            cur = min(cur, (pres[q] - pres[j]) * zs[j]);
        }
        cout << cur << " ";
    }

    cout << endl;

    return 0;
}

Java：[此代码未进行大量数据的测试，仅供参考]

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] xs = new int[n];
        int[] ys = new int[n];
        int[] zs = new int[n];

        for (int i = 0; i < n; ++i) {
            xs[i] = scanner.nextInt();
        }

        for (int i = 0; i < n; ++i) {
            ys[i] = scanner.nextInt();
        }

        for (int i = 0; i < n; ++i) {
            zs[i] = scanner.nextInt();
        }

        int m = scanner.nextInt();
        int[] qs = new int[m];

        for (int i = 0; i < m; ++i) {
            qs[i] = scanner.nextInt();
        }

        int[] pres = new int[n + 1];
        for (int i = 1; i <= n; ++i) {
            pres[i] = pres[i - 1] + xs[i - 1] - ys[i - 1];
        }

        for (int i = 0; i < m; ++i) {
            int q = qs[i];
            int cur = Integer.MAX_VALUE;
            for (int j = 0; j < q; ++j) {
                cur = Math.min(cur, (pres[q] - pres[j]) * zs[j]);
            }
            System.out.print(cur + " ");
        }

        System.out.println();
    }
}

Python：[此代码未进行大量数据的测试，仅供参考]

n = int(input())
xs = [int(c) for c in input().split(" ")]
ys = [int(c) for c in input().split(" ")]
zs = [int(c) for c in input().split(" ")]

m = int(input())
qs = [int(c) for c in input().split(" ")]
pres = [0 for _ in range(n + 1)]
for i in range(1,n+1):
    pres[i] += pres[i-1] + xs[i-1] - ys[i-1]
for i in range(m):
    q = qs[i]
    cur = float('inf')
    for j in range(q):
        cur = min(cur, (pres[q] - pres[j]) * zs[j])
    print(cur, end= " ")

第五题

题目：价值

你现在有一棵树，树上的每个节点都有自己的价值。价值的计算规则如下所示：

1、若某节点N没有儿子节点，那么节点N价值为1；

2、若某节点N有两个儿子节点，那么节点N价值为两个儿子节点的价值之和，或者价值之按位异或。这取决于节点N的颜色，若N的颜色为红色，那么节点N价值为两个儿子节点的价值之和；若N的颜色为绿色，那么节点N价值为两个儿子节点的价值之按位异或。保证这棵树要么没有儿子节点，要么有两个儿子节点。注：树，是一种无向无环联通图。

按位运算就是基于整数的二进制表示进行的运算。按位异或用符号⊕表示，两个对应位不同时为1，否则为0。

如：

5=(101)2

6=(110)2

5⊕6=3，即 (101)2 ⊕ (110)2 = (011)2

输入描述

第一行一个正整数n表示节点个数。

第二行n-1个正整数p[i](2≤i≤n)表示第 i 个节点的父亲。1号节点是根节点。

第三行n个整数c[i](1≤i≤n)，当c[i] = 1时表示第 i 个节点是红色，c[i] = 2则表示绿色。

数据保证形成合法的树。

对于所有的数据，n≤50000

输出描述

输出一行一个整数表示根节点的值。

样例输入

3

1 1

2 2 2

样例输出

0

参考题解

Python：[此代码未进行大量数据的测试，仅供参考]

n = int(input())
parent_nodes = [int(c) for c in input().split()]
colors = [int(c) for c in input().split()]

class TreeNode:
    def __init__(self, color=0):
        self.color = color
        self.children = []

tree_nodes = [TreeNode() for i in range(n)]

for i in range(n):
    tree_nodes[i].color = colors[i]

for i in range(n - 1):
    tree_nodes[parent_nodes[i] - 1].children.append(tree_nodes[i + 1])

def dfs(node):
    if not node.children:
        return 1
    values = []
    for child in node.children:
        values.append(dfs(child))
    if node.color == 1:
        return sum(values)
    current = 0
    for value in values:
        current ^= value
    return current

print(dfs(tree_nodes[0]))

#美团笔试##美团实习#
全部评论
Mark
点赞 回复 分享
发布于 2024-03-25 23:51 江苏
Mark
点赞 回复 分享
发布于 2024-03-25 23:38 江苏
Mark
点赞 回复 分享
发布于 2024-03-25 23:26 江苏
Mark
点赞 回复 分享
发布于 2024-03-25 23:16 江苏
Mark
点赞 回复 分享
发布于 2024-03-25 23:01 江苏
Mark
点赞 回复 分享
发布于 2024-03-25 22:49 江苏
Mark
点赞 回复 分享
发布于 2024-03-25 22:42 江苏
Mark
点赞 回复 分享
发布于 2024-03-25 22:25 江苏
Mark
点赞 回复 分享
发布于 2024-03-25 21:55 江苏
mark
点赞 回复 分享
发布于 2024-03-25 21:43 江苏

相关推荐

07-16 20:44
苏州大学 集成电路IC设计
点赞 评论 收藏
分享
06-09 23:07
已编辑
湖北工程学院新技术学院 运营
点赞 评论 收藏
分享
06-16 09:09
山东工程职业技术大学 运营
点赞 评论 收藏
分享
昨天 10:33
门头沟学院 客户端其它
点赞 评论 收藏
分享
评论
12
12
分享

招聘动态

查看更多

滴滴

2026届秋季校招提前批

Touch CIB

数字兴业科技挑战赛

26届投递链接合集

快手

快Star-X特别技术人才计划启动

地平线

2026届校园招聘

现代汽车前瞻技术研发中心

DJI 大疆

全站热榜

更多

创作者周榜

更多
正在热议
更多
# 26届的你们有几段实习？ #
20264次浏览 276人参与
# 你小时候最想从事什么职业 #
102798次浏览 1771人参与
# 你被哪些公司秒挂过？ #
18953次浏览 185人参与
# 网申一定要掌握的小技巧 #
9704次浏览 65人参与
# 如何提高实习转正率？ #
7673次浏览 135人参与
# 新凯来求职进展汇总 #
41073次浏览 108人参与
# 你认为哪些项目算烂大街？ #
8526次浏览 196人参与
# 机械校招之路总结 #
92465次浏览 1889人参与
# 你后悔自己读研吗？ #
9173次浏览 176人参与
# 你以为的实习VS真实的实习 #
11838次浏览 133人参与
# 月薪多少能在一线城市生存 #
10981次浏览 172人参与
# 腾讯工作体验 #
480022次浏览 3498人参与
# 找工作时的取与舍 #
81356次浏览 578人参与
# 最难的技术面是哪家公司？ #
6088次浏览 58人参与
# 秋招拿一个offer可以躺平吗 #
145011次浏览 928人参与
# 安利/避雷我的专业 #
77792次浏览 526人参与
# 面试等了一周没回复，还有戏吗 #
137214次浏览 1229人参与
# 你想留在一线还是回老家？ #
50112次浏览 513人参与
# 选择和努力，哪个更重要？ #
86070次浏览 745人参与
# 当下环境，你会继续卷互联网，还是看其他行业机会 #
115004次浏览 799人参与
牛客网
牛客网在线编程
牛客网题解
牛客企业服务