美团笔试题解2022-3-12号

第一题 签到

题目大意

n组数据，判断每组是否可以被11整除或者还有两个数位1

两个条件满足其一输出yes 否则输出no

第二题 双指针

题目大意

输入一个序列 只含±1

输出连续子序列乘积为正的数目

#include<bits/stdc++.h>
using namespace std;
const int N=5010;
int num[N];
int main() {
          
   
    int n;
    int sum=0;
    int ans=0;
    cin>>n;
    for(int i=0;i<n;i++){
          
   
        cin>>num[i];
        if(num[i]==1)sum++;
    }
    ans+=sum;
    for(int i=0;i<n;i++){
          
   
        int t=num[i];
        for(int j=i+1;j<n;j++){
          
   
            t*=num[j];
            if(t==1)ans++;
        }
    }
    cout<<ans<<endl;
    return 0;
}

第三题 贪心

题目大意

一共有n个顾客 m道菜，原材料只够每道菜做一份，每个顾客点两个菜，只有吃到自己满意的菜才满意，输出顾客满意的最大数目。

#include<bits/stdc++.h>
using namespace std;
int num[50];
typedef pair<int,int> pii;
pii a[50],b[50];
vector<bool> vis;
int main()
{
          
   
    int n,m,ans=0;
    cin>>n>>m;
    vis=vector<bool>(m);
    for(int i=0;i<n;i++){
          
   
        int p,q;
        cin>>p>>q;
        a[i]={
          
   p,q};
        num[p]++;
        num[q]++;
    }
    for(int i=0;i<n;i++){
          
   
        int p=a[i].first,q=a[i].second;
        int sum=0;
        sum+=num[p]+num[q];
        b[i]={
          
   sum,i};
    }
    sort(b,b+n);
    for(int i=0;i<n;i++){
          
   
        int k=b[i].second;
        int p=a[k].first,q=a[k].second;
        if(!vis[p]&&!vis[q]){
          
   
            ans++;
            vis[p]=vis[q]=true;
        }
    }
    cout<<ans<<endl;
    return 0;
}

第四题 动态规划 （状态压缩DP）

题目大意

炸弹游戏，初始在房间1，持续时间m，每一s后第i个房间会爆炸，迁移到另一个房间损耗能量1，求无伤通关消耗的最低能量

dfs深度搜索 55%

#include<bits/stdc++.h>
using namespace std;
const int N=1e4+10;
int a[N],num[15];
int n,m;
int ans=0x3f3f3f3f;
pair<int,int> p[15];
void dfs(int st,int u,int s){
          
   
    if(s>=ans)return;
    if(u==m){
          
   
        ans=min(ans,s);
        return;
    }
    if(a[u]==st){
          
   
        for(int i=1;i<=n;i++){
          
   
            int t=p[i].second;
            if(t!=st&&t!=a[u+1]){
          
   
                dfs(t,u,s+1);
                break;
            }
        }
    }else{
          
   
        dfs(st,u+1,s);
    }
}
int main()
{
          
   
    cin>>n>>m;
    for(int i=0;i<m;i++){
          
   
        scanf("%d",&a[i]);
        num[a[i]]++;
    }
    for(int i=1;i<=n;i++){
          
   
        p[i]={
          
   num[i],i};
    }
    sort(p,p+n);
    dfs(1,0,0);
    cout<<ans<<endl;
    return 0;
}