8.12美团笔试（后端方向）

8.12笔试

第一题：小美玩排列

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

数据范围：

1 ≤ n ≤ 1e5

第二题：小美走公路

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

1 ≤ n ≤ 1e5

1 ≤ a[i] ≤ 1e9

第三题：小美切蛋糕

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

1 ≤ n , m≤ 1e3

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

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

现有一个长度为n的且仅包含小写字母的字符串s，小美想把这个字符串s平铺成一个xy的矩阵，要求xy == n，平铺的方法为：将字符串前y个字符按顺序放到第一行，将字符串第y+1到第2*y个字符按顺序放到第二行，以此类推。现规定矩阵的权值为连通量的数目，连通量代表的是从一个点出发，上下左右若存在相同字符则可以继续扩展该连通量（类似于一个岛屿，上下左右若存在相同的字符则可以扩展这个岛屿，或者可以理解为上下左右如果是相同字符则可以合并成一个连通量），求矩阵的最小权值

1 ≤ n ≤ 1e4

第五题：小美染色

现有一颗包含n个节点的树，节点i的权值为w[i]，d[i]代表节点i相邻的节点集合。一开始所有节点均为白色，若两个相邻节点均为白色且权值的乘积为完全平方数则可以将两个节点都染成红色，问最多可以将多少个节点染成红色

1 ≤ n ≤ 1e5

1 ≤ w[i] ≤ 1e9