【LittleXi】拼多多后端8.11解题报告

极限ak，开题顺序3421成谜

A、旅行计划

题意：

给定n个旅行计划，每个旅行计划完成的时间只能是xi,xi+d,xi+2d,...，并且每天最多只能完成一个旅游，求最小时间

题解：

可以考虑维护当前的天数result

如果result小于当前旅行计划开始的天数，那么result = day_i

否则求最小的b使得day_i + b * d > result

注意坑就是求b的时候，也可以day_i + b * d = result ， 此时要b++

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

void solve(){
    ll n;
    cin>>n;
    vector<vector<ll>> data(n,vector<ll>(3));
    for(ll i= 0;i<n;i++){
        cin>>data[i][0]>>data[i][1]>>data[i][2];
    }
    sort(data.begin(),data.end());
    ll result = 1;
    for(ll i =0;i<n;i++){
        vector<ll> current = data[i];
        if(result < current[1]){
            result = current[1];
        }
        else{
            ll day = current[1];
            ll dis = result - day;
            ll b = dis/current[2] + (dis%current[2] > 0);
            if(day + b * current[2]==result) b ++;
            result = day + b * current[2];
        }
    }
    cout<<result<<endl;
}

signed main(){
    cin.tie(0);cout.tie(0);
    ios::sync_with_stdio(0);
    solve();
}

B、多多的作业

题意：

给定n个作业，作业有开始时间和需要的时间，求最小总作业消耗时间，单个作业消耗时间是作业完成时间减去作业开始时间

题解：

可以考虑使用优先队列进行贪心， 每次获取作业的时候，对于前面那个时间片，我们优先让消耗时间小的作业被计算

代码：

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

void solve(){
    ll n;
    cin>>n;
    vector<pair<ll,ll>> vp(n);
    for(ll i =0;i<n;i++) cin>>vp[i].first>>vp[i].second;
    priority_queue<ll,vector<ll>,greater<ll>> pq;
    ll t = 1 , ans = 0;
    pq.push(vp[0].second);
    for(ll i =1;i<n;i++){
        ll d = vp[i].first - vp[i-1].first;
        while(pq.size()&&d){
            auto x = pq.top();pq.pop();
            ll dis = min(x,d);
            ans += dis * (pq.size() + 1);
            x -= dis ; d -= dis;
            if(x) pq.push(x);
        }
        pq.push(vp[i].second);
    }
    while(pq.size()){
        ll x = pq.top();pq.pop();
        ans += x * (pq.size() + 1);
    }
    cout<<ans;
}

signed main(){
    cin.tie(0);cout.tie(0);
    ios::sync_with_stdio(0);
    solve();
}

C、玫瑰和牡丹

题意：

给一个01串，你可以最多选择一个区间进行反转，0->1 , 1->0 ,求最终abs(cnt[0]-cnt[1])的可能数

题解：

我们可以这样考虑，每次延长我们的[l,r]区间一次，cnt[0] - cnt[1] 要么+1，要么-1，所以我们可以求一个区间，使得cnt[0] - cnt[1] 最大或者最小，这个可以使用前缀和解决，那么对于最大的cnt[0] - cnt[1] ， 一定可以每次+2到达，所以沿途的数字都可以到达

代码：

// 3
#include<bits/stdc++.h>
using namespace std;
#define ll long long
void solve(){
    int n ;cin>>n;
    vector<int> a(n);
    for(int&x:a) cin>>x;
    for(int&x:a) if(x==0) x = -1;
    int prmi = 0 , prmx = 0;
    int pr = 0;
    int mx = 0 , mi = 0;
    for(int i = 0;i<n;i++){
        pr += a[i];
        mx = max(mx,pr-prmi);
        mi = min(mi,pr-prmx);
        prmx = max(prmx,pr);
        prmi = min(prmi,pr);
    }
    set<int> se;
    int sm = accumulate(a.begin(),a.end(),0);
    for(int i = sm - 2*mx ; i <= sm -2*mi;i+=2){
        se.insert(abs(i));
    }
    cout<<se.size();
}

signed main(){
    cin.tie(0);cout.tie(0);
    ios::sync_with_stdio(0);
    solve();
}

D、哈希表

难度：区域赛铜牌题目，一股ACM味儿

题意：

哈希函数为f = x % n , 给定一个插入完成的哈希表，要求还原插入顺序，如果多个可能，还原字典序最小的

题解：

很容易想到使用拓扑排序，对于从i位置跳到j位置的数字， 将[i,j-1]的所有点连向j，然后进行拓扑排序+贪心就行，时间复杂度n^2 , 不行

可以考虑优化，删除一个数字之后，一定是右边最靠近这个数字可能被选，可以压进优先队列中，查找右边那个数字可以考虑使用树状数组+二分，时间复杂度nlg^2n

代码：

// 4
#include<bits/stdc++.h>
using namespace std;
#define ll long long
//坐标从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);
    }
};


void solve(){
    int n;cin>>n;
    vector<int> a(n);
    for(int &x:a) cin>>x;
    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;
    map<int,int> mp;
    for(int i =0;i<n;i++){
        if(a[i]==-1) a[i] = 0;
        else if(a[i]%n==i){
            pq.push({a[i],i});
            mp[a[i]] = 1;
        }
    }
    for(int i =0 ;i < n;i++) a.push_back(a[i]);

    vector<int> b = a;
    for(int&x:b) if(x) x = 1;
    Fenwick<int> fw(b);

    vector<int> ans;
    while(pq.size()){
        auto p = pq.top();pq.pop();
        int x = p.first , pos = p.second;
        ans.push_back(x);
        fw.add(pos,-1);fw.add(pos+n,-1);
        int l = pos , r = 2*n;
        while(l+1!=r){
            int m = l+r>>1;
            if(fw.range_sum(pos,m)==0) l = m;
            else r = m;
        }
        l++;
        if(l<2*n&&fw.range_sum(pos,l)==1){
            if(mp[a[l]]) continue; 
            int lp = a[l]%n;
            if(lp > l) l+=n;
            if(fw.range_sum(lp, l - 1)==0){
                mp[a[l]] = 1;
                if(l >= n ) l -= n;
                pq.push({a[l],l});
            }
        }
    }
    for(int x:ans) cout<<x<<" ";
}

signed main(){
    cin.tie(0);cout.tie(0);
    ios::sync_with_stdio(0);
    solve();
}

❤关注LittleXi ,谢谢喵， ACM金牌，持续更新更多题解❤

也可以提供大厂算法辅导喵