2024秋招美团笔试题目记录(2023.8.12, 2023.8.19)

8.12

第一题

题目描述：

给定一个排列\(A = [a_1, a_2, ..., a_n]\)，数字不重复。给定两个数x, y, 判断x, y 在A中是否相邻，输出yes or no.

例子： 输入第一行是A的长度，第二行A，第三行x y

Input:

4
1 3 2 4
1 2

Output:

No

第二题

Leetcode 1184. 公交站间的距离

第三题

题目描述：

给一个矩阵\(A_{mxn}\)，代表一块蛋糕，每个位置的值\(A_{i,j}\)代表这部分蛋糕的美味度，横着或竖着切一刀，使得两部分蛋糕美味度之差尽可能小。输出最小的差。

例子： 输入第一行是m，n，第二行开始是A

Input:

2 3
1 3 2 
1 2 5

Output:

0

第四题

题目描述： 给定一棵树，开始时所有节点为白色。如果两个相连的节点的值相乘是完全平方数，且它们都是白色，可以将这两个节点染成红色。输出最多能染色几个节点。

例子： 输入第一行是节点数n，第二行是各个节点的值，接下来n-1行是节点的边

Input:

3
3 3 12 
1 2
2 3

Output:

2

My answer:

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

bool issquare(int n)
{
    int x = int(sqrt(n));
    if(x * x == n)return true;
    else return false;
}

class Solution
{
    public:
        Solution(int n)
        {
            vector<int> tmp;
            edge.resize(n, tmp);
            match.resize(n, -1);
            num = n;
        }

        void add_edge(int i, int j)
        {
            edge[i].push_back(j);
            edge[j].push_back(i);
        }
    
    int search_max()
    {
        int sum = 0;
        for (int i = 0; i < num; i++)
        {
            if (match[i] != -1)
                continue;
            for (int j:edge[i])
            {
                if (match[j] == -1 || search(match[j]))
                {
                    match[i] = j;
                    match[j] = i;
                    sum++;
                    break;
                }
            }
        }
        return sum;
    }

    bool search(int i)
    {
        for (int j : edge[i])
        {
            if(j == match[i])
                continue;
            if(match[j] == -1 || search(match[j]))
            {
                match[i] = j;
                match[j] = i;
                return true;
            }
        }
        return false;
    }
    
    private:
        int num;
        vector<vector<int>> edge;
        vector<int> match;
};

int main() {
    int n;
    while (cin >> n) { // 注意 while 处理多个 case
        Solution s(n);
        vector<int> value(n);
        for (int i = 0; i < n; i++)
        {
            cin >> value[i];
        }
        for (int i = 0; i < n - 1; i++)
        {
            int x, y;
            cin >> x >> y;
            if(issquare(value[x-1] * value[y-1])){
                s.add_edge(x - 1, y - 1);
            }
        }        
        cout << s.search_max() * 2 << endl;
    }
}

8.19

第一题

题目描述：

给定一个整数x，一个上限m，当x超过上限m时从1开始重新计数（就是取余）

例子：

输入第一个数x，第二个m

Input:

3 2
2 2
4 6
5 3

Output:

1
2
4
2

第二题

输入一个整数数组\(\{a_i\}\)，总和\(sum=a_1 + a_2 + ... + a_n\)，可以将其中一个加号换成乘号，也可以不换。求可能的sum的最大值

例子：

第一行是数组个数

第二行是数组元素

Input:

5
1 2 4 5 1

Output:

24

1 + 2 + 4 * 5 + 1 = 24

可以枚举乘号的位置，只需要注意\(a_i\)变量类型设为long long int

第三题

题目描述：

对于一个只含0，1的字符串，对其某一位取反定义为操作一次，对一个字符串操作最少次数使其相邻两位不同，这个最少次数为字符串的权值。现给定一个字符串，求其所有字符串的权值之和。

例子：

Input:

10001

Output:

8

长度为2的子串：两个00，每个权重为1 长度为3的子串：3个子串，每个权重为1 长度为4的子串：2个子串，每个权重为1 长度为5的子串：1个，权重为1 总共 2 + 3 + 2 + 1 = 8

My answer: 假设对长度为len,结束位置为i的子字符串，使其变为相邻两位不同且最后一位为0的最小变换次数为\(a_0[len][i]\),最后一位为1的最小变换次数为\(a_1[len][i]\)。则递推公式为

若s[i] = 0：

\[a_0[len][i] = min(a_1[len - 1][i-1], len - 1)\] \[a_1[len][i] = min(a_0[len - 1][i-1], len)\]

s[i] = 1同理

int main() {
    string s;
    while (cin >> s) { // 注意 while 处理多个 case
        int n = s.size();
        vector<int> a0(n, 0), a0_tmp(n, 0);
        vector<int> a1(n, 0), a1_tmp(n, 0);
        for (int i = 0; i < n - 1; i++)
        {
            if(s[i] == '0')
                a1[i] = 1;
            else
                a0[i] = 1;
        }
        int sum = 0;
        for (int l = 2; l <= n; l++)
        {
            for (int i = l - 1; i < n; i++)
            {
                if(s[i] == '0')
                {
                    a0_tmp[i] = min(a1[i-1], l - 1);
                    a1_tmp[i] = min(a0[i-1] + 1, l);
                }
                else
                {
                    a1_tmp[i] = min(a0[i-1], l - 1);
                    a0_tmp[i] = min(a1[i-1] + 1, l);
                }
                sum += min(a0_tmp[i],a1_tmp[i]);
            }
            a0.swap(a0_tmp);
            a1.swap(a1_tmp);
        }
        cout << sum << endl;
    }
}

第四题

题目描述： 给定n个正数，一次操作可以对一个数加1，一个数减1. 问使其众数出现次数最多的最少操作数。

例子：

第一行是n

第二行是n个数

Input:

3
1 4 4 
3
1 5 5

Output:

2
0

这题没做出来，只想到

• 如果\(a_i\)的总和sum能整除n，那最小次数就是 \(\frac{1}{2}\sum \|a_i - \frac{sum}{n}\|\)

• 如果不整除，众数个数已等于n-1，答案就是0

• 其他情况： n个数，将其中n-1个变为值v，要次数最少那剩余的一个一定是最大值或最小值。应该要枚举v的可能取值？