美团秋招 2023.08.12 笔试题目与题解

发表于 2023-08-12 更新于 2023-11-11 分类于笔试阅读次数：本文字数： 3.6k 阅读时长 ≈ 3 分钟

1、小美的排列询问

小美拿到了一个排列。她想知道在这个排列中，\(x\)和\(y\)是否是相邻的。你能帮帮她吗？

排列是指一个长度为\(n\)的数组，其中\(1\)到\(n\)每个元素恰好出现一次。

输入

第一行输入一个正整数\(n\)，代表排列的长度。

第二行输入\(n\)个正整数\(a_i\)，代表排列的元素。

第三行输入两个正整数\(x\)和\(y\)，用空格隔开。

\(1\leq n \leq 200000\)
\(1\leq a_i,x,y \leq n\)
保证\(x\neq y\)

输出

如果\(x\)和\(y\)在排列中相邻，则输出"Yes"。否则输出"No"。

样例

输入：
4
1 4 2 3
2 4

输出：
Yes

输入：
5
3 4 5 1 2
3 2

输出：
No

解答

记录下每一个元素的位置，然后判断\(x,y\)这两个元素是否相邻即可。

代码

# include <bits/stdc++.h>
using namespace std;
const int N=200004;
int pos[N],n;
int main(){
    int x,y;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&x);
        pos[x]=i;
    }
    scanf("%d %d",&x,&y);
    puts(abs(pos[x]-pos[y])==1?"Yes":"No");
}

2、小美走公路

有一个环形的公路，上面共有\(n\)站，现在给定了顺时针第\(i\)站到第\(i+1\)站之间的距离（特殊的，也给出了第\(n\)站到第\(1\)站的距离）。小美想沿着公路第\(x\)站走到第\(y\)站，她想知道最短的距离是多少？

输入

第一行输入一个正整数\(n\)，代表站的数量。

第二行输入\(n\)个正整数\(a_i\)，前\(n-1\)个数代表顺时针沿着公路走，第\(i\)站到第\(i+1\)站之间的距离；最后一个正整数代表顺时针沿着公路走，第\(n\)站到第\(1\)站的距离。

第三行输入两个正整数\(x\)和\(y\)，代表小美的出发地和目的地。

\(1\leq n \leq 10^5\)
\(1\leq a_i \leq 10^9\)
\(1\leq x,y \leq n\)

输出

一个正整数，代表小美走的最短距离。

样例

输入：
3
1 2 2
2 3

输出：
2

输入：
3
1 2 2
1 3

输出：
2

解答

首先使用前缀和记录这个环形道路中，从第\(n\)站顺时针到第\(i\)个站的距离为\(s[i]\)，那么\(s[n]\)就是这个环形铁路的总长度。

从点\(x\)走到点\(y(x<y)\)无非就两种选择，一种是顺时针，一种是逆时针，两者所包含的路径是对立的。其中一种走法的总距离是\(s[y-1]-s[x-1]\)，另一种走法是\(s[n]-(s[y-1]-s[x-1])\)。

代码

# include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=200004;
int a[N],n;
ll s[N];
int main(){
    int x,y;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        s[i]=s[i-1]+a[i];
    }
    scanf("%d %d",&x,&y);
    if(x>y) swap(x,y);
    ll d=s[y-1]-s[x-1];
    printf("%lld\n",min(d,s[n]-d));
}

3、小美的蛋糕切割

小美有一个矩形的蛋糕，共分成了\(n\)行\(m\)列，共\(n\times m\)个区域，每个区域是一个小正方形，已知蛋糕每个区域都有一个美味度。她想切一刀把蛋糕切成两部分，自己吃一部分，小团吃另一部分。

小美希望两个人吃的部分的美味度之和尽可能接近，请你输出\(|s_1-s_2|\)的最小值。（其中\(s_1\)代表小美吃的美味度，\(s_2\)代表小团吃的美味度）。

请务必保证，切下来的区域都是完整的，即不能把某个小正方形切成两个小区域。

输入

第一行输出两个正整数\(n\)和\(m\)，代表蛋糕区域的行数和列数。

接下来的\(n\)行，每行输入\(m\)个正整数\(a_{ij}\)，用来表示每个区域的美味度。

\(1\leq n,m \leq 10^3\)
\(1\leq a_{ij} \leq 10^4\)

输出

一个整数，代表\(|s_1-s_2|\)的最小值。

样例

输入：
2 3
1 1 4
5 1 4

输出：
0

提示：
把蛋糕像这样切开：
1 1 | 4
5 1 | 4
左边蛋糕美味度之和是8
右边蛋糕美味度之和是8
所以答案是0。

解答

这里只需要完整地横向/竖向切一刀。由此只需要记录第\(i\)行中的所有元素和\(ax[i]\)，以及第\(j\)列所有元素和\(ay[j]\)。

然后分别求出\(ax[i],ay[i]\)的前缀和\(sx[i],sy[i]\)（可见\(sx[n],sy[n]\)就是矩阵所有元素之和）。对于每种按行切法，上面\(i\)行的所有元素都属于一个人，剩下的元素属于另一个人，因此这种切法的美味度相差值为\(|sx[i]-(sx[n]-sx[i])|=|sx[n]-2\cdot sx[i]|\)。

对于每种按列切法也类似，如果这种切法位于第\(j\)列的下面，那么美味度相差值为\(|sy[j]-(sy[m]-sy[j])|=|sy[m]-2\cdot sy[j]|\)。

代码

# include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1004;
int ax[N],ay[N];
ll sx[N],sy[N];
int n,m;
int main(){
    int x;
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            scanf("%d",&x);
            ax[i]+=x;
            ay[j]+=x;
        }
    }
    for(int i=1;i<=n;i++)
        sx[i]=sx[i-1]+ax[i];
    for(int j=1;j<=m;j++)
        sy[j]=sy[j-1]+ay[j];
    ll ans=sx[n];
    for(int i=0;i<n;i++)
        ans=min(ans,abs(sx[i]-(sx[n]-sx[i])));
    for(int j=0;j<m;j++)
        ans=min(ans,abs(sy[j]-(sy[m]-sy[j])));
    printf("%lld\n",ans);
}

4、小美的字符串变换

小美拿到了一个长度为\(n\)的字符串，她希望将字符串从左到右平铺成一个矩阵（先平铺第一行，然后是第二行，以此类推，矩阵有\(x\)行\(y\)列，必须保证\(x*y=n\)，即每\(y\)个字符换行，共\(x\)行）。

该矩阵的权值定义为这个矩阵的连通块数量。小美希望最终矩阵的权值尽可能小，你能帮小美求出这个最小权值吗？

注：我们定义，上下左右四个方向相邻的相同字符是连通的。

输入

第一行输入一个正整数\(n\)，代表字符串的长度。

第二行输入一个长度为\(n\)的、仅由小写字母组成的字符串。

\(1\leq n \leq 10^4\)

输出

输出一个整数表示最小权值。

样例

输入：
9
aababbabb

输出：
2

提示：
平铺为3*3的矩阵：
aab
abb
abb
共有2个连通块，4个a和5个b。

解答

本题本质上是\(2\)个问题的结合。

第\(1\)个问题是将一个字符串转化成一个二维矩阵。这里的处理仅仅是顺序遍历每个字符并拼接到对应的列中。

第\(2\)个问题是求出这个二维矩阵有多少个连通块。只需要按顺序枚举每个矩阵的元素，使用BFS求出一个个连通块并统计数量即可。

因此总的时间复杂度为\(O(n\cdot \sigma_0(n))=O(n\log n)\)，其中\(\sigma_0(n)\)是\(n\)的因数个数，这里我们只需要求出\(\sigma_0(n)\)个矩阵并进行BFS。

代码

# include <bits/stdc++.h>
# define pi pair<int,int>
# define X first
# define Y second
using namespace std;
typedef long long ll;
const int N=1004;
int dx[4]={-1,1,0,0},dy[4]={0,0,-1,1};
vector<string>reshape(string &s,int n,int m){
    vector<string>a(n);
    for(int j=0;j<s.size();j++)
        a[j/m]+=s[j];
    return a;
}
int bfs(vector<string>&mp){
    int n=mp.size(),m=mp[0].size();
    vector<vector<int>>vis(n,vector<int>(m));
    queue<pi>q;
    int cnt=0;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(vis[i][j]==0){
                ++cnt;
                q.push(pi(i,j));
                while(!q.empty()){
                    auto [px,py]=q.front();q.pop();
                    for(int i=0;i<4;i++){
                        int x=px+dx[i],y=py+dy[i];
                        if(x<0||y<0||x>=n||y>=m||vis[x][y]||mp[px][py]!=mp[x][y]) continue;
                        vis[x][y]=1;
                        q.push(pi(x,y));
                    }
                }
            }
        }
    }
    return cnt;
}
int main(){
    int n;
    string s;
    cin>>n>>s;
    int ans=n;
    for(int r=1;r<=n;r++){
        if(n%r==0){
            vector<string>mp=reshape(s,r,n/r);
            ans=min(ans,bfs(mp));
        }
    }
    printf("%d\n",ans);
}

5、小美的树上染色

小美拿到了一棵树，每个节点有一个权值。初始每个节点都是白色。

小美有若干次操作，每次操作可以选择两个相邻的节点，如果它们都是白色且权值的乘积是完全平方数，小美就可以把这两个节点同时染红。

小美想知道，自己最多可以染红多少个节点？

输入

第一行输入一个正整数\(n\)，代表节点的数量。

第二行输入\(n\)个正整数\(a_i\)，代表每个节点的权值。

接下来的\(n-1\)行，每行输入两个正整数\(u,v\)，代表节点\(u\)和节点\(v\)有一条边连接。

\(1\leq n \leq 10^5\)
\(1\leq a_i \leq 10^9\)
\(1\leq u,v \leq n\)

输出

输出一个整数，表示最多可以染红的节点数量。

样例

输入：
3
3 3 12
1 2
2 3

输出：
2

提示：
可以染红第二个和第三个节点。
请注意，此时不能再染红第一个和第二个节点，因为第二个节点已经被染红。
因此，最多染红 2 个节点。

解答

本题是一道树形DP问题。这道题是为了求一组在树\(T\)上满足题目条件的最大匹配\(M\)，对于每个节点\(u\)，只有两种可能性：被染色了，没有被染色。在遍历这棵树的时候，假设以\(1\)为根节点，\(T.son[u]\)表示节点\(u\)中的所有子节点。

令\(f_1(u)\)表示以\(u\)为根节点的子树中，满足题目条件的最大匹配数，并且节点\(u\)在这组匹配中被使用。令状态\(f_2(u)\)表示以\(u\)为根节点的子树中，满足题目条件的最大匹配数，并且节点\(u\)在这组匹配中不被使用。

接下来先求解\(f_2(u)\)。由于\(u\)没有被选上，因此它的子节点有没有被选上一组匹配并没有所谓，只需要取最优的一个即可，并相加。因此可以写出关于\(f_2(u)\)的状态转移方程：

\[f_2(u)=\sum_{v\in T.son[u]} \max\{f_1(v),f_2(v)\}\]

接下来求解\(f_1(u)\)。由于\(u\)被选上了一组匹配，并且和某个子节点\(v\)相连，此时\(a[u]\cdot a[v]\)必定是个完全平方数，\(v\)在\(v\)所在子树上必定不能被选在一组匹配中，因此必须从\(f_2(v)\)转移而来。而对于\(u\)中的其它子节点\(w\in T.son[u]-\{v\}\)，\(w\)有没有被选上并没有所谓，因此可以从\(f_1(w)\)或者\(f_2(w)\)转移而来。最终再将\((u,v)\)再增添到以\(u\)为子树的这组匹配中即可（也就是需要\(+1\)）。因此可以写出关于\(f_1(u)\)的状态转移方程：

\[\begin{aligned} f_1(u)&=\max_{\substack{v\in T.son[u];\\ a[u]\cdot a[v]\text{ is a perfect square}}} \left\{f_2(v)+1+\sum_{w\in T.son[u]-\{v\}} \max\{f_1(v),f_2(v)\}\right\}\\ &=\max_{\substack{v\in T.son[u];\\ a[u]\cdot a[v]\text{ is a perfect square}}} \{f_2(u)-\max\{f_1(v),f_2(v)\}+f_2(v)+1\} \end{aligned}\]

由于最终要求的是染色的节点数，因此最终答案为\(2\cdot \max\{f_1(1),f_2(1)\}\)。

这里还需要注意一个细节，判断是否为平方数的过程中，sqrt的输出结果是一个浮点数，需要再添加上一个比较小的数\(\epsilon=10^{-7}\)，再向下取整才能够正确求出\(\lfloor\sqrt{x}\rfloor\)的值。

代码

# include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=100004;
bool is_sqrt(ll x){
    ll y=sqrt(x)+1e-7;
    return y*y==x;
}
vector<int>g[N];
ll a[N];
int n;
int f1[N],f2[N];
void dfs(int u,int fa){
    for(int v:g[u]){
        if(v==fa) continue;
        dfs(v,u);
    }
    int sum=0;
    for(int v:g[u]){
        if(v==fa) continue;
        sum+=max(f1[v],f2[v]);
    }
    f2[u]=sum;
    for(int v:g[u]){
        if(v==fa) continue;
        if(is_sqrt(a[u]*a[v])){
            f1[u]=max(f1[u],sum-max(f1[v],f2[v])+f2[v]+1);
        }
    }

}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%lld",&a[i]);
    int u,v;
    for(int i=1;i<n;i++){
        scanf("%d %d",&u,&v);
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs(1,0);
    printf("%d\n",max(f1[1],f2[1])*2);
}