2024-3-16美团笔试题(A~E)

提前一小时AK纪念

A:

概述：有n个商品，价值a_i元，有一个x元的满减，一个y元的优惠卷，保证一定可以用到满减和优惠卷，问购买这n个商品需要多少元

思路：求和，减去x,y即可

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>

#define _for(i,a,b) for(int (i)=(a);(i)<=(b);(i)++)

using namespace std;
int main(void)
{
    int n;
    scanf("%d",&n);
    
    long long sum=-0;
    for(int i=1;i<=n;i++)
    {
        int x;
        scanf("%d",&x);
        sum+=x;
    }
    int a,b;
    scanf("%d%d",&a,&b);
    printf("%lld",sum-a-b);
}

B:

概述：给定一个只含有大小写字母的字符串，问至少可以变化几个字母的大小写，使得其满足以下条件之一

1.只含有大写字母

2.只含有小写字母

3.除首字母含有大写字母外，其余字母均为小写

思路:计算三种方案所需的开销，取min即可

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>

#define _for(i,a,b) for(int (i)=(a);(i)<=(b);(i)++)

using namespace std;
char s[100500];
int main(void)
{
    scanf("%s",s+1);
    int len=strlen(s+1);
    int cnt1=0,cnt2=0;
    _for(i,1,len)
    {
        if(s[i]<='z'&&s[i]>='a') cnt1++;
        else cnt2++;
    }
    printf("%d",min(cnt2-(s[1]<='Z'&&s[1]>='A'),cnt1));
}

C:

概述：有一个长度为n的数组，每个数组有一个权值val_i，有q次操作，每次操作给定一个数字x，之后除数组中第x个数以外，所有数的权值均翻倍，问q次操作后，所有数字之和mod 1e9+7是多少

思路：与其让所有数字翻倍，不如让该数组除以2，然后在操作结束后，让所有数字翻倍q次即可

当然，对于没有接触过数论和离散数学的同学，并不知道在同余系下的除法如何处理，因此只需要记录每个数字被除二了多少次，然后轮到他的时候给他翻倍q-t_i次即可(t_i 为第i个数被除二的次数)，对于翻倍q次的操作，我们采用快速幂去计算答案即可

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>

#define _for(i,a,b) for(int (i)=(a);(i)<=(b);(i)++)
#define MAXN 100050
const int mod=1000000007;
using namespace std;
int arr[MAXN];
int cnt[MAXN];
inline int quickpow(int x,int k)
{
    int res=1;
    while(k)
    {
        if(k&1) res=1ll*res*x%mod;
        x=1ll*x*x%mod;
        k>>=1;
    }
    return res;
}
int main(void)
{
    int n,q;
    scanf("%d%d",&n,&q);
    _for(i,1,n)
    {
        scanf("%d",&arr[i]);
    }
    _for(i,1,q)
    {
        int x;
        scanf("%d",&x);
        cnt[x]--;
    }
    int sum=0;
    _for(i,1,n)
    {
        sum+=1ll*quickpow(2,q+cnt[i])*arr[i]%mod;
        sum%=mod;
    }
    printf("%d",sum);
}

D:

概述：有一个数组，该数组仅仅含有1和2，区间[l,r]的权值为数组中第l个数到第r个数中的众数（如果有多个，则取较小的那个），问该数组中，每个区间的权值和为多少

前置知识：树状数组/线段树

思路：考虑有哪些区间的众数为2

设f(x)为数组在区间[0,x]中有多少个数字为2，若区间[l,r]的众数为2，那么该区间的2一定比1多

2的数量：f(r)-f(l-1)，1的数量：r-l+1-f(r)+f(l-1)

因此，该区间只需2*f(r)-r>2*f(l)-(l-1)即可

设g(x)=2*f(x)-x，因此，对于每个r结尾的区间，我们只需要知道有多少个l满足g(l)<g(r)即可，因此，我们考虑枚举右端点r，然后通过线段树或者树状数组维护一个可以动态添加以及计算区间和/前缀和的桶即可，然后在计算过所有[l,r]区间的值后，将g(r)添加进桶中即可。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>

#define _for(i,a,b) for(int (i)=(a);(i)<=(b);(i)++)

using namespace std;
#define MAXN 200050

int n;
int tree[MAXN<<4];
int arr[MAXN];
int sum[MAXN];
int val[MAXN];

inline int lowbit(int x)
{
    return x&(-x);
}
inline void update(int x,int k)
{
    for(int i=x;i<=2*n+10;i+=lowbit(i))
    {
        tree[i]+=k;
    }
}
inline int query(int x)
{
    int sum=0;
    for(int i=x;i;i-=lowbit(i))
    {
        sum+=tree[i];
    }
    return sum;
}
int main(void)
{
    scanf("%d",&n);
    _for(i,1,n)
    {
        scanf("%d",&arr[i]);
        sum[i]=sum[i-1]+(arr[i]==2);
    }
    update(1+n,1);
    long long cnt=0;
    _for(i,1,n)
    {
        val[i]=2*sum[i]+n-i+1;
        cnt+=query(val[i]-1);
        update(val[i],1);
    }
    printf("%lld",1ll*n*(n+1)/2+cnt);
}

E:

概述：对于一个排列，问，对于该排列中的每一个数字，将其变为其相反数后，该排列的逆序对有多少个

前置知识：树状数组维护逆序对

思路：由于取反后为负数，该数字一定小于原本的任何一个数字，我们可以先计算原排列的逆序对数目，然后对于每一个数字，计算他被取反后，能使该排列的逆序对变化多少

对于第i个数字，他在变为最小的数字后，在他之前的所有比他小的数字都会和他组成逆序对，在他之后所有比他小的数字会由原本构成逆序对转变成不构成逆序对，设在他之前比他小的数字的数量为x，因此该次操作的带来的变化为x-(v_i-1-x)，考虑原本的逆序对数目k，则第i个数字取反后的逆序对数目为k+x-(v_i-1-x)

参考上题用树状数组维护即可

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>

#define _for(i,a,b) for(int (i)=(a);(i)<=(b);(i)++)

using namespace std;
#define MAXN 200050
int n;
int arr[MAXN];
int tree[MAXN];
inline int lowbit(int x)
{
    return x&(-x);
}
inline void update(int x,int k)
{
    for(int i=x;i<=n;i+=lowbit(i))
    {
        tree[i]+=k;
    }
}
inline int query(int x)
{
    int sum=0;
    for(int i=x;i;i-=lowbit(i))
    {
        sum+=tree[i];
    }
    return sum;
}
int main(void)
{
    scanf("%d",&n);
    long long sum=0;
    _for(i,1,n)
    {
        int x;
        scanf("%d",&x);
        sum+=query(n)-query(x);
        int temp=query(x-1);
        arr[i]=temp-(x-1-temp);
        update(x,1);
    }
    _for(i,1,n)
    {
        printf("%lld ",sum+arr[i]);
    }
}

;Bval

}