美团笔试（2023/8/12）1、小美拿到了一个排列。她想知道在这个排列中，x和y是否是相邻的。你能帮帮她吗？排列是指一个长度为n的数组，其中 1 到n 每个元素恰好出现一次。输入描述第一行输入一个正整数n，代表排列的长度。第二行输入n个正整数ai，代表排列的元素。第三行输入两个正整数x和y，用空格隔开。保证x≠y输出描述如果x和y在排列中相邻，则输出"Yes"。否则输出"No"。示例1输入：41 4 2 32 4输出Yes示例2：输入：53 4 5 1 23 2输出：No#include <bits/stdc++.h>using namespace std;int main() {    int n;    cin >> n;    vector<int> nums(n);    for (int i = 0; i < n; i++) {        cin >> nums[i];    }    int x, y;    bool flag = false;    for (int i = 0; i < n - 1; i++) {        if (nums[i] == x && nums[i + 1] == y)            flag = true;        if (nums[i] == y && nums[i + 1] == x)            flag = true;    }    if (flag) cout << "Yes" << endl;    else cout << "No" << endl;    return 0;}2、有一个环形的公路，上面共有n站，现在给定了顺时针第i站到第i+1站之间的距离（特殊的，也给出了第n站到第1站的距离）。小美想沿着公路第x站走到第y站，她想知道最短的距离是多少？输入描述第一行输入一个正整数n，代表站的数量。第二行输入n个正整数ai，前n-1个数代表顺时针沿着公路走，i站到第i+1站之间的距离；最后一个正整数代表顺时针沿着公路走，第n站到第1站的距离。· 第三行输入两个正整数x和y，代表小美的出发地和目的地。输出描述一个正整数，代表小美走的最短距离。示例1输入31 2 22 3输出2示例2输入31 2 21 3输出2#include <bits/stdc++.h>using namespace std;int main() {    int n;    cin >> n;    vector<long long> nums(n+1);    long long sum =0,ans = 0;    for(int i = 1; i<=n; i++){        cin >> nums[i];        sum += nums[i];    }    int x,y;    cin >> x >> y;    if(x > y) swap(x,y);    for(int i= x; i < y; i++){        ans += nums[i];    }    ans = min(ans,sum-ans);    cout << ans << endl;    return 0;}3、小美有一个矩形的蛋糕，共分成了n行m列，共n*m个区域，每个区域是一个小正方形，已知蛋糕每个区域都有一个美味度。她想切一刀把蛋糕切成两部分，自己吃一部分，小团吃另一部分。小美希望两个人吃的部分的美味度之和尽可能接近，请你输出 |s1-s2|的最小值。(其中s1代表小美吃的美味度，s2代表小团吃的美味度)请务必保证，切下来的区域都是完整的，即不能把某个小正方形切成两个小区域。输入描述第一行输出两个正整数n和m,代表蛋糕区域的行数和列数。接下来的n行，每行输入m个正整数，用来表示每个区域的美味度。1 <=n,m <=10^3m个正整数均小于10^4示例1输入2 31 1 45 1 0输出：0#include <bits/stdc++.h>using namespace std;int n,m;long long a[1005][1005];int main() {    cin >> n >> m;    long long sum =0;    for(int i =1; i<=n; i++){        for(int j = 1; j<=m; j++){            cin >> a[i][j];            sum += a[i][j];        }    }    for(int i=1; i<=n; i++){        for(int j=1; j<=m; j++){            a[i][j] = a[i][j-1] +a[i-1][j] -a[i-1][j-1] +a[i][j];        }    }    long long ans = sum;    for(int j =1; j<=m; j++){        ans = min(ans,abs(sum - 2*a[n][j]));    }        for(int i=1; i<=n; i++){        ans = min(ans,abs(sum-2*a[i][m]));    }    cout << ans <<endl;    return 0;}4、小美拿到了一个长度为n的字符串，她希望将字符串从左到右平铺成一个矩阵（先平铺第一行，然后是第二行，以此类推，矩阵有x行y列，必须保证x*y=n，即每y个字符换行，共x行）。该矩阵的权值定义为这个矩阵的连通块数量。小美希望最终矩阵的权值尽可能小，你能帮小美求出这个最小权值吗？注：我们定义，上下左右四个方向相邻的相同字符是连通的。输入描述第一行输入一个正整数n，代表字符串的长度。第二行输入一个长度为n的、仅由小写字母组成的字符串。1<=n<=10^4输出描述输出一个整数表示最小权值。示例1输入9aababbabb输出2说明平铺为3*3的矩阵：aababbabb共有2个连通块，4个a和5个b。5、小美拿到了一棵树，每个节点有一个权值。初始每个节点都是白色。小美有若干次操作，每次操作可以选择两个相邻的节点，如果它们都是白色且权值的乘积是完全平方数，小美就可以把这两个节点同时染红。小美想知道，自己最多可以染红多少个节点？输入描述第一行输入一个正整数n，代表节点的数量。第二行输入n个正整数ai，代表每个节点的权值。接下来的n-1行，每行输入两个正整数u，v，代表节点u和节点v有一条边连接。输出描述输出一个整数，表示最多可以染红的节点数量。示例1输入33 3 121 22 3输出2