20200822综合设计期末试卷-题解

  1. 某家小吃店最近的生意分外火爆,但是店面不大,每次只能容纳最多 (n) 个人进行排队,如果小店已经挤满了人,新来的顾客就会离开。店家会每隔一段时间会供应 (m_i) 份点心,试问当供应的点心销售完后,正在排队又没有买到的顾客是哪些?

直接模拟。当有人进入排队时,若有之前产出的点心剩余,则直接买走;若队列已满,则直接退出;其他情况下均插入队列。

产出点心时,可以处理一下,当队内还有人时,优先给队内的人买。

最后输出队列即可。复杂度 (O(n+sum a_i))

#include<bits/stdc++.h>
using namespace std;
int main(){
    int T,N,Cnt=0,A,Num;
    queue<int> q;
    cin>>T>>N;
    while(T--&&cin>>A)
        if(!A){
            cin>>Num;
            Cnt+=Num;
            while(q.size())
                if(Cnt) q.pop(),Cnt--;
                else break;
        }
        else{
            for(int i=1;i<=A;i++){
                cin>>Num;
                if(Cnt){
                    Cnt--;
                    continue;
                }
                if(q.size()==N) continue;
                q.push(Num);
            }
        }
    if(q.empty()) cout<<-1;
    while(q.size()) cout<<q.front()<<" ",q.pop();
    return 0;
}

  1. 郭老师有草莓和山楂两种水果共计 (n) 个,她打算用这些水果做一串冰糖葫芦。她会把这串冰糖葫芦的水果组成用字符串的形式告诉你,其中’B’表示草莓,’W’表示山楂,例如:BBW,表示这串冰糖葫芦的水果按照顺序是草莓、草莓、山楂。郭老师想知道这串冰糖葫芦上的草莓串有几串,按照从左到右的顺序,这些草莓串的长度分别是多少?例如,冰糖葫芦WBBBBWWBWBBBW中共有 (3) 个草莓串它们的长度分别是 (4)(1)(3)

某原题,遍历字符串,找到 B 字母时向后扫出所有 B 字母即可。为方便处理,最后可以插入一个 W 字母。复杂度 (O(n))

#include<bits/stdc++.h>
using namespace std;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int N;
    string s;
    vector<int> v;
    (cin>>N).get();
    getline(cin,s);
    s+='W';
    for(int i=0;i<N;)
        if(s[i]=='W') i++;
        else{
            int Cnt=0;
            while(s[i]=='B') i++,Cnt++;
            v.push_back(Cnt);
        }
    cout<<v.size()<<endl;
    if(v.size()){
        for(auto num : v) cout<<num<<" ";
        cout<<endl;
    }
    return 0;
}

  1. 你很想一边吃红buff一边吃蓝buff。日有所思,夜有所梦。你在梦里构建了一个地形,一边是蓝buff,一边是红buff。你有两种技能q和e,你可以无限次数地使用它们,如果你使用技能q,你能选择对其中一个buff的血条减少或增加 (1) 点;如果你使用技能e,你能选择对两个buff的血条同时减少或增加1点。给定初始红蓝buff的血量和使用两种技能分别需要消耗的能量,你的目标是让红buff和蓝buff血条减少到零,并且耗费的能量最少。此时你就可以达成“红buff,蓝buff,我全都要”的成就。 总共有 (t) 组数据。

显然,要么只使用技能q,要么使用技能q和e。

只用技能q时,单次开销为 (a) 。总开销为 (a(x+y))

当需要使用技能e时,我们贪心一下:

我们先使用足够多次技能q,再使用技能e时。此时,两个buff应该血量相同。不妨设此时血量为 (h) ,则使用q的次数为 (|x-h|+|y-h|) ,使用e的次数为 (h) 。总开销为 (a(|x-h|+|y-h|)+bh)

显然,当 (h=min(x,y)) 时开销最小(前后两个式子同时取到最小值)。

因此对这两个取最小值即可。复杂度为 (O(T))

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    ll T,X,Y,A,B;
    cin>>T;
    while(T--){
        cin>>X>>Y>>A>>B;
        ll Ans=(max(X,Y)-min(X,Y))*A+min(X,Y)*B;
        Ans=min(Ans,(X+Y)*A);
        cout<<Ans<<endl;
    }
    return 0;
}

  1. Dio由于太喜欢吃面包成为了一个面包吃播,有一天他直播接受微博粉丝留言的最速吃播挑战:粉丝快递了两袋面包按顺序摆好,dio每次只能吃袋子里的第一个面包。由于面包大小口感不一,dio吃每个面包的时间都会有所差别。粉丝会给定时间限制,现在问你dio在这段时间内能吃的面包数量最多为多少?

Dio 爷当背景?讲究

某原题,设 (sa_i) 表示第一袋面包中,吃完前 (i) 个的耗时; (sb_i) 表示第二袋面包中,吃完前 (i) 个的耗时。

很显然,当 (sa_{head}+sb_{tail}leq t<sa_{head}+sb_{tail+1}) 时,若多吃一个第一袋的面包,那么吃第二袋面包的个数不会大于 (tail)

(sa_{head+1}+sb_{tail'}leq t<sa_{head+1}+sb_{tail'+1},tail'leq tail)

边界条件为若 (sa_{head}>t) ,此时已经不合法,直接退出。

接下来只要初始化 (head=-1,tail=m) ,在 (headleq n)(sa_{head}leq t) 范围内不停枚举 (head) ,而后将 (tail) 前移至合法位置即可。

复杂度为 (O(n+m))

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MAXN=2e5+10;
ll N,M,T,SA[MAXN],SB[MAXN];
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin>>N>>M>>T;
    for(int i=1;i<=N;i++) cin>>SA[i],SA[i]+=SA[i-1];
    for(int i=1;i<=M;i++) cin>>SB[i],SB[i]+=SB[i-1];

    ll Head=-1,Tail=M,Ans=0;
    while(Head<N){
        Head++;
        if(SA[Head]>T) break;
        while(SB[Tail]+SA[Head]>T) Tail--;
        Ans=max(Ans,Tail+Head);
    }
    cout<<Ans<<endl;
    return 0;
}

  1. 给出 (n) 个整数 (a_1,a_2,cdots ,a_n(0leq a_ileq 100)) 和整数 (k) 。定义 (f(a_i)=a_i/10) (直接向下取整) ,如 (f(24)=2,f(36)=3)(k) 的值可以自由分配给 (a_1,a_2,cdots ,a_n) 。求经过分配后所有 (f(a_i)) 和的最大值。(要求:经过分配后 (a_i) 不能超过 (100)(k) 可以不分配完)。

我们将所有的 (a_i)(a_imod 10) 分类。对于所有分到 (a_imod 10=c(c>0)) 的数字,他们只需要增加 ((10-c)) 即可对答案产生额外的贡献 (1)

贪心一下,优先从 ((10-c)) 最小的位置开始分配会对答案产生更高贡献。因此我们从 (9)(1) 枚举。

此后,若 (k) 仍有剩余,则仅需要在满足所有数均不超过 (100) 的过程中随机分配即可。

最后计算答案。复杂度为 (O(n))

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<ll> Cnt[10];
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    ll N,K,Ans=0;
    cin>>N>>K;
    for(int i=1;i<=N;i++){
        ll A;
        cin>>A;
        Cnt[A%10].push_back(A);
    }
    for(int i=9;i>=1;i--)
        for(auto &num : Cnt[i])
            if(K>=10-i)
                num+=10-i,K-=10-i;
    for(int i=9;i>=0;i--)
        for(auto &num : Cnt[i]){
            while(K>=10&&num<100) K-=10,num+=10;
            Ans+=num/10;
        }
    cout<<Ans<<endl;
    return 0;
}

  1. 双子座团队战开始了!这次有 (n) 个boss排成一列,编号从 (1)(n) ,第 (i) 只boss有 (h_i) 的血量。

    行会内只有你和会长两个人,所以你只能和你的会长轮流与boss作战。 首先你和你的会长一起打第一只boss,在打死了第一只boss后(boss的血量小于等于 (0) ),你才可以和你的会长打第二只boss,以此类推。

    你与会长轮流与boss进行战斗。

    当你与boss进行战斗,你可以对boss造成 (a) 点伤害,并且如果boss在这个回合被你杀死,那么就认为boss是你击杀的
    同理,会长在他的回合击杀了boss,就认为boss是他击杀的
    打每次boss时都是你先手
    现在你可以使用 ~让会长挂树~ 这一方法来迫使会长跳过一个他的回合,你最多只能使用 (k) 次这个方法。

    你想知道你最多能击杀几只boss。

之前某次周末的原题。

每只boss若轮流被两人攻击,最后一轮攻击前的血量一定会是 (h_imod (a+b)>0)((a+b))

仅需要在此时使用技能增加额外攻击机会即可。

我们不妨设 (H_i=egin{cases} h_imod (a+b),h_imod (a+b)>0 \ \ a+b,h_imod (a+b)=0 end{cases})

(H_ileq a) ,显然不需要额外攻击机会。否则,需要额外的 (lceil {H_i-aover a} ceil) 次攻击机会。

我们将额外需要的攻击机会从小到大排序,在不超过 (k) 次的情况下尽可能选小的即可。复杂度 (O(nlog n))

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll N,A,B,K,H;
vector<ll> v;
inline ll Ceil(ll P,ll Q) { return P/Q+!!(P%Q); }
inline ll calc(){
    H%=A+B;
    if(H>0&&H<=A) return 0;
    if(!H) H+=A+B;
    H-=A;
    return Ceil(H,A);
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin>>N>>A>>B>>K;
    for(int i=1;i<=N;i++) cin>>H,v.push_back( calc() );

    sort(v.begin(),v.end());
    ll Ans=0;
    for(auto num : v)
        if(K>=num) K-=num,Ans++;
    
    cout<<Ans<<endl;
    return 0;
}

  1. 已知一个有 (n) 个数的序列 (a_i) ,在序列 (a) 中的区间 ([l,r]) 中的最小值为 (a_p),求 (a_pcdot (a_l+a_{l+1}+...+a_r)) 的最大值为多少?

正面枚举区间,复杂度为 (O(n^2)) 显然不够。介于保证 (a_igeq 0) ,因此我们考虑枚举 (a_p)

贪心一下,由于 (a_igeq 0) ,因此对于固定的 (a_p) ,显然区间大小越大越好。

现在问题转化为对于序列 (a_i) 中的任何一个元素,求最大的区间 ([l,r]) 使得 (a_i) 为区间中的最小值。

(sa_i) 表示 (a_i) 的前缀和。那么,以这个元素作为 (a_p) 的贡献即为 (a_icdot (sa_r-sa_{l-1})) ,取最大值即可。

现在仅需求出每个 ([l,r]) 即可。

我们不妨设 (a_0=a_{n+1}=-infty) ,那么求解 (l) 仅需要求出 (a_i) 左边第一个小于它的位置 (+1)

我们用单调栈维护从小到大的 (a_i) 值。当新出现的 (a_ileq a_{top}) 时,显然 (l) 可以更左;当 (a_i>a_{top}) 时,若 (lleq top)(a_p=a_{top}<a_i) 因此 (l=top+1)

而查询时,若出现不小于 (a_i) 的值,可以直接弹出。因为对于后续元素 (a_j) 而言,若 (a_jleq a_i) 就没那些更大的值的事了;若 (a_j> a_i) ,显然它的 (l=i+1) 。因此查询时,不小于 (a_i) 的值直接弹出,最后将 (a_i) 插入栈中即可。

(r) 也是类似的方法。可以先求出所有 (a_i)(l) 值与 (r) 值再来统一计算。复杂度为 (O(n))

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MAXN=1e5+10;
ll N,A[MAXN],L[MAXN],R[MAXN],SA[MAXN];
inline void solve(){
    stack<int> stk;
    stk.push(0);
    for(int i=1;i<=N;i++){
        while(A[i]<=A[stk.top()]) stk.pop();
        L[i]=stk.top()+1;
        stk.push(i);
    }

    while(stk.size()) stk.pop();
    stk.push(N+1);
    for(int i=N;i>=1;i--){
        while(A[i]<=A[stk.top()]) stk.pop();
        R[i]=stk.top()-1;
        stk.push(i);
    }
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin>>N;
    for(int i=1;i<=N;i++) cin>>A[i],SA[i]=SA[i-1]+A[i];
    A[0]=A[N+1]=-0x3f3f3f3f;
    solve();
    ll Ans=0;
    for(int i=1;i<=N;i++)
        Ans=max(Ans, A[i]*( SA[ R[i] ]-SA[ L[i]-1 ] ) );
    cout<<Ans<<endl;
    return 0;
}
原文地址:https://www.cnblogs.com/JustinRochester/p/13546177.html