美团秋招 2023.08.19 机试题目与题解

发表于 2023-08-19 分类于笔试阅读次数：本文字数： 3.3k 阅读时长 ≈ 3 分钟

1、小美的外卖订单编号

美团商家的订单发起时，订单编号最开始从\(1\)开始，后续每发起一个订单，订单编号便在上一订单编号的基础上\(+1\)。为了防止订单号过大，商家还可以设置一个编号上限\(m\)，当订单编号超过\(m\)时，将又从\(1\)开始编号。

小美想知道，当订单编号上限为\(m\)时，第\(x\)个订单编号是多少？将有\(q\)次询问。

输入

第一行输入一个整数\(q(1 \leq q \leq 50000)\)。

接下来\(q\)行，每行两个整数\(m,x(1 \leq m,x \leq 10^9)\)。

输出

\(q\)行，每行一个整数表示答案。

样例

解答

可见，订单号都是按照\(1,2,3,\dots,m,1,2,3,\dots,m,1,\dots\)的循环往复，只需要使用模运算即可。对于第\(x\)个订单，它的编号将是\((x-1)\% m+1\)。

代码

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

int main(){
    int T,m,x;
    scanf("%d",&T);
    while(T--){
        scanf("%d %d",&m,&x);
        printf("%d\n",(x-1)%m+1);
    }
}

2、小美的加法

小美有一个长度为\(n\)的数组，她想将这个数组进行求和，即\(sum = a_1+a_2+...+a_n\)。

小美可以使用一次魔法（也可以不使用），将其中一个加号变成乘号，使得\(sum\)最大。

求出最大的\(sum\)。

输入

第一行输入一个整数 \(n\) 。第二行输入 \(n\) 个整数表示数组 \(a\) 。

\(1 \leq n \leq 10^5\)
\(1 \leq a_i \leq 10^9\)

输出

输出一个整数表示答案。

样例

输入：
6
1 1 4 5 1 4

输出：
27

提示：
小美可以将 4 和 5 之间的加号改成乘号。
1 + 1 + 4 * 5 + 1 + 4 = 27

解答

假设现在将\(a[i]\)和\(a[i+1]\)中间的加号替换成乘号，式子中的其它符号不变，那么考虑如下变化：

\(a[i]\)和\(a[i+1]\)这两个项从这个加法式子中剔除。
\(a[i]\times a[i+1]\)作为新的项被添加进来。

因此，这个式子的新值就变成了\(sum-a[i]-a[i+1]+a[i]\times a[i+1]\)。最终答案为

\[\max\left\{sum,\max_{i=1}^{n-1}\{sum-a[i]-a[i+1]+a[i]\times a[i+1]\}\right\}\]

代码

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

const int N=100004;
ll a[N];
int main(){
    int n;
    scanf("%d",&n);
    ll s=0;
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i]);
        s+=a[i];
    }
    ll ans=s;
    for(int i=1;i<n;i++){
        ans=max(ans,s-a[i]-a[i+1]+a[i]*a[i+1]);
    }
    printf("%lld\n",ans);
}

3、小美的01串翻转

小美定义一个 01 串的权值为：每次操作选择一位取反，使得相邻字符都不相等的最小操作次数。

例如，"10001"的权值是 1，因为只需要修改一次：对第三个字符取反即可。现在小美拿到了一个 01 串，她希望你求出所有非空连续子串的权值之和，你能帮帮她吗？

输入

一个仅包含'0'和'1'的字符串，长度不超过\(2000\)。

输出

所有非空子串的权值和。

样例

输入：
10001

输出：
8

提示：
长度为 2 的子串中，有 2 个"00"的权值是 1。
长度为 3 的 3 个子串权值都是 1。
长度为 4 的 2 个子串权值都是 1。
长度为 5 的 1 个子串权值是 1。
总权值之和为 2+3+2+1=8

解答

一个01字符串，且相邻两位都不相同的无非就以下两种情况：

10101010...
01010101...

因此，对于一个长度为\(n\)的01字符串\(s\)，它的权值就是转换成这两个字符串中较少的次数。

这意味着字符串的下标奇偶性都和字符的奇偶性要么都相同，要么都不相同。假设字符串\(s\)有\(c\)个下标的奇偶性都和字符的奇偶性相同，那么\(s\)的权值为\(\min\{c,n-c\}\)。直接枚举每个起点，并维护\(c\)值即可。

代码

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

const int N=100004;
char s[N];
int main(){
    scanf("%s",s+1);
    int n=strlen(s+1);
    int ans=0;
    for(int i=1;i<=n;i++){
        int cnt=0;
        for(int j=i;j<=n;j++){
            cnt+=((s[j]&1)==((j-i)&1));
            ans+=min(cnt,j-i+1-cnt);
        }
    }
    printf("%d\n",ans);
}

4、小美的数组构造

小美拿到了一个数组\(a\)，她准备构造一个数组\(b\)满足：

\(b\)的每一位都和\(a\)对应位置不同，即\(b_i \neq a_i\)
\(b\)的所有元素之和都和\(a\)相同。
\(b\)的数组均为正整数。

请你告诉小美有多少种构造方式。由于答案过大，请对\(10^9+7\)取模。

输入

第一行输入一个正整数\(n\)，代表数组的大小。

第二行输入\(n\)个正整数\(a_i\)，代表小美拿到的数组。

\(1\leq n \leq 100\)
\(1\leq a_i \leq 300\)
\(1\leq \sum a_i \leq 500\)

输出

一个整数，代表构造方式对\(10^9+7\)取模的值。

样例

输入：
3
1 1 3

输出：
1

提示：
只有[2,2,1]这一种数组合法。

输入：
3
1 1 1

输出：
0

解答

这是一道特别特别裸的动态规划的题目，状态设计非常明显：令状态\(f(i,j)\)表示有多少个数组\(b\)满足如下条件：

其长度为\(i\)，和为\(j\)。
\(\forall p\in\{1,2,\dots,i\}\)，都有\(b_i\neq a_i\)。

那么可以写出如下状态转移方程：

\(f(i,j)= \left \{\begin{aligned} &1 & & \text{if}\quad i=0\land j=0 \\ &0 & & \text{if}\quad i=0\land j\neq 0 \\ &\sum_{1\le k\le j,k\neq a_i} f(i-1,j-k) & & \text{if}\quad i>0\\ \end{aligned}\right.\)

这个方程的前两行说明如果一个数组是空数组，那么其和为\(0\)。第三行假定了\(b_i\)可以填上任意不超过\(j\)的整数\(k\)，并且不能填上\(a_i\)，填上这个数\(k\)后，状态从\(f(i-1,j-k)\)转移到\(f(i,j)\)。

因此，最终答案为\(f(n,s)\)，其中\(\displaystyle{s=\sum_{i=1}^n a_i}\)。

代码

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

const int N=504;

int mod=1e9+7;
int f[N][N];
int a[N],n,s=0;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        s+=a[i];
    }
    f[0][0]=1;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=s;j++){
            for(int k=1;k<=j;k++){
                if(a[i]!=k){
                    f[i][j]=(f[i][j]+f[i-1][j-k])%mod;
                }
            }
        }
    }
    printf("%d\n",f[n][s]);
}

5、小美的数组操作

小美拿到了一个数组，她每次可以进行如下操作：

选择两个元素，一个加 \(1\)，另一个减 \(1\)。

小美希望若干次操作后，众数的出现次数尽可能多。你能帮她求出最小的操作次数吗？

众数定义：在一组数据中，出现次数最多的数据，是一组数据中的原数据，而不是相应的次数。一组数据中的众数不止一个，如数据2、3、-1、2、1、3中，2、3都出现了两次，它们都是这组数据中的众数。

输入

第一行为一个正整数\(n\)，代表数组的大小。第二行输入\(n\)个正整数\(a_i\)，代表小美拿到的数组。

\(1\leq n \leq 10^5\)
\(1\leq a_i \leq 10^9\)

输出

一个整数，代表最小的操作次数。

样例

输入：
3
1 4 4

输出：
2

提示：
第一次操作：第一个数加 1，第二个数减 1。
第二次操作：第一个数加 1，第三个数减 1。
数组变成[3,3,3]，众数出现了 3 次。

输入：
3
1 5 5

输出：
0

提示：
众数出现了 2 次，由于无法再用操作使得众数出现的次数变得更多，所以无需操作。

解答

令数组和\(\displaystyle{s=\sum_{i=1}^n a_i}\)。如果\(s\)是\(n\)的倍数，那么说明存在一种操作，可以使得众数的出现次数为\(n\)，这时得到的是\(a\)的平均数，只需要将所有值平均化即可。因此，令平均数\(\overline{a}=s/n\)，那么最终答案是\(\displaystyle{s=\sum_{1\le i\le n,a_i>\overline{a}} (a_i-\overline{a})}\)。

如果\(s\)不是\(n\)的倍数，那么必定存在一种方法可以使得众数的出现次数为\(n-1\)。具体操作是假设众数值是\(x\)，选定\(n-1\)个数，尝试将它们全部变成\(x\)，并且将多余的加\(1\)或者是减\(1\)操作未被选上的那\(1\)个元素。

因此，令这\(n-1\)个元素所构成的数组为\(b\)，如果现在要将\(b\)中的数都变成\(x\)，那么令\(\displaystyle{s_1(x)=\sum_{1\le i< n,b_i>x} (b_i-x),s_2(x)=\sum_{1\le i< n,b_i<x} (x-b_i)}\)。那么所需要的操作个数为\(f_(x)=\max\{s_1(x),s_2(x)\}\)，因为有些加\(1\)操作可以和减\(1\)操作共同处在同一个操作中，只花费一个次数。

假设\(m,M\)分别表示\(b\)中的最小值和最大值，那么可见\(s_1(x)\)在区间\([m,M]\)是一个递减函数，\(s_2(x)\)在区间\([m,M]\)是一个递增函数。因此\(f(x)\)是一个向下凹陷的函数，我们只需要找到函数\(f(x)\)的最低点即可。

在这里我使用的是二分法进行这个最低点，具体是找到最小的\(x\)使得\(f(x)<f(x+1)\)，那么\(x\)就是最低点。当然使用三分法也可以，具体不在这里讲述三分法。

最后一个问题：最终如何选择\(a\)中的\(n-1\)个数成为\(b\)？在这里我是直接用最小的\(n-1\)个数或者是最大的\(n-1\)个数，因为它们彼此更加接近，最优解必定在它们之间产生。

代码

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

const int N=100004;
ll a[N];
int n;
ll cal(ll *a,int n, ll x){
    ll s1=0,s2=0;
    for(int i=1;i<=n;i++){
        if(a[i]<x) s1+=x-a[i];
        else s2+=a[i]-x;
    }
    return max(s1,s2);
}
ll solve(ll *a,int n){
    ll l=0,r=1e9;
    while(l<r){
        ll mid=(l+r)>>1;
        if(cal(a,n,mid)<cal(a,n,mid+1)) r=mid;
        else l=mid+1;
    }
    return cal(a,n,l);
}
int main(){
    scanf("%d",&n);
    ll s=0;
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i]);
        s+=a[i];
    }
    ll ans=0;
    if(s%n==0){
        ll avg=s/n;
        for(int i=1;i<=n;i++){
            if(a[i]>avg) {
                ans+=a[i]-avg;
            }
        }
    }
    else{
        sort(a+1,a+n+1);
        ans=min(solve(a+1,n-1),solve(a,n-1));
    }
    printf("%lld\n",ans);
}