【LittleXi】美团后端8.10笔试题解

第一题签到题略

第二题：

题意：

小美有一个长度为元的数组 a1,a2,...,an ，输入n,x,k他可以进行两种操作：

● 删除第一个元素，同时数组的长度减一，花费为 x。

● 删除整个数组，花费为 MEX(a)(其中 MEX(a)表示第一个没有出现的非负整数）

题解：

可以考虑倒序遍历，每次求出后缀的mex，然后统计答案即可

#include<vector>
#include<set>
#include<iostream>
#include<map>

// 第二题,删除数字mex
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
void solve(){
    ll n,k,x;cin>>n>>k>>x;
    vector<ll> a(n);
    for(ll&x:a) cin>>x;
    reverse(a.begin(),a.end());
    ll mex = 0;
    vector<ll> me(n+2,0);
    ll ans = n*x;
    for(ll i =0;i<n;i++){
        me[a[i]] = 1;
        while(me[mex]) mex++;
        ans = min(ans, k*mex + (n-1-i)*x);
    }
    cout<<ans<<endl;
}

signed main(){
    cin.tie(0);cout.tie(0);
    ios::sync_with_stdio(0);
    ll t;cin>>t;
    while(t--)
        solve();
}

第三题：

题意：

给一个无限长的循环五颜六色纸带，每次询问要么减去前x长度，要么减去后x长度，问每次得到的带子的颜色数量

题解：

（典中典，原题来自HH的项链https://www.luogu.com.cn/problem/P1972）

可以考虑前面减和后面减情况独立

当减的长度超过n，那么全部颜色都有了，否则统计区间[l,r]颜色数量，这个可以按照r排序，每次只保留最靠近r的数字

比如1 2 1 3，枚举到0位置的时候是1 0 0 0 ,枚举到1位置的时候是 1 1 0 0 ,枚举到2位置的时候是0 1 1 0 ,枚举到3位置的时候是0 1 1 1 ，统计区间1的数量就行了

可以考虑树状数组单点修改，区间sum

#include<vector>
#include<set>
#include<iostream>
#include<map>

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

//坐标从0开始直接用的树状数组
template <typename T>
class Fenwick
{
private:
    int n;
    vector<T> c;
    int lowbits(int x){
        return (-x) & x;
    }
    int pre_sum(int i){
        int re = 0;
        for (; i > 0; i -= lowbits(i))
            re += c[i];
        return re;
    }
public:
    explicit Fenwick<T>(vector<T> v){
        this->n = v.size();
        this->c = vector<T>(n+1,0);
        for(int i=0;i<n;i++)
            add(i,v[i]);
    };
    void add(int i, int val){
        ++i;
        for (;i<=n; i += lowbits(i))
            c[i] += val;
    }
    int range_sum(int i,int j){
        ++i;++j;
        return pre_sum(j) - pre_sum(i - 1);
    }
};

vector<int> a;
vector<int> ans;

void del(vector<int> da,vector<vector<int>> qu){
    int n = da.size();
    sort(qu.begin(),qu.end(),[&](vector<int>&v1,vector<int>&v2){return v1[1] < v2[1];});
    Fenwick<int> fw(vector<int>(2*n,0));
    map<int,int> mp;
    int p = 0;
    for(int i = 0;i<qu.size();i++){
        while(p <= qu[i][1] ){
            if(mp.find(da[p])!=mp.end()){
                fw.add(mp[da[p]],-1);
            }
            fw.add(p,1);
            mp[da[p]] = p;
            p++;
        }
        ans[qu[i][2]] += fw.range_sum(qu[i][0],qu[i][1]);
    }
}

void solve(){
    int n, q , p1= 0 ,p2 = 0;
    cin>>n>>q;a = vector<int>(n);
    for(int&x:a)cin>>x;
    vector<vector<int>> ql , qr;
    ans =vector<int>(q,0);
    set<int> se(a.begin(),a.end());
    int wanz = se.size();
    for(int i = 0;i<q;i++){
        char c;cin>>c;
        int x;cin>>x;
        int wzt = x / n;
        if(wzt) ans[i] += wanz;
        if(c=='L') {
            if(x < n) ql.push_back({p1,p1+x - 1,i});
            p1 += x%n;
            if(p1>=n) p1 -= n;
        }else{
            if(x < n) qr.push_back({p2,p2+x-1,i});
            p2 += x%n;
            if(p2>=n) p2 -= n;
        }
    }
    vector<int> da = a;
    for(int x:a) da.push_back(x);
    del(da,ql);
    reverse(da.begin(),da.end());
    del(da,qr);
    for(int x:ans )cout<<x<<"\n";
}
int main(){
    cin.tie(0);cout.tie(0);
    ios::sync_with_stdio(0);
    solve();
}

♥关注LittleXi，谢谢喵，ACM金牌选手，更新更多题解♥