美团秋招 2023.09.02 编程题目与题解

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

1、小美的升序数组

给定一个大小为\(n\)的数组\(a\)，请你判断一个数组是否满足以下条件:

数组严格升序，即\(a_1 < a_2 <\dots < a_n\)。
对于\(1 \le i\le n-1\)，我们定义\(b_i = a_{i+1} - a_i\)，则数组严格降序，即\(b_1 > b_2 >\dots > b_{n-1}\)。

输入

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

第二行输入\(n\)个正整数\(a_i\)，代表给定的数据。

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

输出

若满足给定的两个条件，则输出Yes。否则输出No。

样例

输入：
3
1 3 4

输出：
Yes

输入：
3
1 3 3

输出：
No

输入：
3
1 2 3 4

输出：
No

解答

这题似乎没有什么难度，直接按照题意模拟这两个条件即可。

代码

# include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=100005;
int a[N],b[N],n;
bool ok(){
    for(int i=1;i<n;i++){
        if(a[i]>=a[i+1]) return 0;
        b[i]=a[i+1]-a[i];
    }
    for(int i=1;i<n-1;i++){
        if(b[i]<=b[i+1]) return 0;
    }
    return 1;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    puts(ok()?"Yes":"No");
}

2、小美的子序列

小美在\(n\)行\(m\)列的本子上写了许多字母，她会在每一行中找出一个字母，然后组成一个字符串。

小美想知道，组成的字符串中是否存在至少一个字符串包含"meituan"子序列。

输入

第一行输入\(2\)个整数\(n,m(1\le n,m\le 1000)\)。

接下来\(n\)行，每行输入一个长度为\(n\)的字符串表示小美写下的字母。

输出

若存在至少一个字符串包含"meituan"子序列，则输出"YES"，否则输出"NO"。

样例

输入：
3 3
abc
def
ghi

输出：
NO

提示：
显然并不能找到meituan子序列。

输入：
8 2
nm
ex
it
td
ul
qu
ac
nt

输出：
YES

提示：
第1行选择第2个字母。
第2行选择第1个字母。
第3行选择第1个字母。
第4行选择第1征字母。
第5行选择第2个字母。
第6行选择第2个字母。
第7行选择第1个字母。
第8行选择第1个字母。
组成字符串"meitluan"，其中存在"meituan"子序列。
当然，第6行选第1个字母且第5行选第1个字母组成的字符串"meituqan"中也存在"meituan"子序列。

解答

假设现在有一个字符串为\(p=\texttt{meituan}\)，并且有一个指针\(j\)指向\(p\)的一个字母（或者是\(p\)的最后一个字符后面）。一开始\(j=0\)。

对于每次输入的字符串\(s\)，如果\(p[j]\)在\(s\)中，那么说明此线输入的所有字符串包含了当前前\(j\)个字母的子序列，这时将\(j\)加上\(1\)。

如果\(j\)指向了\(p\)的最后一个字符后面，说明可以匹配，应当输出"YES"。

代码

# include <bits/stdc++.h>
using namespace std;
int main(){
    string p="meituan",s;
    int n,m;
    cin>>n>>m;
    int j=0;
    for(int i=0;i<n&&j<p.size();i++){
        cin>>s;
        if(s.find(p[j])!=-1){
            ++j;
        }
    }
    puts(j==p.size()?"YES":"NO");
}

3、小美的数组

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

选择一个元素，使其乘以\(2\)。
选择一个元素，使其除以\(2\)，向下取整。

小美希望第一个元素变成所有元素的最大值。请你判断小美最少需要操作多少次?

输入

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

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

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

输出

输出最小操作次数。

样例

输入：
4
1 2 3 4

输出：
2

提示：
将第一个元素乘两次2即可。

解答

显而易见，最优的做法是将乘\(2\)操作施加在第\(1\)个元素\(a_1\)，除\(2\)操作必定施加在第\(2\sim n\)个元素。可以发现答案必定不会超过\(32\)次，因为无论\(a_1\)初值如何，乘上\(32\)次\(2\)必定是最大值。

因此，我们可以枚举乘法操作次数\(m\)，判断\(32-m\)次内能否将\(a\)的第\(2\sim n\)个元素的最大值降到不超过\(a_1\cdot 2^m\)，如果不行，那么说明\(m\)还不够大；否则，记录满足条件时，除法的操作次数为\(k\)，那么\(m+k\)就是一个候选答案。

当\(n=1\)的时候，什么都不需要做，输出\(0\)。

代码

# include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=100004,M=104;
int a[N],b[M];
int main(){
    int n;
    scanf("%d",&n);
    int w=0,x;
    priority_queue<int>q;
    for(int i=1;i<=n;i++){
        scanf("%d",&x);
        if(i==1) w=x;
        else q.push(x);
    }
    int ans=0x3f3f3f3f;
    if(n>1){
        for(int i=0;i<M;i++){
            int x=q.top();q.pop();
            b[i]=x;
            q.push(x>>1);
        }
        for(int k=0;k<=31;k++){
            ll x=1ll*w<<k;
            int j;
            for(j=0;j<M&&x<b[j];++j);
            ans=min(ans,k+j);
        }
    }
    else ans=0;
    printf("%d\n",ans);
}

4、小美的元素删除

小美有一个数组，她希望删除\(k\)个元素，使得剩余的元素两两之间互为倍数关系。你能告诉小美有多少种删除方案吗？

由于答案过大，请对\(10^9+7\)取模。

输入

第一行输入两个整数\(n,k(1\le k\le n\le 10^3)\)表示数组长度，删除的元素数量。

第二行输入\(n\)个整数表示数组\(a(1\le a_i\le 10^9)\)。

保证给定的数组中不存在两个相等元素。

输出

输出一个整数表示答案。

样例

输入：
6 4
1 4 2 3 6 7

输出：
8

提示：
方案1:删除1,4.2,7。
方案2:删除1,4,3,7。
方案3:删除1,3,6,7。
方案4:删除4,2,3,6。
方案5:删除4,2,3,7。
方案6:删除4,2,6,7。
方案7:删除4,3,6,7。
方案8:删除2,3,6,7。

解答

令\(k'=n-k\)，即保留下来的数的数量。一个特殊情况是，如果\(k'=0\)，那么说明全部数都被删去了，只有\(1\)种方法，因此输出\(1\)。

此外，这一题给出了一个非常重要的条件：输入的元素两两之间不相等。

由于倍数关系具有传递性，因此假设\(b_1,b_2,\dots,b_m\)是满足题目条件的一个递增序列，那么由于元素各不相同，因此\(b\)的后一个元素必定是前一个元素的至少\(2\)倍。

另一方面，由于题目限定了输入的值最大为\(10^9\)，因此上面的\(b\)序列的长度\(m\)不会超过\(32\)。因此这意味着，如果\(k'\ge 32\)，那么可以直接输出\(0\)。

由于子序列中的倍数关系对顺序并没有影响，因此我们考虑对\(a\)排序，使用动态规划的思想计算出这样的序列个数。

假设现在排序后，已经满足\(a_1<a_2<\dots<a_n\)。令状态\(f(i,j)(1\le i\le k',1\le j\le m)\)表示长度为\(i\)，并且以\(a_j\)为终点的倍数关系的子序列个数。由于倍数关系是传递关系，因此只需要保证后一个元素是前一个元素的倍数即可。那么我们可以写出状态转移方程：

\(f(i,j)= \left \{\begin{aligned} &1 & & \text{if}\quad i=1 \\ &\sum_{1\le k<j,a_k\mid a_j} f(i-1,k) & & \text{if}\quad i>1 \\ \end{aligned}\right.\)

其中这个状态转移方程的意思是，如果\(a_j\)是\(a_k\)的倍数，那么\(a_j\)可以放在\(a_k\)的后面，此时\(a_j\)同样是\(f(i-1,k)\)中所有方案，非\(a_k\)的元素的倍数。

因此，最终答案为\(\displaystyle{\sum_{j=1}^n f(k',j)}\)。

需要注意的是，上面的算法如果暴力实现，那么可能达到\(O(k'n^2)\)的运行时间。由于一个数\(x\)只有\(O(\log x)\)个因子，因此我们可以考虑先预处理出每一对满足\(a_k\mid a_j\)的有序对\((k,j)\)，然后在求解\(f(i,j)\)的时候直接查找这些有序对即可（可以把它们看成是一个有向图的边邻接表），这种情况下的实现的时间复杂度为\(O(n^2+k'n\log n)\)，比原来快。

代码

# include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1004;
const int K=35;
int mod=1e9+7;
int n,k;
int f[K][N];
int a[N];
vector<int>g[N];
int main(){
    scanf("%d %d",&n,&k);
    k=n-k;
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    int ans=0;
    if(k>=32) ans=0;
    else if(k==0) ans=1;
    else{
        sort(a+1,a+n+1);
        for(int i=1;i<=n;i++)
            for(int j=1;j<i;j++)
                if(a[i]%a[j]==0){
                    g[i].push_back(j);
                }
        for(int j=1;j<=n;j++)
            f[1][j]=1;
        for(int i=2;i<=k;i++){
            for(int j=1;j<=n;j++){
                for(int x:g[j]){
                    f[i][j]=(f[i][j]+f[i-1][x])%mod;
                }
            }
        }
        for(int j=1;j<=n;j++){
            ans=(ans+f[k][j])%mod;
        }
    }
    printf("%d\n",ans);
}

5、小美的彩虹糖

小美有很多的彩虹糖，每颗彩虹糖都有一个颜色，她每天可以吃两颗彩虹糖，如果今天吃的彩虹糖组合是之前没吃过的组合，则小美今天会很高兴。

例如，小美有\(6\)颗彩虹糖，颜色分别是\([1,1,4,5,1,4]\)。

小红第一天吃一组颜色为\(1\)和\(4\)的彩虹糖，小美会很高兴；

第二天吃一组颜色\(4\)和\(1\)的彩虹糖，小美不会很高兴；第三天小美吃一组颜色为\(1\)和\(5\)的彩虹糖，小美会很高兴，此时小美共有\(2\)天很高兴小美想知道，她最多有几天会很高兴。

输入

第一行输入一个整数\(n(1 \le n \le 10^5)\)表示彩虹糖数量。

第二行输入\(n\)个整数表示彩虹糖颜色\(a(1 \le a_i \le 10^9)\)。

输出

输出一个整数表示答案。

样例

输入：
6
1 1 4 5 1 4

输出：
3

提示：
第1天吃一组颜色为1，4的彩虹糖。
第2天吃一组颜色为4，5的彩虹糖。
第3天吃一组颜色为1，1的彩虹糖。
小美3天都会很高兴。

解答

这一题我采取的做法是未经验证的，仅作参考。

基本思想是，每次从数组中取一个使用过的频率最高的数\(x_1\)（如果没有，那么选择未使用过的频率最高的），然后按照类似的方式，贪心地优先选择使用过的频率最高的数\(x_2\)，否则选择未使用过的数（也就是说策略和\(x_1\)类似），如果\((x_1,x_2)\)已经在集合中，那么查找下一个这样的\(x_2\)；否则，将\((x_1,x_2)\)添加到集合中。

如果没有\(x_2\)可以和\(x_1\)匹配上，那么说明\(x_1\)已经无处匹配，需要丢弃。

最终如此选择的集合作为答案。

代码

# include <bits/stdc++.h>
# define pi pair<int,int>
using namespace std;
typedef long long ll;
const int N=100004;
unordered_map<int,int>cnt;
struct P{
    int used,cnt,val;
    bool operator < (const P & p)const {
        return used>p.used||used==p.used&&(cnt>p.cnt||cnt==p.cnt&&val>p.val);
    }
};
set<pi>st;
set<P>db;
int main(){
    int n,x;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&x);
        ++cnt[x];
    }
    for(auto &[k,c]:cnt){
        db.insert(P{0,c,k});
    }
    while(!db.empty()){
        P o1=*db.begin();db.erase(o1);
        o1.cnt--;o1.used=1;
        if(o1.cnt>0){
            db.insert(o1);
        }
        P o2=P{-1,-1,-1};
        for(P o:db){
            int x=min(o1.val,o.val),y=max(o1.val,o.val);
            if(!st.count(pi(x,y))){
                o2=o;
                break;
            }
        }
        if(o2.used==-1){
            db.erase(o1);
        }
        else{
            db.erase(o2);
            o2.cnt--;o2.used=1;
            if(o2.cnt>0){
                db.insert(o2);
            }
            st.insert(pi(min(o1.val,o2.val),max(o1.val,o2.val)));
        }
    }
    printf("%d\n",st.size());
}