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;
}

2. 郭老师有草莓和山楂两种水果共计 \(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;
}

3. 你很想一边吃红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;
}

4. 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\) ，在 \(head\leq 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;
}

5. 给出 \(n\) 个整数 \(a_1,a_2,\cdots ,a_n(0\leq a_i\leq 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_i\bmod 10\) 分类。对于所有分到 \(a_i\bmod 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;
}

6. 双子座团队战开始了！这次有 \(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_i\bmod (a+b)>0\) 或 \((a+b)\) 。

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

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

若 \(H_i\leq a\) ，显然不需要额外攻击机会。否则，需要额外的 \(\lceil {H_i-a\over a}\rceil\) 次攻击机会。

我们将额外需要的攻击机会从小到大排序，在不超过 \(k\) 次的情况下尽可能选小的即可。复杂度 \(O(n\log 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;
}

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

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

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

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

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

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

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

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

而查询时，若出现不小于 \(a_i\) 的值，可以直接弹出。因为对于后续元素 \(a_j\) 而言，若 \(a_j\leq 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;
}

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

原文：https://www.cnblogs.com/JustinRochester/p/13546177.html