美团8.12笔试 后端开发

第一题：排列判断是否相邻

有一个排列，一共有n个数，还有两个数x和y，请你判断x和y在排列中是否相邻，是则输出”Yes”，不是则输出”No”

1 ≤ n ≤ 1e5

输入n,x,y

注意判断x的前后有没有y即可；

第二题：环形公路最短距离

现有一条环形公路，总共有n个站点，a[i]代表第i个站点与第i+1个站点之间的距离，特殊的，a[n]表示第n个站点与第一个站点之间的距离。出发地为x，目的地为y，请你求出x到y的最短距离

1 ≤ n ≤ 1e5

1 ≤ a[i] ≤ 1e9

注意a[i]要用long int，判断正着走与反着走哪个小输出哪个

第三题：切蛋糕

现有一个n*m的蛋糕矩阵a，a[i][j]代表一小块蛋糕的美味度，现在小美要和一个好朋友分享蛋糕，因此需要把这个蛋糕矩阵切成两半，并且要求分成两半后的两块蛋糕的美味度尽可能相等，即求出分成两半后的两块蛋糕的abs(s1 - s2)的最小值，s1代表第一块蛋糕的美味度，s2代表第二块蛋糕的美味度。要求：必须保证每一小块蛋糕的完整性（即不能斜着切，如果把整个大蛋糕正着放）

1 ≤ n , m≤ 1e3

1 ≤ a[i][j] ≤ 1e5

因为只能横切或者竖切，那每次输入数组的时候保存下来每一行 以及 每一列的美味度之和，再遍历每次切的abs最小值判断即可。

#include <iostream>
#include <vector>
#include <limits.h>
using namespace std;
int main(){
    int n, m, temp;
    cin>>n>>m;
    vector<int> row(n,0);
    vector<int> col(m,0);
    int sum_all = 0;
    for(int i = 0; i < n; i++){
        int sum = 0;
        for(int j = 0; j < m; j++){
            cin>>temp;
            sum += temp;
            col[j] += temp;
            sum_all += temp;
        }
        row[i] = sum;
    }
    int half_row = 0, half_col = 0;
    int min_row = INT_MAX, min_col = INT_MAX;
    for(int i=0; i<n; i++){
        half_row +=row[i];
        int minus_row = abs(sum_all - 2*half_row);
        min_row = min(min_row,minus_row);
    }
    for(int i=0; i<m; i++){
        half_col += col[i];
        int minus_col = abs(sum_all - 2*half_col);
        min_col = min(min_col,minus_col);
    }
    int res = min(min_col,min_row);
    cout<<res<<endl;
    return 0;
}

第四题：字符串平铺成矩阵

一个长为n的字符串s，将其重组为一个二维矩阵，二维数组长宽x,y，那么x*y = n。

矩阵的权重定义为矩阵连通块的数量。定义上下左右四个方向相邻相同字符是连通的，希望矩阵的权重最小，求最小权重值。

比如 abcbbcbcc，可建立矩阵3*3 abc,bbc,bcc，此时权重为3。

可以遍历出所有x,y的组合，并对每一组x,y分别进行dfs，来计算矩阵的权重

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
void dfs(const string& s, int width, int height, int row, int col, vector<vector<bool>>& visited) {
    if (row < 0 || row >= height || col < 0 || col >= width || visited[row][col]) {
        return;
    }
    visited[row][col] = true;
    char currentChar = s[row * width + col];

    if (row > 0 && s[(row - 1) * width + col] == currentChar) {
        dfs(s, width, height, row - 1, col, visited);
    }
    if (row < height - 1 && s[(row + 1) * width + col] == currentChar) {
        dfs(s, width, height, row + 1, col, visited);
    }
    if (col > 0 && s[row * width + col - 1] == currentChar) {
        dfs(s, width, height, row, col - 1, visited);
    }
    if (col < width - 1 && s[row * width + col + 1] == currentChar) {
        dfs(s, width, height, row, col + 1, visited);
    }
}

int computeWeight(const string& s, int width, int height) {
    int weight = 0;
    vector<vector<bool>> visited(height, vector<bool>(width, false));

    for (int i = 0; i < height; ++i) {
        for (int j = 0; j < width; ++j) {
            if (!visited[i][j]) {
                dfs(s, width, height, i, j, visited);
                weight++;
            }
        }
    }
    return weight;
}

int minWeight(string s, int n) {
        int minWeight = INT_MAX;
        // 遍历不同的宽高组合
        for (int width = 1; width <= n; ++width) {
            for (int height = 1; height <= n; ++height) {
                if (width * height == n) {
                    int weight = computeWeight(s, width, height);
                    minWeight = min(minWeight, weight);
                }
            }
        }
        return minWeight;
    }

int main() {
    int n;
    string s;
    cin>>n;
    cin>>s;
    int result = minWeight(s, n);
    cout << "Minimum weight: " << result << endl;
    return 0;
}

第五题 染色问题

一个树，每个节点一个值，初始每个节点都是白色，每次操作可以选择一组相邻节点，如果两个节点都是白色并且乘积为完全平方数，可以把这两个节点同时染红，问最多能染红多少个节点

输入第一行n个节点，第二行每个节点权值，后面n-1行每行两个数代表这两个节点中间有边相连

思路：树形dp