拼多多秋招 2023.09.10 编程题目与题解

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

1、\(\mathbf{X}\)数组

多多最近在研究一种由\(n\)个数字构成的特殊数组\(\mathbf{X}=\{x_1,x_2,\dots,x_n\}\)，这个数组有\(2\)个特点：

\(\mathbf{X}\)数组是严格递增的，也就是\(x_1 < x_2 < \dots < x_n\)
\(\mathbf{X}\)数组的相邻数字间做差值，得到新数组\(\mathbf{Y}\)是严格递减的。换句话说，用\(y_i=x_{i+1}-x_{i}\) 表示相邻数字间差值，则新数组\(\mathbf{Y}=\{y_1, y_2,\dots, y_{n-1}\}\)满足：\(y_1 > y_2 > \dots > y_{n-1}\)

现在，假设只有数字\(n\)、数组的第一个数字的值 \(a=x_1\)以及数组最后一个数字的值\(b=x_n\)的情况下，多多想知道能不能到找到任意\(1\)个这样的特殊数组，同时满足上面两个条件。

输入

第一行，一个整数\(T\)，表示测试用例的组数\((1\le T\le 3000)\)

接下来每组测试用例包含一行数据，由\(3\)个数字构成分别是: \(n,a,b (1\le n \le 400，1\le a\le b \le1000)\)，分别表示：数组的长度、第一个数字的值、最后一个数字的值。

输出

每组测试用例，输出一行：

YES或者NO表示：是否存在任意\(1\)个这样的数组。

样例

输入：
3
3 1 5
5 1 5
5 1 100

输出：
YES
NO
YES

提示：
共有3组测试用例
，对于第1组用例，可以找到数组: [1,4,5] 满足数组本身是严格递增的，数组相邻数字之间的差值[3,1] 是严格递减的，所以输出: YES
对于第2组用例，严格递增的数组是:[1,2,3,4,5]，但是数组相邻数字之间差值构成的数组[1,1,1,1] 不满足严格递减，所以输出: NO
对于第3组用例，可以找到数组: [1,40,70.90,100]满足数组本身严格递增，数组相邻数字之间的差值[39,30,20,10] 满足严格递减，所以输出：YES

解答

我们需要通过尝试构造\(\mathbf{Y}\)，从而构造出\(\mathbf{X}\)数组。

由于\(\mathbf{X}\)是单调递增的，因此为了使它的递增趋势尽量小，并且\(\mathbf{Y}\)是单调递减的，那么此时\(\mathbf{Y}\)至少可以取成\([n-1,n-2,\dots,1]\)，因此\(x_n\)的值至少为\(a+\dfrac{n(n-1)}{2}\)。只要将\(y_1\)的值任意加上一个数\(t\)，那么\(x_n\)也必定会加上\(t\)，同时\(\mathbf{X}\)和\(\mathbf{Y}\)仍然会满足题目的条件。

因此，只需要验证\(a+\dfrac{n(n-1)}{2}\le b\)是否满足即可。

代码

#include <bits/stdc++.h>
using namespace std;

void solve(){
    int n,a,b;
    scanf("%d %d %d",&n,&a,&b);
    puts(a+n*(n-1)/2<=b?"YES":"NO");
}
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        solve();
    }
}

2、数字匹配

多多君从小到大都没有谈过恋爱，因此他希望大家都能成双入对，包括数字。现在他有一串数字，他希望其中的数字能两两匹配。能够两两匹配的数字满足如下要求：

他们之间差的绝对值大于等于一个特定值。
他们没有出现在其他数字对中，即每个数字只能被匹配一次或零次。

现在，多多君希望能知道，给定一串数字，最多可以匹配成功多少对数字对。

输入

第一行，\(2\)个整数\(N,M\)，分别表示数字的个数和要求数字间的差异值\(( 1\le N\le 2000000,0 \le M \le 10^9)\)。

接下来一行，由\(N\)个整数构成，分别表示第\(i\)个数字\(X_i\)。\((0\le X_i\le 10^9)\)。

输出

一个数字，表示在给定的数字中，能匹配的最多数字对个数。

样例

输入：
4 2
1 3 3 7

输出：
2

提示：
可以匹配最多2个数字对(1,3)和(3,7)。

输入：
5 5
10 9 5 8 7

输出：
1

提示：
可以匹配最多1个数字对(5,10)，其余数字对都不满足差的绝对值大于等于5。

解答

如果我们可以匹配出\(k(k\le n/2)\)个匹配对，那么在极端情况下，我们可以选择最小的\(k\)个数和最大的\(k\)个数进行匹配。

更具体地，如果这\(k\)个最小数从小到大为\(a_1,a_2,\dots,a_k\)，以及\(k\)个最大数从小到大为\(b_1,b_2,\dots,b_k\)，那么我们可以很简单地验证这个匹配是否为所求：\(\forall i\in[1,k],b_i-a_i\ge k\)成立。

因此，我们可以对\(k\)进行二分，从而求出最大的匹配数量。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int M=2000004;
int a[M],n,m;
bool ok(int k){
    for(int i=1;i<=k;i++)
        if(a[n-k+i]-a[i]<m) return 0;
    return 1;
}
int main(){
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    sort(a+1,a+n+1);
    int l=0,r=n/2;
    while(l<r){
        int mid=(l+r+1)>>1;
        if(ok(mid)) l=mid;
        else r=mid-1;
    }
    printf("%d\n",l);
}

3、矩阵还原

多多君在研究一种特殊的01矩阵，即一个\(N\times M\)的二维矩阵中，每个元素只能是\(0\)或者\(1\)。

多多君将原始矩阵\(A\)进行一种特殊变换来创造一个新矩阵\(B\)，其中两个矩阵的行和列保持一致。

对于第\(i\)行第\(j\)列的元素（编号从\(1\)开始），生成规则如下：

\[b[i][j]= \max(A[i][1],A[i][2],\dots,A[i][M],A[1][j],A[2][j],\dots,A[n][j])\]

即\(B[i][j]\)的值为\(A[i][j]\)所在的同一行和同一列的所有元素中的最大值。多多君经过分析发现，通过矩阵\(A\)计算得出矩阵\(B\)比较容易，那是否能快速通过矩阵\(B\)还原得出矩阵\(A\)呢。

输入

第一行，\(1\)个整救\(T\)。代表试用例的组数。

\((1\le T\le 20)\)

对于每俎筹试用例：

第一行：2个整数\(N\)和\(M\)。表示矩阵的行和列。

\((1\le N\le 100,1\le M\le 100)\)

接下来\(N\)行\(M\)列，其中第\(i\)行第\(j\)列表示给定的矩阵\(B\)的元素\(B[i][j]\)。

\((0\le B[i][j]\le 1)\)

输出

对于每组测试用例：

如果可以通过矩阵\(B\)还得到阵\(A\)，那么输出所有可能的矩阵\(A\)中，最多能有多少个值为\(1\)的元素。

否则输出\(-1\)，表示矩阵\(B\)无法还原得到矩阵\(A\)。

样例

输入：
3
2 2
1 0
0 0
2 3
0 1 0
1 1 1
1 2
1 1

输出：
-1
1
2

提示：
对于第一组用例，不存在矩阵A可以得到该矩阵B
对于第二组用例，满足条件的矩阵A只有一个：
0 0 0
0 1 0
对于第二组用例，满足条件的矩阵A只有一个：
1 1

解答

如果\(B[i][j]=0\)，那么\(A\)的第\(i\)行第\(j\)列中的所有元素都为\(0\)。因此，我们可以提前确定\(A\)矩阵的这些位置的元素。

如果\(B[i][j]=1\)。那么第\(i\)行第\(j\)列必定存在一个元素为\(1\)。按照贪心的思想，如果\(A[i][j]\)可以不填\(0\)，那么必定填上\(1\)。

因此，我们重新构造出来了一个待验证的\(A\)矩阵，按照这个\(A\)矩阵，我们按照相同的算法构造出一个\(B'\)矩阵，并判断\(B=B'\)是否满足即可。

代码

#include <bits/stdc++.h>
using namespace std;

const int N=104;
int b[N][N],a[N][N];
int r[N],c[N],mr[N],mc[N],n,m;
int solve(){
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            scanf("%d",&b[i][j]);
    memset(r,0,sizeof(r));
    memset(c,0,sizeof(c));
    memset(mr,0,sizeof(mr));
    memset(mc,0,sizeof(mc));
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(b[i][j]==0){
                r[i]=c[j]=1;
            }
        }
    }
    int ans=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(r[i]||c[j]) a[i][j]=0;
            else a[i][j]=1,++ans;
            mr[i]=max(mr[i],a[i][j]);
            mc[j]=max(mc[j],a[i][j]);
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(max(mr[i],mc[j])!=b[i][j]) return -1;
        }
    }
    return ans;

}
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        printf("%d\n",solve());
    }
}

4、修车计划

多多君计划周未去骑行，不过他的自行车目前年久失修，有很多部件都坏了。多多想在出发前把它修好。

对于每个部件，多多可以选择修理，也可以选择直接换。直接换比修理花的时间少一点，但是花的钱多一点。多多想知道怎么安排修理计划，才能在出发前修好他的自行车并且花的钱最少。

输入

第一行两个整数\(N,M\)分别代表坏的部件数和多多可以用于修车的时间。 \((1\le N \le 40,1\le M \le 10000000)\)

接下来有\(N\)行，每行有\(4\)个整数\(A_i,B_i,C_i,D_i\)，分别代表第\(i\)个部件，修理需要花的时间，修理需要花的钱，直接换需要花的时间，直接换需要花的钱。\((1 \le C_i<A_i \le 10000000,1 \le B_i <D_i\le 10000000)\)

输出

输山一个整数，代表在\(M\)时间内修好自行车，需要花的最少金钱，如果不能在\(M\)时间内修好，输出\(-1\)。

样例

输入：
1 10
10 2 3 5

输出：
2

提示：
选择修理，时间花费10，金钱花费2

输入：
1 10
12 2 3 5

输出：
5

提示：
修理这个部件需要时间花费是12，时间不够，只能选择换，时间花费3，金钱花费5

输入：
1 10
10 2 3 5

输出：
2

提示：
选择修第一个部件，第二、三个部件直接换，总时间花费9 + 3 + 5 = 17，金钱花费1 + 10 + 12 = 23

解答

由于\(m\le 10^7\)，数量级比较高，同时\(n\le 40\)，因此普通的\(O(nm)\)的0-1背包问题做法非常容易超时。而如果我们直接使用搜索算法来枚举每个选择，那时间也达到了\(O(2^n)\)，这样同样也是不可接受的。

我们能不能枚举一半的部件的选择，然后继续枚举另一半的部件的选择，再将它们组合起来呢？可以，我们将使用meet in the middle算法解决这个问题。

更具体地说，我们将这些部件均匀地分成两份，其中一份有\(\lfloor n/2\rfloor\)个部件，另一份有\(\lceil n/2\rceil\)个部件。

我们分别枚举其中一份部件的每种不同决策的组合，比如说，第一份部件有\(2^{\lfloor n/2\rfloor}\)种，第二份有\(\lceil n/2\rceil\)种。两个部分种，每种决策的组合都有两种个变量\(k,v\)，分别表示这组决策花费了\(k\)的时间和\(v\)金钱。

假设这两部分不同的决策分别存在数组\(s_0,s_1\)中，其每个数组元素都有两个属性\(k,v\)，那么我们先对\(s_0,s_1\)按照\(k\)进行排序。对于\(s_0\)中的每个元素\(s_0[i]\)，找到一个最大的下标\(j\)满足\(s_0[i].k+s_1[j].k\le m\)，那么其中一个答案的候选值为\(\displaystyle{s_0[i].v+\min_{k=0}^j \{s_1[k].v\}}\)。后面这个过程我们可以使用双指针法完成。

因此，这道题可以在\(O(n\cdot 2^{n/2})\)的时间内完成。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

# define X first
# define Y second
# define pi pair<int,int>

int A[44],B[44],C[44],D[44];
int main(){
    int n,m;
    scanf("%d %d",&n,&m);
    vector<int>a,b;
    for(int i=0;i<n;i++){
        scanf("%d %d %d %d",&A[i],&B[i],&C[i],&D[i]);
        if(i&1) a.push_back(i);
        else b.push_back(i);
    }
    vector<pi>s0,s1;
    for(int s=0;s<(1<<a.size());s++){
        int k=0,v=0;
        for(int i=0;i<a.size();i++){
            if(s>>i&1) k+=A[a[i]],v+=B[a[i]];
            else k+=C[a[i]],v+=D[a[i]];
        }
        if(k\lem) s0.push_back(pi(k,v));
    }
    for(int s=0;s<(1<<b.size());s++){
        int k=0,v=0;
        for(int i=0;i<b.size();i++){
            if(s>>i&1) k+=A[b[i]],v+=B[b[i]];
            else k+=C[b[i]],v+=D[b[i]];
        }
        if(k\lem) s1.push_back(pi(k,v));
    }
    sort(s0.begin(),s0.end());
    sort(s1.begin(),s1.end());
    int ans=1e9;
    int mn=1e9;
    for(int i=s0.size()-1,j=0;i>=0;i--){
        for(;j<s1.size()&&s0[i].X+s1[j].X\lem;j++){
            mn=min(mn,s1[j].Y);
        }
        ans=min(ans,s0[i].Y+mn);
    }
    if(ans==1e9) ans=-1;
    printf("%d\n",ans);
}