阿里国际秋招 2023.09.18 编程题目与题解

发表于 2023-09-21 分类于笔试阅读次数：本文字数： 2.3k 阅读时长 ≈ 2 分钟

1、小红吃果子

有\(n\)棵树，每棵树的高度为\(a_i\)，每棵树在\(b_i\)的高度上有一个果子。

小红从第一棵树的\(0\)高度位置开始，每次可以进行如下操作：

可以调整自身的高度，即从高度变为高度\(x+1\)或\(x-1\)，需要保证调整后高度仍然在\(0\)到\(a_i\)之间；
或者从第\(i\)棵树的高度移动到第\(i+1\)棵树的高度，需要保证\(x\le a_{i+1}\)。

小红始终不能超过所在树的高度。

小红吃到所有果子，最少需要几次操作？

输入

第一行一个整数\(n\)，表示树的数量。

第二行\(n\)个整数\(a_i\)，表示每棵树的高度。

第三行\(n\)个整数\(b_i\)，表示每棵树上果子的高度。

\(1\le n\le 10^5\)
\(1\le b_i\le a_i \le 10^9\)

输出

输出一个整数，表示最少需要的操作次数。

样例

解答

该题目的答案为\(\displaystyle{b_1+\sum_{i=2}^n|b_i-b_{i-1}|}\)。对于相邻的两棵树上面的果子，如果\(b_{i-1}\le b_{i}\)，那么先从树\(i-1\)移动到树\(i\)，再上升到高度\(b_i\)即可。如果\(b_{i-1}\ge b_i\)，那么先下降到高度\(b_i\)，再从树\(i-1\)移动到树\(i\)即可。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=100004;
int a[N],n;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    ll ans=n-1+a[1];
    for(int i=1;i<n;i++)
        ans+=abs(a[i+1]-a[i]);
    printf("%lld\n",ans);

}

2、小红做游戏

小红在和朋友们做游戏，包括小红一共\(n\)个人，大家围成了一个圈。

第\(i\)个位置的人只记住了在他右手边的两个人，也就是说，位置\(1\)的人记住了位置\(2\)和位置\(3\)的人，位置\(n-1\)的人记住了位置\(n\)和位置\(1\)的人。

现在小红想知道，能不能还原出每个人的位置。

如果有多种可能，任意输出一种即可，保证至少存在一种符合要求的情况。

输入

输入描述一行一个整数\(n\)，表示人数。接下来\(n\)行，每行两个整数\(a_i\)和\(b_i\)，表示第个人记住了第\(a_i\)个人和第\(b_i\)个人。（\(b_i\)不一定在\(a_i\)的右边）。

\(3\le n\le 10^5\)
\(1\le a_i,b_i\le n\)

输出

还原出每个人的位置，输出一行\(n\)个整数，表示每个人的位置。

样例

解答

假设用一个长度为\(n\)的数组\(z\)来表示一个填充方案。由于这是一个环形，因此不失一般性，先固定好其中一个人的位置（这里假设是第\(1\)个人，即\(z_1=1\)），那么要么\(z_2=a_i,z_3=b_i\)，要么\(z_2=b_1,z_3=a_i\)。

考虑好其中一种情况后，我们将\(i\)从\(2\)一直遍历到\(n-2\)，并将一个人的位置填入\(z_{i+2}\)。如果\(z_{i+1}\in\{a_{z_i},b_{z_i}\}\)，那么说明\(z_{i+2}\)是这两个集合中的另一个数，否则这是错误的排列。

最终填好了序列\(z\)后，按照定义验证填入的\(z_{n-1},z_n\)是否正确即可。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=100004;
int a[N],b[N],n;
int z[N];
bool ok(){
    for(int i=2;i<=n-2;i++){
        int m=z[i],x=z[i+1];
        if(x==a[m]) z[i+2]=b[m];
        else if(x==b[m]) z[i+2]=a[m];
        else return 0;
    }
    int m=z[n-1];
    if(!(a[m]==z[n]&&b[m]==z[1]||a[m]==z[1]&&b[m]==z[n])) return 0;
    m=z[n];
    if(!(a[m]==z[1]&&b[m]==z[2]||a[m]==z[2]&&b[m]==z[1])) return 0;
    return 1;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d %d",&a[i],&b[i]);
    z[1]=1;z[2]=a[1];z[3]=b[1];
    if(!ok()){
        z[2]=b[1];z[3]=a[1];ok();
    }
    for(int i=1;i<=n;i++)
        printf("%d%c",z[i], " \n"[i==n]);
}

3、最长递增子数组

给定两个长度为n的数组\(a,b\)和一个空数组\(c\)。

每次操作，可以选择\(a\)数组或者\(b\)数组的第一个元素，添加到\(c\)数组的末尾然后从相应的数组删除。

\(a\)数组和\(b\)数组都为空时，结束操作。

在所有可能可以获得的\(c\)数组中，请你找出最长的递增子数组，子数组需要满足相邻两个元素的差的绝对值为\(1\)，输出这个子数组的长度。

输入

第一行输入一个整数\(n\)。

第二行输入\(n\)个整数\(a_i\)。

第三行输入\(n\)个整数\(b_i\)。

\(1\le n,a_i,b_i\le 2\times10^3\)

输出

输出一个整数。

样例

输入：
3
5 2 4
7 1 3

输出：
4

提示：
可以得到一个c数组：7 5 1 2 3 4。

解答

这道题的特征比较明显，我们可以使用动态规划来完成。

令状态\(f(i,j,k)(0\le i,j\le n,0\le k\le 1)\)表示当前已经将\(a\)的前\(i\)个元素和\(b\)的前\(j\)个元素插入了数组\(c\)中，并且如果\(k=0\)，那么\(c_{i+j}=a_i\)；如果\(k=1\)，那么\(c_{i+j}=b_j\)的情况下，以\(c_{i+j}\)为终点的最长递增且相邻之差的绝对值为\(1\)子数组的长度。可见，状态\(f(\cdot,0,1)\)和\(f(0,\cdot,0)\)都是未定义的状态，我们令其值为\(-\infty\)。

一开始，数组\(c\)只有一个元素，因此它有如下初值：

\(f(1,0,0)=1,f(0,1,1)=1\)

对于任意合法状态\(f(i,j,0)\)，可以知道我们现在取的是\(a\)中的第\(i\)个数，并放进位置\(c_{i+j}\)中。那么我们可以写出如下\(3\)种情况的转移：

\(1\rightarrow f(i,j,0)\)
\(f(i-1,j,0)+1\rightarrow f(i,j,0)\qquad\text{if}\qquad i>1\land a_i=a_{i-1}+1\)
\(f(i-1,j,1)+1\rightarrow f(i,j,0)\qquad\text{if}\qquad j\ge1\land a_i=b_j+1\)

由于\(a_i\)可以自成一个新的递增子数组，因此有第一行的转移；此外，它还可以拼接在原来自己的元素\(a_{i-1}\)后面，因此有第二行的转移；它还可以拼接在之前\(b_j\)的后面，因此有第三行的转移。

因此，本题的最终答案为\(\displaystyle{\max_{0\le i,j\le n}\{\max\{f(i,j,0),f(i,j,1)\}\}}\)。

代码

# include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2004;
int a[N],b[N],n;
int f[N][N][2];
void MAX(int &x,int y){
    if(y>=x) x=y;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1;i<=n;i++) scanf("%d",&b[i]);
    int ans=0;
    for(int i=0;i<=n;i++){
        for(int j=0;j<=n;j++){
            if(i==0&&j==0) continue;
            f[i][j][0]=f[i][j][1]=1;
            if(i>0){
                if(j>0&&a[i]==b[j]+1) MAX(f[i][j][0],f[i-1][j][1]+1);
                if(i>1&&a[i]==a[i-1]+1) MAX(f[i][j][0],f[i-1][j][0]+1);
            }
            if(j>0){
                if(i>0&&b[j]==a[i]+1) MAX(f[i][j][1],f[i][j-1][0]+1);
                if(j>1&&b[j]==b[j-1]+1) MAX(f[i][j][1],f[i][j-1][1]+1);
            }
            ans=max(ans,max(f[i][j][0],f[i][j][1]));
        }

    }
    printf("%d\n",ans);
}