牛客小白月赛52 题解[非官方]

A题

• 多组测试，对于给出一个字符，"a:b"的形式，我们需要转化为对应的小时和分钟，然后再进行处理。大于8点的肯定是旷课;等于八点的，判断分钟，分钟小于等于5同时大于0的是迟到，分钟大于5就是旷课;小于八点的不处理。

#include<bits/stdc++.h>

using namespace std;


int main(){
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        int ans1=0,ans2=0;
        while(n--){
            string s;
            cin>>s;
            int h=0,m=0;
            int len=s.size();
            for(int i=0;i<len;i++){
                if(s[i]==':'){
                    for(int j=i+1;j<len;j++){
                        m=m*10+s[j]-'0';
                    }
                    break;
                }else{
                    h=h*10+s[i]-'0';
                }
            }
            if(h>8){
                ans2++;
            }else if(h==8){
                if(m<=5&&m>0) ans1++;
                else if(m>5) ans2++;
            }
        }
        cout<<ans1<<" "<<ans2<<endl;
    }
    return 0;
}

B题

• 模拟题，我们不断将对10取余，同时记录下当前的权值，如果当前的余数不小于4,那么就自增1，否则就不处理。每次更新维护当前四舍五入后的值即可。

#include<bits/stdc++.h>

using namespace std;

int main(){
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        int ans=n;
        int sum=1;
        int m=n;
        while(n>0){
            int x=n%10;n/=10;sum=sum*10;
            if(x>=5){
                n++;
                ans=max(ans,n*sum);
            }else{
                ans=max(ans,n*sum);
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}

C题

• 其实就是一个范围覆盖问题，三个询问分别可以对应三个区间，和，每个指令可以覆盖这个区间一次，我们需要找出被覆盖次数最少的点。然后数据范围也才1e6,我们可以用树状数组来处理，最后，遍历，维护查询结果最小的个数,答案就是(-查询结果最小值)以及最小值的个数。

#include<bits/stdc++.h>

using namespace std;

const int N=1e6+10;
int c[1000010];

void add(int x,int y){
    for(;x<N;x+=x&(-x)){
        c[x]+=y;
    }
}

int ask(int x){
    int sum=0;
    for(;x>0;x-=x&(-x)){
        sum+=c[x];
    }
    return sum;
}
int main(){
    int n,m;
    cin>>n>>m;
    int tmp=m;
    while(m--){
        int op;
        cin>>op;
        if(op==1){
            int x,y;
            cin>>x>>y;
            add(x,1);
            add(y+1,-1);
        }else if(op==2){
            int x;
            cin>>x;
            add(x,1);add(n+1,-1);
        }else{
            int x;
            cin>>x;
            add(1,1);add(x+1,-1);
        }
    }
    int ans=0;
    int mi=1e9;
    for(int i=1;i<=n;i++){
        int sum=ask(i);
        if(sum<mi){
            ans=1;
            mi=sum;
        }else if(mi==sum){
            ans++;
        }
    }
    cout<<tmp-mi<<" "<<ans<<endl;
    return 0;
}

D题

• 个数，分别有饱腹值和奶油含量。由于限制了一段连续的区间，所以我们可以用一个双指针来维护，同时由于是看做了一个圆弧的一段，所以我们需要在原来的数组的后面再补上一样的数组。同时，我们需要维护一个区间的最大值，这个我们可以用一个集合来维护，当边界移动的时候需要判断是否更新里面的元素，这里我们需要维护区间里面每个元素的个数。需要特判-1的情况，很显然就是个蛋糕的饱腹值的和小于的情况。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=5e5+10;
int a[N],b[N];
set<int> st;
map<int,int> mp;
int main(){
    int n,s;
    cin>>n>>s;
    ll tmp=0;
    for(int i=1;i<=n;i++){
        cin>>a[i];a[i+n]=a[i];
        tmp+=a[i];
    }
    for(int i=1;i<=n;i++){
        cin>>b[i];b[i+n]=b[i];
    }
    if(tmp<s){
        puts("-1");
        return 0;
    }
    int ans=1e9+7;
    ll sum=0;
    n+=n;
    for(int l=1,r=1;l<=n;l++){
        while(l<=r&&r<=n){
            if(sum>=s) break;
            sum+=a[r];
            mp[b[r]]++;
            st.insert(b[r]);
            ++r;
        }
        if(sum>=s){
            //cout<<l<<" "<<r<<endl;
            ans=min(ans,*st.rbegin());
        }
        mp[b[l]]--;
        if(mp[b[l]]==0){
            st.erase(b[l]);
        }
        sum-=a[l];
    }
    cout<<ans<<endl;
    return 0;
}

E题

• 个数组，每个数组最长可以为1e6，所以显然不能开个a[]来存储，但是我们可以用个来存储。同时我们需要使用一个数组来存储所有的元素，我们发现，对于一个数字x,我们需要找到有多少个可以匹配的，就是需要在所有的元素里面找到大于等于的元素的个数,同时找到这个元素对应的小朋友手中的数中大于等于的元素的个数，那么就有个元素是可以和数字有效匹配的，至于这个寻找我们可以通过排序然后二分查找的方式来降低时间复杂度。我们遍历所有的元素，执行上述操作，最后累加即可，求出的结果是最终答案的两倍，因为同时记录了和的情况,除以2取模即可。

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
const int mod=998244353;
const int N=1000010;
vector<int> v[N],a;
int num[N];
int p[N],q[N];
int main(){
    int n,k;
    cin>>n>>k;
    int cnt=0;
    for(int i=1;i<=n;i++){
        int s;cin>>s;num[i]=s;
        while(s--){
            int x;cin>>x;
            v[i].push_back(x);
            a.push_back(x);
            ++cnt;
            p[cnt]=x,q[cnt]=i;
        }
        sort(v[i].begin(),v[i].end());
    }


    sort(a.begin(),a.end());
    ll ans=0;
    int m=a.size();
    for(int i=1;i<=cnt;i++){
        int x=k-p[i],pos=q[i];
        int tmp1=lower_bound(v[pos].begin(),v[pos].end(),x)-v[pos].begin();
        int tmp2=lower_bound(a.begin(),a.end(),x)-a.begin();
        tmp1=num[pos]-tmp1;
        tmp2=m-tmp2;
        ans+=(tmp2-tmp1);
    }
    ans/=2;
    ans=(ans%mod+mod)%mod;
    cout<<ans<<endl;
    return 0;
}

F题

• 由于两种方案不同是骑士使用的能量总和不同，所以我们对能量和进行考虑，对于相同的能量和，我们肯定是需要让这些能量造成的伤害值尽可能大，这里使用分组背包来维护。我们使用一个数组，表示的是能量和为的时候造成的最大伤害。
• 然后对于每一种能量和，我们需要维护造成对应伤害值的方案数，这里我们使用表示的是第个骑士造成伤害值为的时候的方案数。

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;

const int mod=998244353;

const int N=3e3+10;

int a[N],b[N];
int dp[N];
ll dpp[N][N];

int main(){
    dpp[0][0]=1;
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        int s;cin>>s;
        for(int j=1;j<=s;j++){
            cin>>a[j];
        }
        int sum=0;
        for(int j=1;j<=s;j++){
            cin>>b[j];
            sum+=b[j];
        }

        // dp[i]表示当前这个骑士，能量消耗为i的时候的最大伤害值
        for(int j=0;j<N;j++) dp[j]=-1;
        dp[0]=0;
        for(int j=1;j<=s;j++){
            for(int k=sum;k>=0;k--){
                if(dp[k]>=0){
                    dp[k+b[j]]=max(dp[k+b[j]],dp[k]+a[j]);
                }
            }
        }


        // 枚举能量和
        for(int j=0;j<=sum;j++){
            // 过滤无效值
            if(dp[j]==-1) continue;
            for(int k=m;k>=0;k--){
                int x=min(k+dp[j],m);
                dpp[i][x]=(dpp[i][x]+dpp[i-1][k])%mod;
            }
        }
    }

    cout<<dpp[n][m]<<endl;

    return 0;
}